Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <chrono>
- #include <vector>
- using namespace std;
- struct Nodo {
- string dato = "";
- Nodo *next = nullptr;
- };
- void ins_testa(Nodo *&il, Nodo *nuovo)
- {
- nuovo->next = il;
- il = nuovo;
- }
- void ins_coda(Nodo *&il, Nodo *nuovo)
- {
- if (il == nullptr) //lista vuota ?
- {
- nuovo->next = il;
- il = nuovo;
- }
- else
- {
- Nodo *ultimo = il;
- //otteniamo un puntatore all'ultimo nodo attuale
- while(ultimo->next != nullptr) ultimo = ultimo->next;
- ultimo->next = nuovo;
- nuovo->next = nullptr;
- }
- }
- void stampa_dalla_coda(Nodo *p, int profondita, int &massima)
- {
- massima = max(profondita, massima);
- if (p!=nullptr)
- stampa_dalla_coda(p->next, profondita+1, massima);
- }
- //Equazione di ricorrenza temporale: T(n) = 2*T(n/2) + O(n)
- //Equazione di ricorrenza spaziale: T(n) = T(n/2) + O(1)
- //Complessità temporale: O(nlog(n))
- //Complessità spaziale: O(log(n))
- void stampaInvertita(Nodo *testa,int dim){
- //Casi base
- //Lista vuota
- if (testa == nullptr)
- return;
- //Lista con un solo elemento
- if (testa->next == nullptr)
- ;//cout << testa->dato << endl;
- //Passo ricorsivo
- else{
- Nodo* attuale = testa;
- //Suddivido in due metà la lista
- for (int i = 0; i < dim/2 - 1; ++i) {
- attuale = attuale->next;
- }
- //Mi fermo all'ultimo elemento della prima metà
- //ed imposto il puntatore al successivo a nullptr, così da avere due liste fisicamente separate
- Nodo* temp = attuale;
- attuale = attuale->next;
- temp->next = nullptr;
- //Ora richiedo la stampa della seconda metà seguita dalla prima; l'ordine delle chiamate è fondamentale
- stampaInvertita(attuale, dim/2);
- stampaInvertita(testa, dim - dim/2);
- //Dopo la stampa non resta che ricongiungere le due liste precedentemente divise
- temp->next = attuale;
- }
- }
- //credits Alex-qk5ei (youtube)
- int stampaInvertitaMisuraStack(Nodo *testa, int dim){
- //Casi base
- //Lista vuota
- if (testa == nullptr)
- return 1;
- //Lista con un solo elemento
- if (testa->next == nullptr) {
- ;//cout << testa->dato << endl;
- return 1;
- }
- //Passo ricorsivo
- else{
- Nodo* attuale = testa;
- // 00010010 18
- //
- //Suddivido in due metà la lista
- for (int i = 0; i < (dim>>1) - 1; ++i) {
- attuale = attuale->next;
- }
- //Mi fermo all'ultimo elemento della prima metà
- //ed imposto il puntatore al successivo a nullptr, così da avere due liste fisicamente separate
- Nodo* temp = attuale;
- attuale = attuale->next;
- temp->next = nullptr;
- /*La profondità massima dello stack P(n) può essere definita ricorsivamente come: P(n) = max(P(n/2), P(n-n/2)) + 1
- L'addendo 1 equivale alla presenza sullo stack del record di attivazione corrente
- 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
- P(n) = P(n-n/2) + 1
- L'istruzione sottostante rappresenta dunque la profondità massima che andrà restituita al metodo chiamante
- */
- //Ora richiedo la stampa della seconda metà seguita dalla prima; l'ordine delle chiamate è fondamentale
- int profondita = stampaInvertitaMisuraStack(attuale, dim - (dim>>1)) + 1;
- stampaInvertitaMisuraStack(testa, dim>>1);
- //Dopo la stampa non resta che ricongiungere le due liste precedentemente divise
- temp->next = attuale;
- return profondita;
- }
- }
- enum Comando {START, STOP};
- auto Cronometro(Comando comando = Comando::START)
- {
- static std::chrono::time_point<std::chrono::system_clock> inizio;
- static std::chrono::time_point<std::chrono::system_clock> fine;
- if (comando == Comando::START)
- {
- inizio = chrono::high_resolution_clock::now();
- fine = inizio;
- }
- else
- fine = chrono::high_resolution_clock::now();
- return chrono::duration_cast<std::chrono::milliseconds>(fine - inizio).count();
- }
- void stampaInvertitaVector(Nodo *il)
- {
- vector<Nodo*> v;
- while(il!=nullptr)
- {
- v.push_back(il);
- il = il-> next;
- }
- for (int i=v.size()-1; i>=0; i--);
- //cout << v[i] -> dato << " ";
- }
- void stampa(Nodo *p)
- {
- while (p!=nullptr)
- {
- //cout << p->dato << " ";
- //al prossimo nodo
- p = p->next;
- }
- }
- // Struttura per rappresentare una "mossa"
- struct HanoiMove {
- int n; // Numero di dischi
- char from; // Piolo di partenza (A, B, C)
- char to; // Piolo di destinazione
- char aux; // Piolo ausiliario
- };
- // Versione iterativa senza STL (stack manuale)
- void hanoi_iterative_no_stl(int n, char from = 'A', char to = 'C', char aux = 'B') {
- const int MAX_STACK_SIZE = 1000; // Dimensione massima dello stack
- HanoiMove stack[MAX_STACK_SIZE];
- int top = -1; // Inizializza lo stack vuoto
- // Simula la prima chiamata ricorsiva
- stack[++top] = {n, from, to, aux};
- while (top >= 0) { // Finché lo stack non è vuoto
- HanoiMove current = stack[top--]; // Pop
- if (current.n == 1) {
- // Caso base: sposta il disco
- cout << "Muovi disco 1 da " << current.from << " a " << current.to << endl;
- } else {
- // Simula le chiamate ricorsive in ordine inverso (LIFO)
- // 1. hanoi(n-1, aux, to, from)
- stack[++top] = {current.n - 1, current.aux, current.to, current.from};
- // 2. Sposta il disco n da from a to (caso base fittizio)
- stack[++top] = {1, current.from, current.to, current.aux};
- // 3. hanoi(n-1, from, aux, to)
- stack[++top] = {current.n - 1, current.from, current.aux, current.to};
- }
- }
- }
- //versione ricorsiva
- void hanoi(int n, char from = 'A', char to = 'C', char aux = 'B') {
- if (n == 1) {
- cout << "Muovi disco 1 da " << from << " a " << to << endl;
- return;
- }
- hanoi(n - 1, from, aux, to); // Sposta n-1 dischi da 'from' a 'aux'
- cout << "Muovi disco " << n << " da " << from << " a " << to << endl;
- hanoi(n - 1, aux, to, from); // Sposta n-1 dischi da 'aux' a 'to'
- }
- int main()
- {
- string dati_prova[] = {"abaco", "amo", "bicicletta", "cane", "canguro", "mare", "sale", "zebra"};
- Nodo *il = nullptr;
- int quante_run=5;
- int num_ele = 50000;
- for (int i=0; i<num_ele; i++)
- ins_coda(il, new Nodo{dati_prova[i%8]});
- //stampaInvertitaVector(il);
- Cronometro(Comando::START);
- for (int run=0; run<quante_run; run++)
- stampaInvertita(il,num_ele);
- cout << "Ricorsione con divide/impera: " << Cronometro(Comando::STOP) << endl;
- Cronometro(Comando::START);
- for (int run=0; run<quante_run; run++)
- stampaInvertitaVector(il);
- cout << "Iterativa con vector di puntatori: " << Cronometro(Comando::STOP) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement