[itk] Számítástechnika kezdőknek

C++ programozás kezdőknek - programozási tételek

[2022. április 08.] [ christo161 ]

A programozási tételek olyan algoritmusok, amiket tipikus alapvető feladatok megoldásához használunk.

előző tananyagrész: STL

Megszámlálás

Ha egy adott feltétel teljesül a tömb aktuális elemére ahogy végiglépkedünk a tömb elemein, akkor a megszámoláshoz használt változó értékéhez hozzáadunk egyet.

Pl. hány darab páros szám van a tömbben.

//count
#include <iostream>
#include <vector>

int main() {
  std::vector<int> example = {1,2,3,4,5,6,7,8,9,10};
  int count = 0;

  for (int i = 0; i < example.size(); ++i) {
    if (example[i] % 2 == 0) {
      ++count;
    }
  }

std::cout << "Number of even numbers: " << count << '\n';
}

Hasonlóan működik az STL std::count_if függvénye.

Összegzés

Ha egy adott feltétel teljesül a tömb aktuális elemére ahogy végiglépkedünk a tömb elemein, akkor az összegzéshez használt változó értékéhez hozzáadjuk a tömb aktuális elemét.

Pl. összeadjuk a páros számokat.

//sum
#include <iostream>
#include <vector>

int main() {
  std::vector<int> example = {1,2,3,4,5,6,7,8,9,10};
  int sum = 0;

  for (int i = 0; i < example.size(); ++i) {
    if (example[i] % 2 == 0) {
      sum += example[i];
    }
  }

std::cout << "Sum of even numbers: " << sum << '\n';
}

Hasonlóan működik az STL std::accumulate függvénye.

Maximumkiválasztás

A maximum érték tárolására használt változó először a tömb első elemét tartalmazza. Ha találunk ennél nagyobb elemet ahogy végiglépkedünk a tömb elemein, akkor azt adjuk értékül a maximum tárolására használt változónak.

A ciklus a tömb második elemétől indul, mivel nem kell megvizsgálni, hogy a tömb első eleme nagyobb-e saját magánál.

//max
#include <iostream>
#include <vector>

int main() {
  std::vector<int> example = {13,8,7,21,5,32,-2,17,11,10};
  int max = example[0];

  for (int i = 1; i < example.size(); ++i) {
    if (max < example[i]) {
      max = example[i];
    }
  }

std::cout << "The biggest number: " << max << '\n';
}

Eldöntés

Ha egy adott feltétel teljesül a tömb egyik elemére, akkor a logikai változó értékét igazra állítjuk. A logikai változó kezdőértéke hamis, mivel akkor még nem tudjuk, hogy teljesül-e a feltétel a tömb egyik elemére.

Pl. van-e a tömbben páros szám vagy prímszám-e egy adott szám (van-e osztója).

Ha megtaláltuk a feltételnek megfelelő elemet, a ciklust nem kell tovább folytatni, ki lehet lépni a ciklusból.

//contains
#include <iostream>
#include <vector>

int main() {
  std::vector<int> example = {13,8,7,21,5,32,-2,17,11,10};
  bool contains_even = false;

  for (int i = 0; i < example.size(); ++i) {
    if (example[i] % 2 == 0) {
      contains_even = true;
      break;
    }
  }

  if (contains_even) {
    std::cout << "There is an even number in the numbers.\n";
  } else {
    std::cout << "There isn't any even number in the numbers.\n";
  }
}

Lineáris keresés

Ugyanaz, mint az eldöntés tétel, csak ha találtunk a feltételnek megfelelő elemet a tömbben, akkor annak az indexét is visszaadjuk.

//search
#include <iostream>
#include <vector>

int main() {
  std::vector<int> example = {13,8,7,21,5,32,-2,17,11,10};
  int contains_even = false;
  int index = -1;

  for (int i = 0; i < example.size(); ++i) {
    if (example[i] % 2 == 0) {
      contains_even = true;
      index = i;
      break;
    }
  }

  if (contains_even) {
    std::cout << "There is an even number in the numbers.\n";
    std::cout << "Its index is: " << index << '\n';
  } else {
    std::cout << "There isn't any even number in the numbers.\n";
  }
}

Hasonlóan működik az STL std::find_if függvénye.

Logaritmikus, vagy más néven bináris keresés

Csak rendezett tömbökre működik.

Megfelezzük a tömböt. Megnézzük, hogy az elem a tömb első vagy a második felében van. Ha például az első felében, akkor azt tovább felezzük, és így tovább, amíg meg nem találjuk az elemet.

Ebben a példában egy 1 és 12 közti random generált számot keresünk meg egy 1 és 10 közötti számokat tartalmazó tömbben.

//binary search
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

int generate_rnd_number(const int& intval_begin, const int& intval_end) {
  static std::mt19937 rnd_generator( std::random_device{}());
  std::uniform_int_distribution<int> int_dist(intval_begin,intval_end);
  return int_dist(rnd_generator);
}

int main () {
  std::vector<int> example = {1,2,3,4,5,6,7,8,9,10};
  int find = generate_rnd_number(1,12);
  bool contains = false;
  int index = -1;

  int low = 0;
  int high = example.size()-1;

  while (low <= high && !contains) {
    int mid = (low + high) / 2;
    if (find == example[mid]) {
      contains = true;
      index = mid;
    } else if (find < example[mid]) {
      high = mid-1;
    } else if (find > example[mid]) {
    low = mid+1;
  }
}

  std::cout << "Find: " << find << '\n';
  if (contains) {
    std::cout << "Found at index: " << index << '\n';
  } else {
    std::cout << "Not found\n";
  }
}

Kiválogatás

Egy tömbből bizonyos feltételnek megfelelő elemeket átmásoljuk egy másik tömbbe. Pl. kiválogatjuk a páros számokat.

//select
#include <iostream>
#include <vector>

int main() {
  std::vector<int> input = {1,2,3,4,5,6,7,8,9,10};
  std::vector<int> output;

  for (int i = 0; i < input.size(); ++i) {
    if (input[i] % 2 == 0) {
      output.push_back(input[i]);
    }
  }

  for (const int& element : output) {
    std::cout << element << " ";
  }
  std::cout.put('\n');
}

Szétválogatás

Egy tömbből bizonyos feltételnek megfelelő elemeket átmásoljuk egy másik tömbbe, a feltételnek nem megfelelő elemeket pedig egy harmadik tömbbe.

#include <iostream>
#include <vector>

int main() {
  std::vector<int> input = {1,2,3,4,5,6,7,8,9,10};
  std::vector<int> even;
  std::vector<int> odd;

  for (int i = 0; i < input.size(); ++i) {
    if (input[i] % 2 == 0) {
      even.push_back(input[i]);
    } else {
      odd.push_back(input[i]);
    }
  }

  std::cout << "Even numbers:\n";
  for (const int& element : even) {
    std::cout << element << " ";
  }
  std::cout.put('\n');

  std::cout << "Odd numbers:\n";
  for (const int& element : odd) {
    std::cout << element << " ";
  }
  std::cout.put('\n');
}

Szétválogatás egy tömbön belül (rendezés nélkül)

Ebben a példában páros és páratlan számokat válogatunk szét. A párosak kerülnek a tömb elejére, a páratlanok a tömb végére.

Az első elem mindenképp át lesz helyezve, mégpedig középre, így tehát mindegy, hogy páros vagy páratlan. A többi áthelyezésnél pedig mindig az előző áthelyezésnél felszabadult helyre helyezünk át.

#include <iostream>
#include <random>
#include <vector>

void generate_rnd_number(std::vector<int>& vec, const int& howmany, const int& intval_begin, const int& intval_end) {
  static std::mt19937 rnd_generator( std::random_device{}());
  std::uniform_int_distribution<int> int_dist(intval_begin, intval_end);

  for (int i = 0; i < howmany; ++i) {
    vec.push_back(int_dist(rnd_generator));
  }
}

void print_vector(const std::vector<int>& vec) {
  for (const int& element : vec) { std::cout << element << ' '; }
  std::cout.put('\n');
}

bool is_even(const int& p_element) {
  return p_element % 2 == 0;
}

void even_odd_sort(std::vector<int>& vec){
  int low = 0;
  int high = vec.size()-1;
  int mid = vec[0];

  while (low < high){
    while (low < high && !is_even(vec[high])) {
      --high;
    }

    if (low < high) {
      vec[low] = vec[high];
      ++low;
    }

    while (low < high && is_even(vec[low])){
      ++low;
    }

    if (low < high){
      vec[high] = vec[low];
      --high;
    }
  }
  vec[low] = mid;
}

int main() {
  std::vector<int> stdvec_example1;

  const int howmany = 10;
  generate_rnd_number(stdvec_example1, howmany, 1, 100);

  std::cout << "Elements before sorting:\n";
  print_vector(stdvec_example1);

  even_odd_sort(stdvec_example1);

  std::cout << "Elements after sorting:\n";
  print_vector(stdvec_example1);
}

Összefésülés

Két rendezett tömb elemeit átmásoljuk egy harmadik tömbbe, a rendezettséget megőrízve.

Először két tömbön haladunk egy ciklussal addig amíg az egyik tömb végére nem érünk. Eközben amelyik tömbben van éppen kisebb elem, azt másoljuk át a harmadik tömbbe, és növeljük az annak megfelelő ciklusváltozót. Ha esetleg az elemek egyenlőek (ebben a példában ilyen eset nem fordul elő), akkor mindkét ciklusváltozót növeljük.

Ezt követően ha az egyik tömb feldolgozása még nem ért véget, akkor a fennmaradó elemeket átmásoljuk a harmadik tömbbe.

#include <iostream>
#include <vector>

int main() {
  std::vector<int> even = {2,4,6,8,10,12,14,16};
  std::vector<int> odd = {1,3,5,7,9,11,13};
  std::vector<int> output;

  int i = 0, j = 0;
  for (; i < even.size() && j < odd.size();) {
    if (even[i] < odd[j]) {
      output.push_back(even[i]);
      ++i;
    } else if (odd[j] < even[i]) {
      output.push_back(odd[j]);
      ++j;
    } else if (even[i] == odd[j]) {
      output.push_back(even[i]);
      ++i; ++j;
    }
  }

  for (; i < even.size(); ++i) {
    output.push_back(even[i]);
  }

  for (; j < odd.size(); ++j) {
    output.push_back(odd[j]);
  }

  for (const int& element : output) {
    std::cout << element << " ";
  }std::cout.put('\n');
}

Buborékrendezés

//bubble sort
#include <iostream>
#include <random>
#include <vector>

int main() {
  std::vector<int> stdvec_example = {9,6,11,3,1,7,8,-2};

  for (int i = stdvec_example.size()-1; i >= 0; --i) {
    for (int j = 0; j < i; ++j) {
      if (stdvec_example[j] > stdvec_example[j+1]) {
        int temp = stdvec_example[j];
        stdvec_example[j] = stdvec_example[j+1];
        stdvec_example[j+1] = temp;
      }
    }
  }

  for (const int& element : stdvec_example) {
    std::cout << element << ' ';
  }
  std::cout.put('\n');
}

Egyéb tananyagok

előző tananyagrész: STL

A bejegyzés trackback címe:

https://itkezdoknek.blog.hu/api/trackback/id/tr7717798349

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

Nincsenek hozzászólások.
süti beállítások módosítása