Lucrare de atestare profesionala la informatica

Tehnica Backtracking aplicata la

PROBLEMA DAMELOR

- programare BGI

1. INTRODUCERE

1.1. Motivatia proiectului

Crearea unui soft educational este o arta care seamana cu rezolvarea unui puzzle. In activitatea sa omul lucreaza cu informatia. Metodele si tehnicile de organizare a informatiei au evoluat impreuna cu dezvoltarea echipamentelor de calcul si cu evolutia tehnicilor si limbajelor de programare.

Invatamantul modern presupune utilizarea unor mijloace de prezentare a informatiei intr-o forma dinamica si care sa simuleze realitatea. Se stie ca fiinta umana invata mai usor prin joc. Acest proiect ajuta elevii sa invete mai usor tehnica backtracking prin prezentarea unei interfete in cazul problemei damelor.

Softul educational reflecta necesitatea cunoasterii limbajelor de programare in scopul punerii in valoare a disciplinei <INFORMATICA>.

1.2. Scopul proiectului

In acest scop mi-am ales tema "Tehnica Backtraking aplicata la problema damelor -programare BGI-", care descrie in mod grafic importanta si necesitatea tehnicii Backtraking in diverse aplicatii.

2. TEHNICA BACKTRACKING

. Prezentarea tehnicii Backtracking

Aceasta metoda generala de programare se aplica problemelor in care solutia se poate reprezenta sub forma unui vector. Pentru fiecare problema concreta sunt date anumite relatii intre componentele x₁,. x_n ale vectorului x, numite conditii interne.

Multimea finita s=s₁x..xs_n se numeste spatiu al solutiilor posibile. Solutiile posibile care satisfac conditiile interne se numesc solutii rezultat. Ceea ce ne propunem este de a determina toate solutiile rezultat (cu scopul de a le lista sau de a alege dintre ele una care maximizeaza sau minimizeaza o eventuala functie obiectiv data).

O metoda simpla de determinare a solutiilor rezultat consta in a genera intr-un mod oarecare toate solutiile posibile si de a verifica daca ele satisfac conditiile interne. Dezavantajul consta in faptul ca timpul cerut de aceasta investigare exhaustiva este foarte mare.

Metoda backtracking urmareste sa evite generarea tuturor solutiilor posibile. In acest scop elementele vectorului x primesc pe rand valori, in sensul ca lui x_k i se atribuie o valoare numai daca au fost atribuite deja valori lui x₁,..x_k-1. Mai mult, odata o valoare stabilita pentru x_k, nu se trece direct la atribuirea de valori lui x_k+1, ci se verifica niste conditii de continuare referitoare la x₁,..x_k. Aceste conditii stabilesc situatiile in care are sens sa trecem la calculul lui x_k+1,..x nu vom putea ajunge la o solutie rezultat, adica la o solutie pentru care conditiile interne sa fie satisfacute.

Evident ca in cazul neindeplinirii conditiilor de continuare va trebui sa facem o alta alegere pentru x_k sau, daca s_k a fost epuizat sa micsoram pe k cu o unitate incercand sa facem o noua alegere pentru x_k; aceasta micsorare a lui k da numele metodei, ilustrand faptul ca atunci cand nu putem avansa, urmarim inapoi secventa curenta din solutie. Este evident ca intre solutiile de continuare si conditiile interne exista o stransa legatura. O buna alegere pentru conditiile de continuare are ca efect o importanta reducere a numarului de calcule.

2.2. Procedura standard

Procedura backtracking(n,x)

sir x(n)

k←1

while k>0

i←0

while [mai exista o valoare α din s_k netestata]

x_k←α

if _k(x₁.,x_k) atunci i←1; exit

endif

endwhile

if i=0 atunci k←k-1

else if k=n atunci scrie x₁.,x_k

else k←k+1

endif

endwhile

end

in care _k(x₁.,x_k) reprezinta conditiile de continuare pentru x₁.,x_k.

Descriere proiect si implementare

3.1. Prezentarea tehnicii Backtraking pentru problema damelor

Ca aplicatie la tehnica prezentata am expus problema damelor:

Pe o tabla de sah de dimensiune "n" trebuie asezate "n" dame astfel incat sa nu se atace una pe cealalta, adica sa nu existe doua dame pe aceeasi linie, coloana sau diagonala

In orice solutie rezultat pe fiecare linie a tablei se gaseste exact o dama, de aceea solutia pentru problema celor "n" dame se poate reprezenta sub forma unui vector x=(x₁,.x_n), unde pentru fiecare iє(1,.n), x_i reprezinta coloana pe care se afla dama de pe linia "i"( deci xє)

Programul are o serie de functii (exceptandu-le pe cele care apeleaza modul grafic) cu semnificatiile:

functia <dame> - implementeaza tehnica backtracking;

functia <potcontinua> -functia de testare a indeplinirii conditiilor interne sau a conditiilor de continuare ;

functia <scrie> -afiseaza solutia finala bazandu-se pe componentele vectorului "X" si semnificatia acestuia.

Algoritm:

P₁: se initializeaza contorul k cu 0;

P₂: v[k]=0;

P₃: daca v[k] are successor (v[k]<=n-1) si e valid (nu se ataca cu nici o alta dama, adica oricare ar fi x<k, v[x]!=v[k] si v[x]-v[k]!=|x-k|)

P₃₁: avem solutie (k=n-1) atunci se afiseaza solutia;

P₃₂: nu avem solutie si atunci se incrementeaza k;

P₄: daca exista successor dar nu e valid, se incrementeaza v[k] si se trece la 3;

P₅: daca nu exista, successor se decrementeaza k;

P₆: se executa pasii 3-5 pana cand k<0.

3.2. Prezentarea mediului de programare

Avand in vedere importanta modului de prezentare a aplicatiei pentru ca aceasta sa fie inteleasa de catre elevi am ales ca modalitate de implementare tehnica BGI.

Functiile grafice sunt stocate intr-o biblioteca nestandard. Pentru accesul la functiile implementate in Turbo C este folosit fisierul antet graphics.h.

Functiile folosite pentru implementarea grafica sunt:

• initi - detecteaza placa grafica si modul grafic folosit pentru placa grafica

- initializeaza modul grafic

• umplere - se traseaza chenarul tablei de sah
• tabla - se coloreaza tabla de sah
• titlul - se afiseaza titlul tehnicii de programare
• statuswindows - fereastra de stare care prezinta activitatea programului la fiecare pas
• stiva - simuleaza grafic stiva in gasirea solutiei finale
• atac - avertizeaza grafic cand conditiile interne (functia potcontinua) nu sunt indeplinite
• dama - deseneaza simbolul damei pe tabla de sah la un moment dat

3.3. Efecte si tehnici

Programul foloseste functii grafice predefinite ce apartin bibliotecii <graphics.h> ca:

• settextstyle
• Setcolor
• Settextjustify
• Outtext
• Floodfill
• Setfillstyle

Pentru inchiderea modului graphic se foloseste functia closegraph.

RESURSE

• Ruleaza pe platforma MS-DOS, cu cerinte hardware si software minimale.
• Necesita complilator C/C++.
• Spatiu de memorie 67.7 kb pentru Atestat.exe  si 4.80 kb pentru Atestat.cpp
• Se verifica pentru maxim 8 dame
• Proiectul ruleaza in functie de alegerea utilizatorului, prin delay sau prin getch
• Utilizatorul are la alegere 4 trepte de viteze de rulare, cuprinse intre 0 si 4

Previzualizare

Fig1.Cand programul ruleaza

fig2.La sfarsitul programului

5. LISTINGUL PROGRAMULUI

#include<stdio.h>

#include<graphics.h>

#include<conio.h>

#include<iostream.h>

#include<stdlib.h>

#include<dos.h>

typedef char car[100];

char c[30],a1[30],a2[30];

int x[9],nrsol=0,n,are,ka=4,z;

int opt,vi;

void initi(void)

void umplere(int x, int y, int c)

void titlu1(void)

void tabla(void)

void statuswindows(char c[100])

int dimens;setcolor(RED);

rectangle(50,350,640,480);

setfillstyle(0,BLACK);

floodfill(630,470,RED);

setcolor(14);

setcolor(LIGHTGREEN);

moveto(60,370);

settextjustify(0,0);

settextstyle(3,0,3);

moveto(60,370);

setcolor(15);

outtext(c);

setcolor(10);

outtext('Mazare Anca Valentina- XII F -');

setcolor(15);

settextjustify(0,0);

moveto(60,410); moveto(60,410); outtext(a1);

moveto(60,450); moveto(60,450); outtext(a2);

for(i=0;i<30;i++)

void stiva(void)

settextstyle(2,0,6);

settextjustify(2,2);

setcolor(14);

for(i=0;i<8;i++)

void atac(int i1, int i2, int j1, int j2)

if(opt) getch();

else delay(vi*50+50);

void dama(int a, int b, int i)

else

void scrie(int n, int x[100])

int potcontinua(int x[100], int ka)

else i++;

}

return are;

void dame(int n,int x[100])

if(!are)

else if(ka==n-1) scrie(n,x);

else

}

void main(void)

while(!(n>=4&&n<=8));

sprintf(g,'Ati ales %d dame',n);

cout<<'---CATE SOLUTII SA SE GENEREZE ?---'; cin>>z;

cout<<'---CUM DORITI SA RULEZE APLICATIA ?--- (delay/getch (d/g))';

char d=getch();

if(d=='d') opt=0; else opt=1;

cout<<'n---ALEGETI O TREAPTA DE VITEZA DE LA 0 LA 4---';

cin>>vi;

for(int i=0;i<8;i++)

x[i]=-1;

initi();

setbkcolor(1);

titlu1();

tabla();

stiva;

statuswindows(g);

statuswindows('Apasati orice tasta pentru a continua ');

getch();

dame(n,x);

getch();

closegraph();

BIBLIOGRAFIE:

Prof.dr. L.Vivoschi, lector dr. H.Georgescu, "Bazele informaticii. Algoritm.", Universitatea din Bucuresti-Facultatea de Matematica, Bucuresti, 1985;

Tudor Sorin, "Manual pentru clasa a X-a", Editura L&S INFOMAT, Bucuresti, 2000;

Bogdan Patrut, "Aplicatii in C si C++", editura Teora, 1998;

Aplicatia C/C++: Meniul Help.