Arbori aritmetici şi expresii uzuale
Rezultatul - afişarea în anumite formate, a unei expresii - este banal (cum şi anticipasem) şi se putea obţine şi direct (fără clasele ArTree şi Climb de aici - instrumentând în schimb un algoritm "shunting yard"); dar nu rezultatul ca atare ne-a interesat, ci procedeul de analiză bazat pe proprietăţile operatorilor ("precedence climbing" - metodă ingenioasă, compactă şi eficientă de analiză sintactică) - împreună desigur, cu modelarea în C++ plecând de la modelul de arbori aritmetici ArTree.
Limbajul expresiilor aritmetice
De prin clasa a V-a, se tot deprind mecanisme de analiză sintactică şi morfologică a unui text (la "Limba română" şi la orele de "limbi străine"); iar aceste mecanisme servesc şi cazului mai simplu, al expresiilor algebrice (tot "texte", având asociate anumite "înţelesuri").
Propoziţiile corecte sunt constituite din anumite "părţi de vorbire", cu respectarea anumitor "reguli gramaticale" - a vedea programa şcolară pentru Limba şi literatura romănă, clasele V - VIII.
Un limbaj oarecare presupune deasemenea, anumite "părţi de vorbire" specifice şi un set de "reguli gramaticale" pe baza căruia se pot produce "propoziţiile" (sau "programele") corecte.
Trasarea şi restrângerea căutării, în metoda backtracking
Pentru analiza unui program bazat pe backtracking putem folosi (fie şi numai în scop instructiv) următorul procedeu (în loc de instrumente de tip "debugger"): rezumăm programul respectiv la un caz tipic (să producă o singură soluţie, nu pe toate) şi intercalăm în anumite puncte două "linii de control" (afişând nodul şi adâncimea). Rezultă un fişier text conţinând întreaga istorie a căutării soluţiei - poate foarte voluminos, dar putem angaja utilitare ca less şi grep pentru a depista ramificări inutile (de evitat în cursul căutării soluţiei).
Pânzele drumurilor hamiltoniene pe graful calului 5x5
Prelucrăm (prin comenzi perl) un fişier "informativ" şi reducem (printr-un program Python) cele 1728 de drumuri hamiltoniene ale calului de şah pe tabla 5x5, la un tablou javaScript conţinând cele 864 de drumuri "directe"; apoi, realizăm o funcţie javaScript care produce un element <canvas> pe care se vizualizează drumul indicat (pe tabla a cărei dimensiune este indicată).
Modelare C++ pentru probleme hamiltoniene
Pentru ce n găsim o secvenţă circulară a numerelor 1..n, astfel încât suma oricăror doi termeni vecini să fie pătrat perfect? Şirul cerut este un ciclu hamiltonian al grafului cu vârfurile 1..n în care avem câte o muchie pentru fiecare două valori a căror sumă este pătrat perfect.
Pe graful calului de şah de ordin 5x5 avem 4*304 + 8*56 + 64 = 1728 drumuri hamiltoniene (jumătate dintre ele fiind însă, inversele celorlalte).
Modelăm şi investigăm asemenea grafuri ("Square", "Knight"), bazându-ne pe o clasă "Hamilton" care oferă o metodă de căutare (backtracking compus cu regula lui Warnsdorff) a unui drum/ciclu hamiltonian.
vezi Cărţile mele (de programare)