La clasa a XI-a, urmează să ne ocupăm de metode şi tehnici de programare (backtracking, eficienţa algoritmilor, OOP), de grafuri şi algoritmi de prelucrare a grafurilor. Suntem însă chiar la începutul anului şcolar şi s-ar cuveni să recapitulăm unele lucruri (limbaj C++, ceva HTML), să revedem şi poate să regândim unele deprinderi de lucru (editor de cod sursă, compilator; documentare).
În aceste scopuri recapitulativ-anticipative, să rezolvăm cumva această primă problemă:
Când vom studia "metoda backtracking" ne vom reîntâlni cu "problema damelor"; dar pentru început, să discutăm şi să formulăm în C++ o schemă de rezolvare mai primitivă (în fond, reformulând mot à mot enunţul de mai sus):
1. aşază (oricum) N dame pe tablă;
2. dacă vezi dame care se atacă, atunci reia de la pasul 1;
3. (altfel) reţine soluţia găsită.
Este de sesizat (în loc de a lămuri acum, despre "dame" şi "atac") faptul că această "metodă" de obţinere a unei soluţii este practicabilă pentru foarte multe probleme. De exemplu, dacă vrem o permutare de N elemente:
1. generează un vector cu valori 1..N;
2. reia pasul 1, cât timp nu obţii o permutare;
3. înregistrează permutarea obţinută.
Pasul 1 poate produce (1,1,...,1) iar la reluare poate reproduce un vector generat anterior; să încercăm să nu credem că ar exista vectori favorizaţi şi să sperăm că putem obţine şi vectori noi.
Este important să ne dăm seama (vizând acum şi "eficienţa algoritmilor", de care ar urma să ne ocupăm mai târziu) ce şanse avem să nimerim o soluţie, procedând astfel. Ştim că numărul de permutări de $n$ elemente este $n!$, iar numărul de vectori cu valori $1..n$ este $n^n$ - deci probabilitatea căutată este $\frac{n!}{n^n}$, cu valori din ce în ce mai mici pe măsură ce $n$ creşte. Uneori ne putem mări aceste şanse, remodelând datele astfel încât să ţinem seama de unele aspecte elementare, specifice problemei.
Dacă vedem tabla de şah ca obiect bidimensional, indicând poziţia damei prin doi indici (linia şi coloana pe care se află dama), atunci numărul de poziţii posibile pentru cele $n$ dame este egal cu numărul de submulţimi cu $n$ elemente ale mulţimii de $n^2$ câmpuri ale tablei - fiind mult mai mare decât $n^n$ (a vedea eventual nota [1]).
Dar ştiind că n-ar trebui să avem dame pe o aceeaşi linie (fiindcă s-ar ataca reciproc), putem accepta această uşoară explicitare la Pasul 1:
1'. aşază N dame pe tablă, câte una pe linie;
rezultând astfel o anumită liniarizare a problemei: acum tabla apare ca un vector în care indicii reprezintă în mod implicit liniile tablei, iar însăşi componentele vectorului reprezintă coloanele în care sunt plasate damele. Procedând astfel, reducem numărul total de poziţii posibile la valoarea NN (în loc de combinări de N2 câte N) şi probabilitatea de a nimeri o soluţie se măreşte de cel puţin 10 ori, faţă de cazul bidimensional.
În orice caz - devine clar că nu putem pretinde să tratăm astfel (şi dorind un timp rezonabil, pentru execuţie) decât table de dimensiuni obişnuite - până pe la N = 10.
Putem trece acum, la "scrierea" programului? Răspunsul obişnuit ar fi nu - pentru motivul că încă n-am precizat suficient ce înseamnă "dame" (nu toţi ştiu ce este acela "şah"). Dar încă putem ignora, ce înseamnă că "damele se atacă"; în fond, problema constă în a genera în mod repetat un vector, până ce obţinem unul ale cărui componente satisfac anumite cerinţe - şi putem foarte bine, să tratăm separat (şi să amânăm) verificarea cerinţelor specifice problemei.
Problema obţinerii unei permutări şi respectiv "problema damelor" sunt chestiuni diferite, dar - cum am evidenţiat mai sus - ele pot fi tratate unitar, în fond printr-un acelaşi program, tratarea diferind numai în secţiunea de verificare a condiţiilor specifice problemei.
Aşa că putem foarte bine să trecem la "scrierea" programului, amînând precizările privitoare la "dame de şah" până în momentul când va trebui formulată secţiunea de testare; obţinem în fond un program care va putea rezolva prin "metoda randomizării" - dacă e să numim mai pompos, schema "primitivă" formulată mai sus - nu numai problema iniţială (a damelor), dar cam orice altă problemă care poate fi redusă la obţinerea unui vector care să corespundă anumitor restricţii. Şi tocmai acesta ar fi spiritul unei "metode de programare" (de exemplu, "metoda backtracking" de care urmează să ne ocupăm mai încolo) - ghidează unitar rezolvarea oricăreia dintr-o anumită clasă de probleme.
Vom folosi editorul gedit (aşa de simplu şi de plăcut de folosit, încât este deja preinstalat pe sistemele Ubuntu-Linux; îl putem instala imediat şi pe Windows). Separând editarea faţă de compilare şi faţă de execuţie, programatorul capătă libertate deplină şi control deplin asupra tuturor fişierelor pe care le creează, indiferent de câte fişiere editează şi indiferent de limbajele implicate.
Trecem "să scriem programul"… Să luăm aminte totuşi că (la fel ca în cazul lucrului "la tablă") nu "de scris" este vorba şi nici de copiat - nu poate fi vorba de aşa ceva: "tu dictezi programul din maculator şi eu scriu"; vom avea (fiecare în parte, pe cât se poate) de conceput şi dezvoltat un program, pe baza unui şablon discutat în prealabil. Încercăm să arătăm cam cum s-ar proceda:
În screencast-ul desfăşurat mai sus, am fixat N=7 şi am instituit (la nivel global) un vector pos[] în care să se obţină soluţia; am formulat şablonul programului ("Generează câte un pos[] până când convine şi Scrie soluţia") şi am început să-l explicităm, scriind întâi main() şi adăugând deasupra, pe rând, definiţiile funcţiilor is_good(), touch() şi write_html() - obţinând în final acest program:
#include <fstream> #include <math.h> /* abs() */ #include <cstdlib> /* srand(), rand() */ #include <ctime> using namespace std; #define N 7 // Problema damelor, pe tabla NxN int pos[N]; // damă în (Linia: i, Coloana: pos[i]), i=0..N-1 int touch(int i, int j) { // damele se atacă? // pentru "problema permutărilor": return pos[i] == pos[j]; return pos[i] == pos[j] || abs(i-j) == abs(pos[i]-pos[j]); } int is_good(){ // există dame care se atacă? for(int i=0; i < N; i++ ) for(int j = i + 1; j < N; j++ ) if(touch(j, i)) return 0; return 1; } void write_html() { ofstream F("dame.html", ios::app); // adaugă soluţia curentă F<<"<table border='1' style='padding:0.5em;float:left;'>"; for(int i=0; i < N; i++) { F<<"<tr>"; int k = pos[i]; // accesez tabloul în afara ciclului care urmează! for(int j=0; j < N; j++) F<<"<td>"<<(j==k? "♛":" ")<<"</td>"; F<<"</tr>"; } F<<"</table>"; } int main() { // Iniţializează generatorul de numere aleatoare, // pe baza momentului de timp al execuţiei programului srand(time(NULL)); // www.cplusplus.com/ // Generează pos[] şi repetă dacă nu satisface do { for(int i=0; i < N; i++) pos[i] = rand() % N; } while(! is_good()); // Înscrie soluţia obţinută write_html(); }
Am arătat cum obţinem executabilul pe un sistem Linux; pe un sistem Windows putem folosi pentru aceasta, MinGW - dar nu ne interesează să-l folosim ca "mediu integrat de dezvoltare"[2], ci vrem să folosim direct compilatorul de C şi pe cel de C++, pe care le încorporează. În acest scop avem de făcut o operaţie preliminară: trebuie să furnizăm sistemului calea pe care se vor putea accesa aceste compilatoare, printr-o comandă (lansând CMD.exe) set PATH=%PATH%;C:\MinGW\bin, presupunând că MinGW este instalat la C:\MinGW (a vedea MinGW/wiki).
[1]
$\mathsf{C}_{n^2}^n \gt n^n,\,\forall n\in\mathbb{N}^{\ast},\,n\geqslant 2$
Demonstraţie:
$\mathsf{C}_{n^2}^n = \dfrac{n^2!}{(n^2-n)!\cdot n!} = \dfrac{(n^2-n+1)(n^2-n+2)\cdots(n^2-n+n)}{1\cdot 2\cdots n} = \prod\limits_{k=1}^n\dfrac{n^2-n+k}{k} \gt n^n$
fiindcă $\dfrac{n^2-n+k}{k} \gt n,\,\forall k\in 1..n$ (eliminând numitorul, revine la $n(n-1)\gt k(n-1)$).
Avem de exemplu, $\mathsf{C}_{5^2}^5 = 53130\gg 5^5=3125$.
[2]
Subliniem: nu avem de învăţat să folosim un IDE, dependent de un anumit limbaj - ci să învăţăm să programăm folosind diverse limbaje; compilatoarele şi interpretoarele sunt produse independente şi trebuie folosite ca atare, iar nu prin intermediul unor IDE-uri (de care ajungi apoi să depinzi).
Este de dorit să nu ne mulţumim cu faptul că "programul merge"; la ce ar putea el folosi - doar ca să îl lansăm în execuţie pe calculatorul propriu (cum am şi făcut în screencast, mai sus) şi să vedem rezultatul? În general programele (în format executabil, de obicei) sunt destinate să fie folosite de către diverşi utilizatori (de obicei, prin intermediul Internetului), sau să fie invocate din diverse alte programe sau aplicaţii (indiferent de limbajul acestora).
Ne propunem să modificăm programul de mai sus, pentru a satisface următorul scenariu: un utilizator oarecare (în particular, o anumită aplicaţie proprie) accesează cumva programul nostru, furnizând dimensiunea dorită N=5..10 a tablei şi dorind să obţină direct diagrama corespunzătoare unei soluţii a problemei damelor. Dispunem aici de o ilustrare potrivită a acestui scenariu:
Adaptând cele arătate în acest screencast la cazul programului "dame_rand.cpp" redat mai sus - ar fi suficient ca în cadrul funcţiei "write_html()", să eliminăm definiţia variabilei "F", să înlocuim peste tot "F" cu "cout" (având grijă să includem "iostream", în loc de "fstream") şi să inserăm cout << "Content-type:text/html\n\n"; ca primă linie a acestei funcţii.
Recompilând şi transferând apoi executabilul în /cgi-bin/-ul site-ului (cel "local", de data aceasta) - putem constata deja că http://docere.loc/cgi-bin/dame.cgi furnizează browserului din care s-a lansat această cerere un <table> corespunzător unei soluţii a problemei damelor, pentru N = 7.
Pentru a obţine soluţii pentru N = 5..10 (nu doar pentru N = 7), mai trebuie făcute două-trei modificări; mai întâi, reconsiderăm variabilele globale N şi pos[] astfel:
int N; // în loc de #define N 7 int* pos = 0; // în loc de int pos[N];
Apoi, adaptăm main() pentru a prelua valoarea transmisă pentru N (şi a institui pos[]):
int main(int argc, char* argv[]) { /* ... */ N = atoi(argv[1]); if(N > 10 || N < 5) N = 7; pos = new int[N]; // damă în (Linia: i, Coloana: pos[i]), i=0..N-1 // Generează pos[] şi repetă dacă nu satisface /* ... */ }
Recompilăm şi facem o probă din linia de comandă:
vb@vb:~/clasa11$ g++ dame_rand.cpp -o dame.cgi vb@vb:~/clasa11$ ./dame.cgi 5 Content-type:text/html <table border='1' style='padding:0.5em;float:left;'> <tr><td>♛</td><td> </td><td> </td><td> </td><td> </td></tr> <tr><td> </td><td> </td><td> </td><td>♛</td><td> </td></tr> <tr><td> </td><td>♛</td><td> </td><td> </td><td> </td></tr> <tr><td> </td><td> </td><td> </td><td> </td><td>♛</td></tr> <tr><td> </td><td> </td><td>♛</td><td> </td><td> </td></tr> </table> vb@vb:~/clasa11$
S-a afişat header-ul şi apoi răspunsul pe care browserul va trebui să-l interpreteze (ca "text/html") şi să-l redea utilizatorului.
Transferând executabilul în directorul /cgi-bin/, vom putea acum invoca de exemplu http://docere.loc/cgi-bin/dame.cgi? 8, obţinând în browser o soluţie pentru N=8 (iar dacă repetăm invocarea, obţinem eventual o altă soluţie).
Să facem acum următoarea distincţie, de bun-simţ: în cazul calculării factorialelor are sens să folosim CGI, aşa cum am arătat în screencast-ul de mai sus - fiindcă programul invocat a fost realizat direct în limbaj de asamblare (optimizând toate calculele şi exploatând "la maximum" regiştrii microprocesorului) şi este destul de clar că n-am putea reuşi o viteză de execuţie mai bună, dacă am fi implicat în schimb un program de calcul a factorialelor scris într-un limbaj de nivel înalt.
Pe când, pentru a obţine în browser o soluţie a problemei damelor - chiar nu se cuvine să procedăm cum am arătat (în scop didactic): "dame_rand.cpp" se poate rescrie foarte uşor în javascript (limbajul "nativ" pentru browsere) şi nu este de loc necesar să folosim CGI; în acest caz, cu N mic - chiar nu avem diferenţe sensibile, de la un limbaj la altul, în privinţa vitezei de execuţie şi este firesc atunci, să folosim direct resursele browserului.
vezi Cărţile mele (de programare)