Înainte de a începe, să vorbim despre ceea ce este problema Turnului Hanoi. Ei bine, acesta este un joc distractiv de puzzle în care obiectivul este de a muta un întreg teanc de discuri din poziția sursă în altă poziție. Sunt respectate trei reguli simple:

  1. Doar un singur disc poate fi mutat odată.
  2. Fiecare mișcare constă în luarea discului superior de pe una din stive și plasarea acestuia deasupra unei alte stive. Cu alte cuvinte, un disc poate fi mutat numai dacă este cel mai înalt disc dintr-o stivă.
  3. Niciun disc mai mare nu poate fi plasat deasupra unui disc mai mic.

Acum, să încercăm să ne imaginăm un scenariu. Să presupunem că avem o grămadă de trei discuri. Sarcina noastră este să mutăm această stivă sursa A la destinație C. Cum facem asta?

Înainte de a ajunge acolo, să ne imaginăm că există un punctul intermediar B.

Cum se rezolva problema Turnului Hanoi Ghid de algoritm
Trei discuri.

Putem folosi B ca ajutor pentru a termina această treabă. Acum suntem gata să mergem mai departe. Să parcurgem fiecare dintre pașii:

  1. Mutați primul disc de la A la C.
  2. Mutați primul disc de la A la B.
  3. Mutați primul disc de la C la B.
  4. Mutați primul disc de la A la C.
  5. Mutați primul disc de la B la A
  6. Mutați primul disc de la B la C
  7. Mutați primul disc de la A la C.
Citește mai multCum se face o promisiune dintr-o funcție de apel invers în JavaScript

Boom! Ne-am rezolvat problema.

Cum se rezolva problema Turnului Hanoi Ghid de algoritm
Turnul din Hanoi pentru 3 discuri. Wikipedia

Puteți vedea imaginea animată de mai sus pentru o mai bună înțelegere.

Acum, să încercăm să construim algoritmul pentru a rezolva problema. Așteptați, avem un cuvânt nou aici: „Algoritm”. Ce este asta? Vreo idee? Nicio problemă, să vedem.

Fotografie de bruce mars pe Unsplash

Ce este un algoritm?

Un algoritm este unul dintre cele mai importante concepte pentru un dezvoltator de software. De fapt, cred că nu este important doar pentru dezvoltarea sau programarea de software, ci pentru toată lumea. Algoritmii ne afectează în viața noastră de zi cu zi. Să vedem cum.

Să presupunem că lucrezi într-un birou. Deci, în fiecare dimineață, faceți o serie de sarcini într-o succesiune: mai întâi vă treziți, apoi mergeți la toaletă, luați micul dejun, vă pregătiți pentru birou, plecați de acasă, apoi puteți lua un taxi sau autobuz sau puteți începe să mergeți spre birou și, după un anumit timp, ajungeți la birou. Puteți spune că toți acești pași formează un algoritm.

Citește mai multCum se generează un fișier de reducere GitHub din Microsoft Word utilizând TypeScript

În termeni simpli, un algoritm este un set de sarcini. Sper că nu ați uitat acei pași pe care i-am făcut pentru a muta trei stive de discuri de la A la C. Puteți spune, de asemenea, că acești pași sunt algoritmul pentru rezolvarea problemei Turnului Hanoi.

În matematică și informatică, un algoritm este o specificație fără echivoc a modului de rezolvare a unei clase de probleme. Algoritmii pot efectua sarcini de calcul, procesare a datelor și raționament automat. – Wikipedia

Dacă aruncați o privire la acești pași, puteți vedea că făceam aceeași sarcină de mai multe ori – mutarea discurilor dintr-o stivă în alta. Putem numi acești pași în pași recursivitate.

Recursivitate

1611592267 411 Cum se rezolva problema Turnului Hanoi Ghid de algoritm
Recursivitate – gifă

Recursivitate apelează aceeași acțiune din acțiunea respectivă. La fel ca imaginea de mai sus.

Deci, există o regulă pentru efectuarea oricărei activități recursive: trebuie să existe o condiție pentru a opri executarea acțiunii. Sper să înțelegeți elementele de bază despre recursivitate.

Acum, să încercăm să construim o procedură care ne ajută să rezolvăm problema Turnului Hanoi. Încercăm să construim soluția folosind pseudocod. Pseudocodul este o metodă de scriere a codului computerului utilizând limba engleză.

tower(disk, source, intermediate, destination)
{

}
Citește mai multAutentificare utilizând Google în ASP.NET Core 2.0

Acesta este scheletul soluției noastre. Luăm numărul total de discuri ca argument. Apoi, trebuie să trecem sursa, locul intermediar și destinația, astfel încât să putem înțelege harta pe care o vom folosi pentru a finaliza lucrarea.

Acum trebuie să găsim un starea terminalului. Starea terminalului este starea în care nu vom mai apela această funcție.

IF disk is equal 1

În cazul nostru, aceasta ar fi starea noastră terminală. Deoarece atunci când va exista un singur disc în stiva noastră, este ușor să facem doar acel pas final și după aceea sarcina noastră va fi realizată. Nu vă faceți griji dacă nu vă este clar. Când vom ajunge la final, acest concept va fi mai clar.

Bine, am găsit punctul nostru de stare terminal în care ne mutăm discul la destinație astfel:

move disk from source to destination

Acum apelăm din nou la funcția noastră prin transmiterea acestor argumente. În acest caz, împărțim teancul de discuri în două părți. Cel mai mare disc (a n-a disc) este într-o parte și toate celelalte (n-1) discurile sunt în a doua parte. Acolo numim metoda de două ori pentru – (n-1).

tower(disk - 1, source, destination, intermediate)

După cum am spus, trecem total_disks_on_stack – 1 ca argument. Și apoi din nou ne mutăm discul astfel:

move disk from source to destination

După aceea, apelăm din nou metoda noastră astfel:

tower(disk - 1, intermediate, source, destination)

Să vedem pseudocodul nostru complet:

tower(disk, source, inter, dest)

IF disk is equal 1, THEN
      move disk from source to destination
   ELSE
      tower(disk - 1, source, destination, intermediate)   // Step 1
      move disk from source to destination                 // Step 2
      tower(disk - 1, intermediate, source, destination)   // Step 3
   END IF
   
END

Acesta este arborele pentru trei discuri:

Cum se rezolva problema Turnului Hanoi Ghid de algoritm
Arborele turnului hanoi (3 discuri)

Acesta este codul complet în Ruby:

def tower(disk_numbers, source, auxilary, destination)
  if disk_numbers == 1
    puts "#{source} -> #{destination}"
    return
  end
  tower(disk_numbers - 1, source, destination, auxilary)
  puts "#{source} -> #{destination}"
  tower(disk_numbers - 1, auxilary, source, destination)
  nil
end

Apel tower(3, 'source','aux','dest')

Ieșire:

source -> dest
source -> aux
dest -> aux
source -> dest
aux -> source
aux -> dest
source -> dest

Au fost necesari șapte pași pentru ca trei discuri să ajungă la destinație. Noi numim asta a metoda recursivă.

0*VXmzOesqL7l18gAr
Fotografie de Aron Visuals pe Unsplash

Calculele complexității timpului și complexității spațiului

Complexitatea timpului

Când rulăm cod sau o aplicație în mașina noastră, este nevoie de timp – cicluri CPU. Dar nu este același lucru pentru fiecare computer. De exemplu, timpul de procesare pentru un nucleu i7 și un nucleu dual nu sunt aceleași. Pentru a rezolva această problemă există un concept folosit în informatică numit complexitatea timpului.

Complexitatea timpului este un concept în informatică care se ocupă cu cuantificarea timpului necesar unui set de cod sau algoritm pentru a procesa sau rula în funcție de cantitatea de intrare.

Cu alte cuvinte, complexitatea timpului este în esență eficiență sau cât durează o funcție de program pentru a procesa o intrare dată. – techopedia

Complexitatea în timp a algoritmilor este exprimată cel mai frecvent folosind notație O mare. Este o notație asimptotică pentru a reprezenta complexitatea timpului.

Acum timp obligatoriu să se mute n discurile este T (n). Există două apeluri recursive pentru (n-1). Există o operație de timp constant pentru a muta un disc de la sursă la destinație, lăsați acest lucru să fie m1. Prin urmare:

T(n) = 2T(n-1) + m1    ..... eq(1)

Și

T(0) = m2, a constant   ...... eq(2)
From eq (1)
T(1) = 2T(1-1) + m1
     = 2T(0)+m1
     = 2m2 + m1 ..... eq(3) [From eq 2]
T(2) = 2T(2-1) + m1
     = 2T(1) + m1
     = 4m2 + 2m1 + m1 .... eq(4) [From eq(3)]
T(3) = 2T(3-1) + m1
     = 2T(2) + m1
     = 8m2 + 4m1 + 2m1 + m1  [From eq(4)]

De la aceste tipare – ec (2) până la ultimul – putem spune că complexitatea în timp a acestui algoritm este O (2 ^ n) sau O (a ^ n) Unde A este o constantă mai mare de 1. Deci are o complexitate exponențială în timp. Pentru creșterea unică a dimensiunii problemei, timpul necesar este dublu față de cel anterior. Acest lucru este foarte scump din punct de vedere al calculului. Majoritatea programelor recursive necesită timp exponențial și de aceea este foarte greu să le scrieți iterativ.

Complexitatea spațiului

După explicația analizei complexității timpului, cred că puteți ghici acum ce este asta … Acesta este calculul spațiului necesar în RAM pentru a rula un cod sau o aplicație.

În cazul nostru, spațiul pentru parametru pentru fiecare apel este independent de n, adică este constantă. Lăsați-l să fie J. Când facem al doilea apel recursiv, primul se termină. Asta înseamnă că putem reutiliza spațiul după terminarea primului. Prin urmare:

T(n) = T(n-1) + k .... eq(1)
T(0) = k, [constant] .... eq(2)
T(1) = T(1-1) + k
     = T(0) + k
     = 2K
T(2) = 3k
T(3) = 4k

Deci complexitatea spațiului este Pe).

După aceste analize, putem vedea că complexitatea timpului acestui algoritm este exponențială, dar complexitatea spațială este liniară.

Concluzie

Din acest articol, sper că acum puteți înțelege Turnul din Hanoi puzzle și cum să-l rezolvi. De asemenea, am încercat să vă ofer o înțelegere de bază despre algoritmi, importanța lor, recursivitate, pseudocod, complexitatea timpului, și complexitatea spațiului. Dacă doriți să aflați aceste subiecte în detaliu, iată câteva linkuri de cursuri online bine cunoscute:

  1. Algoritmi, Partea I
  2. Algoritmi, partea II
  3. Cursul Google despre Udacity
  4. Certificarea algoritmilor și structurilor de date Javascript (300 de ore)

Îmi poți vizita structuri de date și algoritmi repo să văd celelalte soluții ale problemelor mele.

sunt pe GitHub | Stare de nervozitate | LinkedIn