momente şi schiţe de informatică şi matematică
To attain knowledge, write. To attain wisdom, rewrite.

Pânzele drumurilor hamiltoniene pe graful calului 5x5

Python | canvas | graf | javaScript | knight | perl
2014 mar

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

C++ | Warnsdorff | backtracking | graf
2014 mar

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.

Generarea expresiilor aritmetice cu patru operanzi

C++
2014 feb

Modelăm expresiile aritmetice prin arbori binari, plecând de la o clasă abstractă pentru noduri şi angajând "smart pointers" din C++11. Generăm prin acest model, toate expresiile aritmetice cu 4 operanzi - filtrând eventual pe cele care interesează în privinţa valorii.

Generarea directă a unui ciclu eulerian, în grafurile complete

C++ | DOT | Hierholzer | Python | graf
2014 feb

Pentru graful complet cu nodurile 0..2n şi cu listele de adiacenţă ordonate crescător, ciclul eulerian produs de algoritmul lui Hierholzer startat din nodul 2n este constituit din n cicli disjuncţi după muchii, având în comun vârful 2n şi respectiv lungimile 3+4*j (j=0..n-1); exceptând ciclul cel mai lung, nodurile fiecărui ciclu - afară de primul nod 2n şi de ultimele patru noduri - provin din nodurile de aceeaşi poziţie ale ciclului de lungime imediat superioară, prin majorarea acestora cu 2.

Model C++ de graf şi submodel de graf eulerian

C++ | DOT | Hierholzer | graf
2014 jan

Completăm modelul "minimal" de graf (introdus anterior), astfel încât să facilităm algoritmii care angajează muchiile grafului: după ce muchia este parcursă, ea trebuie "ştersă" (marcând-o drept "utilizată"), iar gradele curente ale capetelor ei trebuie decrementate. Derivăm de aici, o modelare a grafurilor euleriene (algoritmul lui Hierholzer) şi testăm pentru grafurile complete (K1001 poate fi "rezolvat" sub 100 de secunde).


Prev
Next
ALL (349 titluri)

vezi Cărţile mele (de programare)

despre acesta ~ Home
(sau https://vlad.bazon.net/

Factoriale | Graficul funcţiilor

PGN browser | chess JS engine

Load

in /slightchess

/slightchess

626 partide analizate cu Crafty

(R) Computer Art | Decoraţiuni

Aplicaţii şcolare (javaScript)

Sinteze: