Advertisement
fcamuso

Pillole video 6

Apr 1st, 2025
930
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 7.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <chrono>
  3. #include <vector>
  4.  
  5.  
  6. using namespace std;
  7.  
  8. struct Nodo {
  9.   string dato = "";
  10.  
  11.   Nodo *next = nullptr;
  12. };
  13.  
  14.  
  15.  
  16. void ins_testa(Nodo *&il, Nodo *nuovo)
  17. {
  18.     nuovo->next = il;
  19.     il = nuovo;
  20. }
  21.  
  22.  
  23.  
  24. void ins_coda(Nodo *&il, Nodo *nuovo)
  25. {
  26.   if (il == nullptr) //lista vuota ?
  27.   {
  28.     nuovo->next = il;
  29.     il = nuovo;
  30.   }
  31.   else
  32.   {
  33.     Nodo *ultimo = il;
  34.  
  35.     //otteniamo un puntatore all'ultimo nodo attuale
  36.     while(ultimo->next != nullptr) ultimo = ultimo->next;
  37.  
  38.     ultimo->next = nuovo;
  39.     nuovo->next = nullptr;
  40.   }
  41. }
  42.  
  43. void stampa_dalla_coda(Nodo *p, int profondita, int &massima)
  44. {
  45.   massima = max(profondita, massima);
  46.  
  47.   if (p!=nullptr)
  48.     stampa_dalla_coda(p->next, profondita+1, massima);
  49. }
  50.  
  51.  
  52. //Equazione di ricorrenza temporale: T(n) = 2*T(n/2) + O(n)
  53. //Equazione di ricorrenza spaziale: T(n) = T(n/2) + O(1)
  54. //Complessità temporale: O(nlog(n))
  55. //Complessità spaziale: O(log(n))
  56. void stampaInvertita(Nodo *testa,int  dim){
  57.  
  58.     //Casi base
  59.     //Lista vuota
  60.     if (testa == nullptr)
  61.         return;
  62.     //Lista con un solo elemento
  63.     if (testa->next == nullptr)
  64.         ;//cout << testa->dato << endl;
  65.         //Passo ricorsivo
  66.     else{
  67.         Nodo* attuale = testa;
  68.         //Suddivido in due metà la lista
  69.         for (int i = 0; i < dim/2 - 1; ++i) {
  70.             attuale = attuale->next;
  71.         }
  72.         //Mi fermo all'ultimo elemento della prima metà
  73.         //ed imposto il puntatore al successivo a nullptr, così da avere due liste fisicamente separate
  74.         Nodo* temp = attuale;
  75.         attuale = attuale->next;
  76.         temp->next = nullptr;
  77.  
  78.         //Ora richiedo la stampa della seconda metà seguita dalla prima; l'ordine delle chiamate è fondamentale
  79.         stampaInvertita(attuale, dim/2);
  80.         stampaInvertita(testa, dim - dim/2);
  81.  
  82.         //Dopo la stampa non resta che ricongiungere le due liste precedentemente divise
  83.         temp->next = attuale;
  84.     }
  85. }
  86.  
  87. //credits Alex-qk5ei (youtube)
  88. int stampaInvertitaMisuraStack(Nodo *testa, int dim){
  89.  
  90.     //Casi base
  91.     //Lista vuota
  92.     if (testa == nullptr)
  93.         return 1;
  94.     //Lista con un solo elemento
  95.     if (testa->next == nullptr) {
  96.         ;//cout << testa->dato << endl;
  97.         return 1;
  98.     }
  99.     //Passo ricorsivo
  100.     else{
  101.         Nodo* attuale = testa;
  102.  
  103.         // 00010010 18
  104.         //
  105.  
  106.  
  107.         //Suddivido in due metà la lista
  108.         for (int i = 0; i < (dim>>1) - 1; ++i) {
  109.             attuale = attuale->next;
  110.         }
  111.         //Mi fermo all'ultimo elemento della prima metà
  112.         //ed imposto il puntatore al successivo a nullptr, così da avere due liste fisicamente separate
  113.         Nodo* temp = attuale;
  114.         attuale = attuale->next;
  115.         temp->next = nullptr;
  116.  
  117.         /*La profondità massima dello stack P(n) può essere definita ricorsivamente come: P(n) = max(P(n/2), P(n-n/2)) + 1
  118.         L'addendo 1 equivale alla presenza sullo stack del record di attivazione corrente
  119.         Inoltre, considerando che n-n/2 >= n/2 in ogni caso, max(P(n/2), P(n-n/2)) = P(n-n/2) e, conseguentemente
  120.         P(n) = P(n-n/2) + 1
  121.         L'istruzione sottostante rappresenta dunque la profondità massima che andrà restituita al metodo chiamante
  122.         */
  123.         //Ora richiedo la stampa della seconda metà seguita dalla prima; l'ordine delle chiamate è fondamentale
  124.         int profondita = stampaInvertitaMisuraStack(attuale, dim - (dim>>1)) + 1;
  125.         stampaInvertitaMisuraStack(testa, dim>>1);
  126.         //Dopo la stampa non resta che ricongiungere le due liste precedentemente divise
  127.         temp->next = attuale;
  128.  
  129.         return profondita;
  130.     }
  131. }
  132.  
  133.  
  134. enum Comando {START, STOP};
  135. auto Cronometro(Comando comando = Comando::START)
  136. {
  137.   static std::chrono::time_point<std::chrono::system_clock> inizio;
  138.   static std::chrono::time_point<std::chrono::system_clock> fine;
  139.  
  140.   if (comando == Comando::START)
  141.   {
  142.     inizio = chrono::high_resolution_clock::now();
  143.     fine = inizio;
  144.   }
  145.   else
  146.     fine = chrono::high_resolution_clock::now();
  147.  
  148.  
  149.   return chrono::duration_cast<std::chrono::milliseconds>(fine - inizio).count();
  150. }
  151.  
  152.  
  153. void stampaInvertitaVector(Nodo *il)
  154. {
  155.   vector<Nodo*> v;
  156.  
  157.   while(il!=nullptr)
  158.   {
  159.     v.push_back(il);
  160.     il = il-> next;
  161.   }
  162.  
  163.   for (int i=v.size()-1; i>=0; i--);
  164.     //cout << v[i] -> dato << " ";
  165. }
  166.  
  167. void stampa(Nodo *p)
  168. {
  169.   while (p!=nullptr)
  170.   {
  171.     //cout << p->dato << " ";
  172.  
  173.     //al prossimo nodo
  174.     p = p->next;
  175.   }
  176. }
  177.  
  178. // Struttura per rappresentare una "mossa"
  179. struct HanoiMove {
  180.     int n;          // Numero di dischi
  181.     char from;      // Piolo di partenza (A, B, C)
  182.     char to;        // Piolo di destinazione
  183.     char aux;       // Piolo ausiliario
  184. };
  185.  
  186. // Versione iterativa senza STL (stack manuale)
  187. void hanoi_iterative_no_stl(int n, char from = 'A', char to = 'C', char aux = 'B') {
  188.     const int MAX_STACK_SIZE = 1000; // Dimensione massima dello stack
  189.     HanoiMove stack[MAX_STACK_SIZE];
  190.     int top = -1; // Inizializza lo stack vuoto
  191.  
  192.     // Simula la prima chiamata ricorsiva
  193.     stack[++top] = {n, from, to, aux};
  194.  
  195.     while (top >= 0) { // Finché lo stack non è vuoto
  196.         HanoiMove current = stack[top--]; // Pop
  197.  
  198.         if (current.n == 1) {
  199.             // Caso base: sposta il disco
  200.             cout << "Muovi disco 1 da " << current.from << " a " << current.to << endl;
  201.         } else {
  202.             // Simula le chiamate ricorsive in ordine inverso (LIFO)
  203.             // 1. hanoi(n-1, aux, to, from)
  204.             stack[++top] = {current.n - 1, current.aux, current.to, current.from};
  205.             // 2. Sposta il disco n da from a to (caso base fittizio)
  206.             stack[++top] = {1, current.from, current.to, current.aux};
  207.             // 3. hanoi(n-1, from, aux, to)
  208.             stack[++top] = {current.n - 1, current.from, current.aux, current.to};
  209.         }
  210.     }
  211. }
  212.  
  213. //versione ricorsiva
  214. void hanoi(int n, char from = 'A', char to = 'C', char aux = 'B') {
  215.     if (n == 1) {
  216.         cout << "Muovi disco 1 da " << from << " a " << to << endl;
  217.         return;
  218.     }
  219.     hanoi(n - 1, from, aux, to);  // Sposta n-1 dischi da 'from' a 'aux'
  220.     cout << "Muovi disco " << n << " da " << from << " a " << to << endl;
  221.     hanoi(n - 1, aux, to, from);  // Sposta n-1 dischi da 'aux' a 'to'
  222. }
  223.  
  224. int main()
  225. {
  226.     string dati_prova[] = {"abaco", "amo", "bicicletta", "cane", "canguro", "mare", "sale", "zebra"};
  227.  
  228.     Nodo *il = nullptr;
  229.  
  230.     int quante_run=5;
  231.     int num_ele = 50000;
  232.  
  233.     for (int i=0; i<num_ele; i++)
  234.       ins_coda(il, new Nodo{dati_prova[i%8]});
  235.  
  236.     //stampaInvertitaVector(il);
  237.  
  238.     Cronometro(Comando::START);
  239.     for (int run=0; run<quante_run; run++)
  240.           stampaInvertita(il,num_ele);
  241.     cout << "Ricorsione con divide/impera: " << Cronometro(Comando::STOP) << endl;
  242.  
  243.  
  244.     Cronometro(Comando::START);
  245.     for (int run=0; run<quante_run; run++)
  246.           stampaInvertitaVector(il);
  247.     cout << "Iterativa con vector di puntatori: " << Cronometro(Comando::STOP) << endl;
  248.  
  249.     return 0;
  250. }
  251.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement