Integrarea algoritmului lui Dijkstra
De regulă, Algoritmul lui Dijkstra este formulat cu "tablouri paralele": d[] pentru distanţe şi p[] pentru predecesori; acestea trebuie prevăzute în cadrul programului apelant (la nivel global) - fiind folosite inclusiv pentru constituirea rezultatelor finale. Unele limbaje permit însă extinderea obiectelor pe parcursul execuţiei (în sensul adăugării de noi proprietăţi) - ceea ce permite integrarea rezultatelor în structura de date transferată algoritmului de către programul apelant.
Implementarea, de la minimal la eficient
Manuale versus programator (implementarea unui algoritm de teoria grafurilor)
Povestea arborelui parţial minimal
Implementarea clasică (apoi, folosind o structură priority_queue<double>) a algoritmului lui Prim
Compromisuri între stil şi eficienţă; biblioteci şi interfeţe
Saltul recursiv şi alergarea iterativă
Revenim asupra unor construcţii javaScript din Ambiţiile Cavalerului; vizam drumuri hamiltoniene pe graful săriturii calului - dar poate fi mulţumit Sir Knight? …cavalerii ăştia erau în stare să susţină o cauză până-n pânzele albe.
Cursivitatea recursivităţii (reformulare "tail recursion")
de la 'too much recursion' la formula iterativă
demersurile aplicaţiei Knight
modelarea "problemei calului" (ca graf şi ca obiect de memorie), folosind javaScript
reprezentarea vizuală a grafului în fereastra browserului
modelarea căutării unui drum hamiltonian (backtracking)
backtracking compus cu un algoritm euristic
principiul lui Warnsdorff (1823): continuă pe acel drum din care vei avea cât mai puţine ramificaţii - altfel spus, iterează recomandarea evidentă: dacă ai de ales între a face un ultim pas până la destinaţie şi respectiv a ocoli, atunci încearcă mai întâi prima variantă!
Experimente cu factoriale in javaScript
Câte cifre are n! şi care sunt cifrele iniţiale? Câte cifre zecimale are 22009 şi care sunt primele câteva cifre?
Există n încât n! să aibă n cifre zecimale? Există n încât n! să aibă n cifre hexazecimale?
Modelarea comparativă a calculului factorialelor în bazele 10, 106, 216 (în javaScript).
Cel mai mare număr natural care are Z cifre zecimale este 10Z - 1; cel mai mare număr natural care are T cifre în baza 256 este 256T - 1. Rezultă că Z = T * lg(256) ≈ T * 2.40824, adică:
reprezentarea în baza 256 necesită de minimum 2.4 ori mai puţine "locaţii" decât cea în baza 10, iar operarea bazată pe reprezentarea în baza 256 necesită de 2.4 ori mai puţine operaţii "cifră cu cifră" decât cea bazată pe reprezentarea zecimală obişnuită.
vezi Cărţile mele (de programare)