API tools faq
paste
Sanady

Domaca4

Sanady
Oct 17th, 2019
271
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.59 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. Meno a priezvisko: Ivan Rener
  3.  
  4. POKYNY:
  5. (1)  Subor premenujte na Priezvisko_Meno_ID_du04.cpp (pouzite vase udaje bez diakritiky).
  6. (2)  Implementujte funkcie tak, aby splnali popis pri ich deklaraciach.
  7. (3)  Cela implementacia musi byt v tomto jednom subore.
  8. (4)  Odovzdajte len tento (spravne premenovany) zdrojovy subor.
  9. (5)  Program musi byt kompilovatelny.
  10. (6)  Globalne a staticke premenne su zakazane.
  11. (7)  V ziadnom pripade nemente deklaracie funkcii, ktore mate za ulohu naprogramovat
  12.      (nemente nazvy, navratove hodnoty ani typ a pocet parametrov v zadanych funkciach).
  13.      Nemente implementacie hotovych pomocnych funkcii, ani implementacie zadanych datovych typov.
  14. (8)  V pripade potreby mozete kod doplnit o dalsie pomocne funkcie alebo struktury.
  15. (9)  Vase riesenie otestujte (vo funkcii 'main' a pomocou doplnenych pomocnych funkcii alebo struktur).
  16.      Testovaci kod ale nebude hodnoteny.
  17. (10) Funkcia 'main' musi byt v zdrojovom kode posledna.
  18. */
  19.  
  20. #include <iostream>
  21. #include <cstdlib>
  22. using namespace std;
  23.  
  24. //-------------------------------------------------------------------------------------------------
  25. // DATOVE TYPY
  26. //-------------------------------------------------------------------------------------------------
  27.  
  28. // Hmotnost produktu a obalu. Hmotnost zabaleneho produktu je suctom obidvoch poloziek
  29. struct Weight {
  30.     int product; // hmotnost produktu
  31.     int packing; // hmotnost balenia
  32. };
  33.  
  34. //-------------------------------------------------------------------------------------------------
  35. // ULOHA (0.2 boda)
  36. //-------------------------------------------------------------------------------------------------
  37. /*
  38.     Usporiada pole 'data'.
  39.     Pouzije algoritmus bubble sort.
  40.     Poradie usporiadania je od najvacsieho prvku po najmensi.
  41.  
  42.     PARAMETRE:
  43.         [in, out] data - pole, ktore funkcia usporiada
  44.         [in] length - pocet prvkov pola
  45.  
  46.     VSTUPNA PODMIENKA:
  47.         ak 'length' > 0, tak 'data' ukazuje na platne pole
  48.  
  49.     PRIKLADY:
  50.         {1,3,2} -> {3, 2, 1}
  51.         {} -> {}
  52. */
  53.  
  54. void swap(int* a, int* b)
  55. {
  56.     int tmp = *a;
  57.     *a = *b;
  58.     *b = tmp;
  59. }
  60.  
  61. void bubbleSort(int* data, const size_t length) {
  62.     for (int i = 0; i < length - 1; i++)
  63.     {
  64.         for (int j = 0; j < length - 1 - i; j++)
  65.         {
  66.             if (data[j] < data[j + 1])
  67.             {
  68.                 swap(data + j, data + j + 1); //pointer aritmetics
  69.             }
  70.         }
  71.     }
  72. }
  73.  
  74. //-------------------------------------------------------------------------------------------------
  75. // ULOHA (0.2 boda)
  76. //-------------------------------------------------------------------------------------------------
  77. /*
  78.     Usporiada pole 'data' podla celkovej hmotnosti zabaleneho tovaru, t.j. podla suctu poloziek (product a packing).
  79.     Pouzije algoritmus bubble sort.
  80.     Poradie usporiadania je od najvacsieho prvku po najmensi.
  81.  
  82.     Podmienka porovnania struktur:
  83.     Pri porovnavani prvkov funkcia scita hodnoty product a packing oboch porovnavanych struktur.
  84.     Struktury s vacsim suctom poloziek budu po usporiadani pred strukturami s mensim suctom poloziek.
  85.  
  86.     Vzajomne usporiadanie struktur s rovnakym suctom poloziek:
  87.     Pri bodovom hodnoteni nezalezi na vzajomnom usporiadani struktur s rovnakym suctom poloziek (aj ked hodnoty poloziek mozu byt rozne).
  88.     Lepsie je vsak implementovat stabilne triedenie (struktury s rovnakym suctom poloziek nemenia vzajomne usporiadanie).
  89.  
  90.     PARAMETRE:
  91.         [in, out] data - pole, ktore funkcia usporiada
  92.         [in] length - pocet prvkov pola
  93.  
  94.     VSTUPNA PODMIENKA:
  95.         ak 'length' > 0, tak 'data' ukazuje na platne pole
  96.  
  97.     PRIKLADY:
  98.         {{10, 1}, {20, 2}, {5,2}} -> {{20, 2}, {10, 1},{5,2}} pretoze 20+2=22, 10+1=11, 5+2=7 a 22 > 11 > 7
  99.         {} -> {}
  100.  
  101.     POZNAMKA:
  102.         Priklady jednoducheho vytvorenia pola v testovacom kode:
  103.         Weight baliky[] = {{10, 1}, {20, 2}, {5,2}};
  104.         Weight baliky[] = {{.product = 10, .packing = 1}, {.product = 20, .packing = 2}, {.product = 5, .packing = 2}};
  105. */
  106.  
  107. void bubbleSort(Weight* data, const size_t length) {
  108.     int tmp, tmp1;
  109.     for (int i = 0; i < length - 1; i++)
  110.     {
  111.         for (int j = 0; j < length - 1 - i; j++)
  112.         {
  113.             tmp = data[j].product + data[j].packing;
  114.             tmp1 = data[j + 1].product + data[j + 1].packing;
  115.             if (tmp < tmp1)
  116.             {
  117.                 swap(data[j], data[j + 1]); //pointer aritmetics
  118.             }
  119.         }
  120.     }
  121. }
  122.  
  123. //-------------------------------------------------------------------------------------------------
  124. // ULOHA (0.2 boda)
  125. //-------------------------------------------------------------------------------------------------
  126. /*
  127.     Vyberie pivota a vrati jeho index.
  128.     Pivota vyberie ako median prvkov:
  129.       - data[low]
  130.       - data[(high+low)/2]
  131.       - data[high-1]
  132.  
  133.     PARAMETRE:
  134.         [in] 'data' - pole, v ktoreho casti s indexami low ... high-1, funkcia vybera pivot
  135.         [in] 'low'  - index prveho prvku casti pola, v ktorej funkcia hlada pivot
  136.         [in] 'high' - index za poslednym prvkom casti pola, v ktorej funkcia hlada pivot
  137.  
  138.     RETURN:
  139.         index pivota
  140.  
  141.     VSTUPNE PODMIENKY:
  142.         'data' ukazuje na platne pole
  143.         'low' < 'high'
  144.  
  145.     PRIKLADY:
  146.         data: {10, 20, 2000, 30, 1000, 40, 5000, 50, 60, 70}, low: 2, high: 7 -> return 2
  147.         data: {10, 20, 1000, 30, 2000, 40, 5000, 50, 60, 70}, low: 2, high: 7 -> return 4
  148.         data: {10, 20, 5000, 30, 1000, 40, 2000, 50, 60, 70}, low: 2, high: 7 -> return 6
  149.  
  150.         data: {10, 20, 1000, 30, 40, 2000, 50, 5000, 60, 70}, low: 2, high: 8 -> return 5
  151.  
  152.         data: {10, 20, 1000, 2000, 30, 40, 50},               low: 2, high: 4 -> return 3
  153.         data: {10, 20, 2000, 1000, 30, 40, 50},               low: 2, high: 4 -> return 3
  154.  
  155.         data: {10, 20, 1000, 30, 40},                         low: 2, high: 3 -> return 2
  156. */
  157. size_t getPivotIndex(const int* data, const size_t low, const size_t high)
  158. {
  159.     return data[rand() % (high - low) + low];
  160. }
  161.  
  162. //-------------------------------------------------------------------------------------------------
  163. // ULOHA (0.2 boda)
  164. //-------------------------------------------------------------------------------------------------
  165. /*
  166.     Vykona partition (cast algoritmu quick sort) a vrati novy index pivota.
  167.     Pouzije styl algoritmu Lomuto.
  168.     Poradie usporiadania:
  169.         Najprv (vlavo) budu prvky vacsie alebo rovne ako pivot,
  170.         potom pivot,
  171.         potom (vpravo) prvky mensie ako pivot.
  172.  
  173.     PARAMETRE:
  174.         [in, out] 'data' - pole, v ktoreho casti 'low' ... 'high'-1 bude vykonane partition
  175.         [in] 'pivot' - index pivota (pred partition)
  176.         [in] 'low'   - index prveho prvku casti pola, v ktorej bude vykonany partition
  177.         [in] 'high'  - index za poslednym prvkom casti pola, v ktorej bude vykonany partition
  178.  
  179.     RETURN:
  180.         Index pivota po vykonani partition.
  181.  
  182.     VSTUPNE PODMIENKY:
  183.         'low' <= 'pivot' < 'high'
  184.         (index pivota moze byt lubobolny v rozsahu 'low'...'high'-1, napriklad v pripade nahodneho vyberu)
  185.         'data' ukazuje na platne pole
  186.  
  187.     PRIKLADY:
  188.         1. priklad:
  189.             vstup:  data: {10, 20, 30, 40, 50, 60, 70, 80, 90}, pivot: 5, low: 2, high: 7
  190.             vystup: data: {10, 20, 70, 60, 50, 30, 40, 80, 90}, return 3
  191.  
  192.         2. priklad:
  193.             vstup:  data: {10, 20, 30, 40, 50, 60, 70, 50, 80, 90}, pivot: 4, low: 2, high: 8
  194.             vystup: data: {10, 20, 50, 60, 70, 50, 30, 40, 80, 90}, return 5
  195. */
  196. size_t partition(int* data, const size_t pivot, const size_t low, const size_t high)
  197. {
  198.     swap(&data[pivot], data + high - 1); // data+pivot_index
  199.     int insert_i = low;
  200.     for (int i = low; i < high - 1; i++) {
  201.         if (data[i] < data[high - 1]) {
  202.             swap(data + insert_i, data + i);
  203.             insert_i++;
  204.         }
  205.     }
  206.     swap(data + insert_i, data + high - 1);
  207.     return insert_i;
  208. }
  209.  
  210. //-------------------------------------------------------------------------------------------------
  211. // ULOHA (0.2 boda)
  212. //-------------------------------------------------------------------------------------------------
  213. /*
  214.     Usporiada cast pola 'data' (s indexami 'low' ... 'high'-1)
  215.     Pouzije algoritmus quick sort, styl Lomuto.
  216.     Poradie usporiadania je od najvacsieho prvku po najmensi.
  217.  
  218.     PARAMETRE:
  219.         [in] 'data' - pole, ktoreho cast funkcia usporiada
  220.         [in] 'low'  - index prveho prvkou casti pola, ktoru funkcia usporiada
  221.         [in] 'high' - index za posledny prvok casti pola, ktoru funkcia usporiada
  222.  
  223.     VSTUPNA PODMIENKA:
  224.         ak 'low' < 'high', tak 'data' ukazuje na platne pole
  225.  
  226.     PRIKLAD:
  227.         data: {1, 2, 3, 4, 5, 6, 7, 8, 9}, low: 2, high: 7 -> data: {1, 2, 7, 6, 5, 4, 3, 8, 9}
  228. */
  229. void quickSort(int* data, const size_t low, const size_t high)
  230. {
  231.     if (low < high - 1)
  232.     {
  233.         int pivot_index = getPivotIndex(data, low, high);
  234.         pivot_index = partition(data, pivot_index, low, high); // vrati novi index  //hoare
  235.         quickSort(data, low, pivot_index);
  236.         quickSort(data, pivot_index + 1, high);
  237.     }
  238. }
  239.  
  240. //-------------------------------------------------------------------------------------------------
  241. // TESTOVANIE
  242. //-------------------------------------------------------------------------------------------------
  243.  
  244. // tu mozete doplnit pomocne funkcie a struktury
  245.  
  246. /*void bublepred(int* data, const int n) { //nebude data const lebo svapujem
  247.     for (int i = 0; i < n - 1; i++) {
  248.         for (int j = 0; j < n - 1 - i; j++) {
  249.             if (data[j] > data[j + 1]) {
  250.                 swap(data + j, data + j + 1); //pointer aritmetics
  251.             }
  252.         }
  253.     }
  254.  
  255. }*/
  256.  
  257. /*int getPivotIndex(int* data, int low, int high) {
  258.     return rand() % (high - low) + low;
  259. }*/
  260.  
  261. /*int partitionLomuto(int* data, const int pivot_index, const int low, const int high) {
  262.  
  263.     swap(&data[pivot_index], data + high - 1); // data+pivot_index
  264.     int insert_i = low;
  265.     for (int i = low; i < high - 1; i++) {
  266.         if (data[i] < data[high - 1]) {
  267.             swap(data + insert_i, data + i);
  268.             insert_i++;
  269.         }
  270.     }
  271.     swap(data + insert_i, data + high - 1);
  272.     return insert_i;
  273. }
  274. void quickpred(int* data, const int low, const int high) {// pretazujem funkciu quickpred
  275.     if (low < high - 1) {
  276.         int pivot_index = getPivotIndex(data, low, high);
  277.         pivot_index = partitionLomuto(data, pivot_index, low, high); // vrati novi index  //hoare
  278.         quickpred(data, low, pivot_index);
  279.         quickpred(data, pivot_index + 1, high);
  280.  
  281.     }
  282.  
  283. }
  284.  
  285. void quickpred(int* data, const int n) {
  286.     quickpred(data, 0, n);// o je low
  287.  
  288. }*/
  289.  
  290. void printArray(int* data, const int n) {
  291.     for (int i = 0; i < n; i++) {
  292.         cout << data[i] << ' ';
  293.     }
  294.     cout << endl;
  295.  
  296. }
  297.  
  298. void printData(Weight* data, const int n) {
  299.     for (int i = 0; i < n; i++) {
  300.         cout << data[i].packing << ' ' << data[i].product << '\n';
  301.     }
  302.     cout << endl;
  303.  
  304. }
  305.  
  306. #define ARRAY_SIZE(data) (sizeof(data)/sizeof(data[0]))
  307. int main() {
  308.     //int data[] = { -5,0,9,12,7,3 };
  309.     Weight data[] = { {10, 1}, {20, 2}, {5,2} };
  310.     //printArray(data, ARRAY_SIZE(data));
  311.     //bublepred(data,ARRAY_SIZE(data));
  312.     printData(data, ARRAY_SIZE(data));
  313.     bubbleSort(data, ARRAY_SIZE(data));
  314.     //quickpred(data, ARRAY_SIZE(data));
  315.     //printArray(data, ARRAY_SIZE(data));
  316.     // tu mozete doplnit testovaci kod
  317.     printData(data, ARRAY_SIZE(data));
  318.     return 0;
  319. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!