Pillole video 6

fcamuso

Apr 1st, 2025

929

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C# 7.02 KB | None | 0 0

raw download clone embed print report

#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;
}

Add Comment

Please, Sign In to add comment