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ă.
Şablonul "return 0; ELSE return 1" (mot-à-mot din Pascal în C)
Manualul vizează în paralel limbajul Pascal şi limbajul C/C++ (plus… pseudocodul excesiv). Ideea de a viza împreună mai multe limbaje de programare este excelentă, dar "realizarea" ei în acest manual este… "în paralel": programele redate în C/C++ nu sunt altceva în acest manual, decât traduceri mot-à-mot ale programelor Pascal.
Limbajul Pascal nu are o instrucţiune return. Ca urmare, traducerea mot-à-mot a funcţiilor recursive din Pascal în C duce la formulări principial greşite: if(...) return 0; else return 1;
Numerele vizate la matematică nu sunt la fel cu cele vizate într-un limbaj de programare; ca urmare, transcrierea mot-à-mot de la formulă matematică la program poate atrage rezultate greşite.
greşit: int id_mijloc = (id_st + id_dr) / 2;
// variabile C de tip "int"
corect: int id_mijloc = id_st + (id_dr - id_st) / 2;
Când suma depăşeşte sizeof(int)
, rezultatul va fi trunchiat modulo INT_MAX + 1
; de aceea, prima variantă de mai sus este incorectă.
vezi Cărţile mele (de programare)