kburnik

C++ - Zadatak Tjelesni

Jan 26th, 2013
102
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3. ZRS - C++ radionica
  4.  
  5. TEMA : Dvostruko povezana cirkularna lista
  6.  
  7. Zadatak: Tjelesni
  8.  
  9. Autor: Kristijan Burnik, udruga informaticara Bozo Tezak
  10.  
  11. */
  12. #include <iostream>
  13. #include <cstdlib>
  14. #include <vector>
  15.  
  16. using namespace std;
  17.  
  18. // cvor u dvostrukoj povezanoj listi
  19. typedef struct node {
  20.         int index;
  21.         node * prev;
  22.         node * next;
  23.  
  24.         node() {
  25.             next = NULL;    
  26.             prev = NULL;
  27.         }
  28.        
  29.         node(int _index) {
  30.             index = _index;
  31.             next = NULL;
  32.             prev = NULL;    
  33.         }
  34. } node;
  35.  
  36. // ovdje cemo pohraniti cvorove (alocirati memoriju)
  37. vector<node> v;
  38.  
  39. int main() {
  40.    
  41.     int n,p;
  42.    
  43.     // unosimo ulazne podatke
  44.     cin >> n >> p;
  45.    
  46.     // pripremi memoriju za cvorove
  47.     v.resize(n);
  48.    
  49.     // stvori prvi cvor
  50.     v[0] = node(1);
  51.    
  52.     // stvori sve ostale cvorove i povezi ih
  53.     for (int i = 1; i < n ; i++) {
  54.         // popuni cvor sa index = i + 1
  55.         v[i] = node(i+1);
  56.        
  57.         // sljedeci od prethodnog je trenutni
  58.         v[i-1].next = &v[i];
  59.        
  60.         // prethodni od trenutnog
  61.         v[i].prev = &v[i-1];
  62.     }
  63.    
  64.     // uzmi reference na prvi i zadnji cvor u krugu
  65.     node * prvi = &v[0];
  66.     node * zadnji = &v[n-1];
  67.    
  68.     // povezi prvi cvor sa zadnjim u listi (zaokruzi listu)
  69.     // lista je od ovog koraka cirkularna!
  70.     zadnji->next = prvi;
  71.     prvi->prev = zadnji;
  72.  
  73.    
  74.  
  75.     int steps = 0 ;
  76.  
  77.     // putujemo redom po svim stolcima ukrug dok je broj stolaca veci od P
  78.     for ( node * t = prvi ; n > p ; t = t->next ) {
  79.        
  80.         // ako je p-ti korak i ako nismo na 1. stolcu, uklanjamo ga
  81.         if ( (steps % p) == 0 && t->index != 1) {
  82.                 // cvor a je prethodni od trenutnog
  83.                 // cvor b je sljedeci od trenutnog                
  84.                 node * a, *c;
  85.                 a = t->prev;                
  86.                 c = t->next;
  87.                
  88.                 // jednostavno "preskacemo" trenutni cvor
  89.                 a->next = c;
  90.                 c->prev = a;
  91.                
  92.                 // smanjujemo broj stolaca
  93.                 n--;
  94.                
  95.                 // ispisujemo koji stolac smo izbacili
  96.                 cout << t->index  << " ";
  97.         }
  98.        
  99.         // brojimo korake
  100.         steps++;
  101.     }
  102.  
  103.    
  104.    
  105.     cout << endl;
  106.    
  107.     // ispisi preostale stolce, njih P
  108.     int i = 0;
  109.     for ( node * t = prvi ; i < p ; t = t->next , i++ ) {
  110.          cout << t->index  << " ";
  111.          
  112.     }
  113.     cout << endl;
  114.    
  115.  
  116.     system("pause");
  117.     return 0;
  118. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×