Domy131097

[LV3] Algoritmi - Rekurzije i stog

Apr 10th, 2018
98
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <time.h>
  6.  
  7.  
  8. #define N 100;
  9.  
  10. typedef struct stog {
  11.     int Sp = -1;
  12.     int V[1000];
  13. }Stog;
  14.  
  15. typedef struct stog_PP {
  16.     int x;
  17.     struct stog_PP *sljedeci;
  18. }Stog_PP;
  19.  
  20. Stog_PP *zadnji = NULL;
  21.  
  22. int povrh_Rek(int, int);
  23. int povrh_Stog(Stog*, Stog*, int, int);
  24. int povrh_Stog_PP(int, int);
  25. //Stog - niz
  26. int IsEmpty(Stog*);
  27. int IsFull(Stog*);
  28. int Pop(Stog*);
  29. void Push(Stog*, int);
  30. void Clear(Stog*);
  31. //Stog - povezani popis
  32. int IsEmpty_PP();
  33. void Push_PP(int);
  34. int Pop_PP();
  35. void Clear_PP();
  36.  
  37. int main() {
  38.     int n, m, rez;
  39.     time_t t;
  40.     Stog *s1 = (Stog *)malloc(sizeof(Stog)), *s2 = (Stog *)malloc(sizeof(Stog));
  41.     printf("Unesite broj n:\n");
  42.     scanf("%d", &n);
  43.     m = n / 2;
  44.     t = clock();
  45.     rez = povrh_Rek(n, m);
  46.     t = clock() - t;
  47.     printf("Povrh rekurzijom: REZ: %d | VRIJEME: %dms\n", rez, t);
  48.     t = clock();
  49.     rez = povrh_Stog(s1, s2, n, m);
  50.     t = clock() - t;
  51.     printf("Povrh stogom - niz: REZ: %d | VRIJEME: %dms\n", rez, t);
  52.     t = clock();
  53.     rez = povrh_Stog_PP(n, m);
  54.     t = clock() - t;
  55.     printf("Povrh stogom - povezani popis: REZ: %d | VRIJEME: %dms\n", rez, t);
  56. }
  57.  
  58. /*===== POVRH (rekurzivna) =====*/
  59. int povrh_Rek(int n, int m)
  60. {
  61.     if (m == n || n == 1 || m == 0) return 1;
  62.     return povrh_Rek(n - 1, m - 1) + povrh_Rek(n - 1, m);
  63. }
  64.  
  65. /*===== POVRH (stog - niz) =====*/
  66. int povrh_Stog(Stog *s1, Stog *s2, int a, int b)
  67. {
  68.     int n, m;
  69.     Clear(s1);
  70.     Clear(s2);
  71.     Push(s1, a);
  72.     Push(s2, b);
  73.     int povrh = 0;
  74.    
  75.     do {
  76.         n = Pop(s1);
  77.         m = Pop(s2);
  78.         if (m == n || n == 1 || m == 0) povrh++;
  79.         else {
  80.             Push(s1, n - 1);
  81.             Push(s2, m - 1);
  82.             Push(s1, n - 1);
  83.             Push(s2, m);
  84.         }
  85.     } while (IsEmpty(s1) == 0);
  86.     return povrh;
  87. }
  88. /*===== POVRH (stog - povezani popis) =====*/
  89. int povrh_Stog_PP(int a, int b)
  90. {
  91.     int n, m;
  92.     Clear_PP;
  93.     Push_PP(a);
  94.     Push_PP(b);
  95.     int povrh = 0;
  96.     do {
  97.         m = Pop_PP();
  98.         n = Pop_PP();
  99.         if (m == n || n == 1 || m == 0) povrh = povrh + 1;
  100.         else {
  101.             Push_PP(n - 1);
  102.             Push_PP(m - 1);
  103.             Push_PP(n - 1);
  104.             Push_PP(m);
  105.         }
  106.     } while (IsEmpty_PP() == 0);
  107.     return povrh;
  108. }
  109.  
  110. /*===== STOG (niz) =====*/
  111. int IsEmpty(Stog *s) {
  112.     if (s->Sp == -1) return 1;
  113.     else return 0;
  114. }
  115.  
  116. int IsFull(Stog *s) {
  117.     if (s->Sp == 999) return 1;
  118.     else return 0;
  119. }
  120.  
  121. int Pop(Stog *s) {
  122.     if (IsEmpty(s)) {
  123.         printf("PREKID!\n");
  124.         return -1;
  125.     }
  126.     s->Sp--;
  127.     return s->V[s->Sp + 1];
  128.  
  129. }
  130.  
  131. void Push(Stog *s, int x) {
  132.     if (IsFull(s)) {
  133.         printf("PREKID!\n");
  134.         return;
  135.     }
  136.     s->Sp++;
  137.     s->V[s->Sp] = x;
  138. }
  139.  
  140. void Clear(Stog *s) {
  141.     s->Sp = -1;
  142. }
  143.  
  144. /*===== STOG (povezani popis) =====*/
  145. int IsEmpty_PP() {
  146.     if (zadnji == NULL) return 1;
  147.     else return 0;
  148. }
  149.  
  150. int Pop_PP() {
  151.     int x;
  152.     if (IsEmpty_PP()) {
  153.         printf("PREKID!\n");
  154.         return -1;
  155.     }
  156.     x = zadnji->x;
  157.     Stog_PP *temp = (Stog_PP *)malloc(sizeof(Stog_PP));
  158.     temp = zadnji;
  159.     zadnji = zadnji->sljedeci;
  160.     free(temp);
  161.     return x;
  162.  
  163. }
  164.  
  165. void Push_PP(int x) {
  166.     Stog_PP *novi = (Stog_PP *)malloc(sizeof(Stog_PP));
  167.     novi->x = x;
  168.     novi->sljedeci = zadnji;
  169.     zadnji = novi;
  170. }
  171.  
  172. void Clear_PP() {
  173.     while (IsEmpty_PP == 0) {
  174.         Pop_PP();
  175.     }
  176. }
RAW Paste Data Copied