|
|
|
In questo tutorial elencherò alcuni problemi intrattabili(con complessità superiore al polimoniale),gli algoritmi di ordinamento tipo bubble sort ci metteva un tempo polimoniale ed è trattabile,i problemi non polimoniali,invece non sono per niente efficienti e non si possono usare,cioè sono algoritmi proibiti a causa del loro tempo di esecuzione.
In imperium ne vedremo uno di questi algoritmi,ad esempio quello di indovinare una parola,e costruire un algoritmo in grado di farlo.
Cioè dobbiamo costruire un algoritmo in grado di costruire tutte le combinazioni,ed è:
CODICE int i,l,n=1;
int lunghezza_parola=4,tempo=0;
StrArray alfabeto;
str parola_da_indovinare = "B<7%";
str parola_analizzata;
alfabeto[0]="A";
alfabeto[1]="B";
alfabeto[2]="C";
alfabeto[3]="D";
alfabeto[4]="E";
alfabeto[5]="F";
alfabeto[6]="G";
alfabeto[7]="H";
alfabeto[8]="I";
alfabeto[9]="J";
alfabeto[10]="K";
alfabeto[11]="L";
alfabeto[12]="M";
alfabeto[13]="N";
alfabeto[14]="O";
alfabeto[15]="P";
alfabeto[16]="Q";
alfabeto[17]="R";
alfabeto[18]="S";
alfabeto[19]="T";
alfabeto[20]="U";
alfabeto[21]="V";
alfabeto[22]="W";
alfabeto[23]="X";
alfabeto[24]="Y";
alfabeto[25]="Z";
alfabeto[26]="a";
alfabeto[27]="b";
alfabeto[28]="c";
alfabeto[29]="d";
alfabeto[30]="e";
alfabeto[31]="f";
alfabeto[32]="g";
alfabeto[33]="h";
alfabeto[34]="i";
alfabeto[35]="j";
alfabeto[36]="k";
alfabeto[37]="l";
alfabeto[38]="m";
alfabeto[39]="n";
alfabeto[40]="o";
alfabeto[41]="p";
alfabeto[42]="q";
alfabeto[43]="r";
alfabeto[44]="s";
alfabeto[45]="t";
alfabeto[46]="u";
alfabeto[47]="v";
alfabeto[48]="w";
alfabeto[49]="x";
alfabeto[50]="y";
alfabeto[51]="z";
alfabeto[52]="0";
alfabeto[53]="1";
alfabeto[54]="2";
alfabeto[55]="3";
alfabeto[56]="4";
alfabeto[57]="5";
alfabeto[58]="6";
alfabeto[59]="7";
alfabeto[60]="8";
alfabeto[61]="9";
alfabeto[62]="_";
alfabeto[63]="+";
alfabeto[64]="-";
alfabeto[65]="*";
alfabeto[66]="/";
alfabeto[67]="!";
alfabeto[68]="£";
alfabeto[69]="$";
alfabeto[71]="%";
alfabeto[72]="&";
alfabeto[73]="(";
alfabeto[74]=")";
alfabeto[75]="=";
alfabeto[76]="^";
alfabeto[77]="?";
alfabeto[78]="[";
alfabeto[79]="]";
alfabeto[80]="{";
alfabeto[81]="}";
alfabeto[82]="à";
alfabeto[83]="è";
alfabeto[84]="ò";
alfabeto[85]="ù";
alfabeto[86]="@";
alfabeto[87]="#";
alfabeto[88]="ç";
alfabeto[89]="°";
alfabeto[90]="§";
alfabeto[91]="<";
alfabeto[92]=">";
alfabeto[93]=":";
alfabeto[94]=".";
alfabeto[95]=";";
alfabeto[96]="ì";
alfabeto[97]="'";
alfabeto[98]="•";
alfabeto[99]="|";
l=alfabeto.size();
for(i=0;i<lunghezza_parola;i+=1)
n=n*l;
pr("Numero combinazioni totali: " + n);
SetSpeed(50000);
tempo = GetTime();
for(i=0;i<n;i+=1)
{
parola_analizzata = alfabeto[(i/(l*l*l))%l]+alfabeto[(i/(l*l))%l]+alfabeto[(i/l)%l]+alfabeto[i%l];
pr(parola_analizzata);
/* if(parola_analizzata == parola_da_indovinare)
{
pr("Parola indovinata! " + parola_analizzata);
break;
}*/
}
tempo = GetTime()-tempo;
pr("Tempo impiegato: " + (tempo/3600000) + ":" + ((tempo/60000)%60) + ":" + ((tempo/1000)%60));
Notate che se la lunghezza della parola da indovinare,in questo caso la parola "B<7%" imperium ci mette una vita ad analizzare tutte le combinazioni,la complessità è esponenziale cioè n^k(n elevato alla k) dove n diciamo che è l'alfabeto(in questo caso 100 caratteri che rappresentano tutti i simboli di imperium e quelli importanti) e k è la lunghezza della parola(in questo caso 4,ma potete modificarlo per provare).
Questa è una soluzione iterativa e sfrutto il modulo per fare tutte le combinazioni,guardate questa riga in particolare:
CODICE parola_analizzata = alfabeto[(i/(l*l*l))%l]+alfabeto[(i/(l*l))%l]+alfabeto[(i/l)%l]+alfabeto[i%l];
Come per il tempo(secondi,minuti ecc...) l'alfabeto in questo caso ha 100 carattteri,quindi se siamo al carattere 102 avremmo il carattere 102/100 cioè 1 è il resto della divisione 2 quindi la lettera AC.
Ma noi abbiamo 4 caratteri e quindi arriviamo fino a: i/(l*l*l))%l,dove l è la lunghezza dell'alfabeto(100),i è il carattere n-esimo,nell'esempio di prima 102 = AC.
Sappiamo che le combinazioni seguno questo ordine,supponiamo che il nostro alfabeto abbia solo 5 caratteri(ABCDE) e che la lunghezza della parola sia 3,avremmo quindi:
CODICE AAA i=0;
AAB i=1;
AAC i=2;
AAD i=3;
AAE i=4;
ABA i=5;
ABB i=6;
ABC i=7;
ABD i=8;
ABE i=9;
ACA i=10;
ecc....
Per rappresentarli:
alfabeto[(i/(l*l))%l]+alfabeto[(i/l)%l]+alfabeto[i%l];
Ma noi abbiamo solo 3 caratteri in questo caso,e come facciamo a rappresentarli con un indice i? usando il modulo.
alfabeto[i%l]-> se i vale 1000 noi lo dividiamo per 5 e con il resto otteniamo l'ultima lettera dell'elenco,un pò come i secondi,se i secondi sono 200(cioè i=200) come possiamo ottenere i secondi e i minuti? i minuti si ottengono facendo 200/60 =3 e i secondi li otteniamo facendo 200%60=20 quindi 200 secondi sono 3 minuti e 20 secondi.
Se i secondi fossero 13454,a quante ore,minuti e secondi corrispondono?
Iniziamo dalle ore: ci verebbe in mente di fare 13454/24 = 560 ore,sbagliato! il calcolo giusto sarebbe: 13454/(ore in secondi) le ore in secondi sono uguali a minuti=60*60 secondi quindi applicando una sostituzione le ore sono: 13454/(60*60)
i minuti come prima sono minuti/(minuti in secondi) i minuti in second = 60 quindi:13454/60 = minuti,ed ecco perchè ho fatto: i/(l*l) dove l*l sta a indicare la posizione superiore in un certo senso.
Questo problema sono riuscito a risolverlo in maniera ricorsiva che vi farò vedere dopo in c chiaramente.
Ma comunque questi tipi di problemi non bisogna usarli(se non per input piccoli).
|
|
.
.
