Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  
AccessAdobe photoshopAlgoritmiAutocadBaze de dateC
C sharpCalculatoareCorel drawDot netExcelFox pro
FrontpageHardwareHtmlInternetJavaLinux
MatlabMs dosPascalPhpPower pointRetele calculatoare
SqlTutorialsWebdesignWindowsWordXml

Tehnica Backtracking aplicata la PROBLEMA DAMELOR - programare BGI

calculatoare



+ Font mai mare | - Font mai mic



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 x1,. xn ale vectorului x, numite conditii interne.

Multimea finita s=s1x..xsn 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 xk i se atribuie o valoare numai daca au fost atribuite deja valori lui x1,..xk-1. Mai mult, odata o valoare stabilita pentru xk, nu se trece direct la atribuirea de valori lui xk+1, ci se verifica niste conditii de continuare referitoare la x1,..xk. Aceste conditii stabilesc situatiile in care are sens sa trecem la calculul lui xk+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 xk sau, daca sk a fost epuizat sa micsoram pe k cu o unitate incercand sa facem o noua alegere pentru xk; 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 sk netestata]

xk←α

if k(x1.,xk) atunci i←1; exit

endif

endwhile

if i=0 atunci k←k-1

else if k=n atunci scrie x1.,xk

else k←k+1

endif

endwhile

end

in care k(x1.,xk) reprezinta conditiile de continuare pentru x1.,xk.

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=(x1,.xn), unde pentru fiecare iє(1,.n), xi 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:

P1: se initializeaza contorul k cu 0;

P2: v[k]=0;

P3: 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|)

P31: avem solutie (k=n-1) atunci se afiseaza solutia;

P32: nu avem solutie si atunci se incrementeaza k;

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

P5: daca nu exista, successor se decrementeaza k;

P6: 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.





Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 3326
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved