informatica - aplicatii ale metodei backtraking

 

1. TEMA SI PREZENTAREA MODULUI

 

“ APLICATII ALE METODEI BACKTRAKING »

In limbajul C++ prezinta DOUA APLICATII-

ale metodei backtraking si anume :

1. problema parantezelor

2. problema asezarii damelor pe o tabla de sah

Ambele probleme le-am rezolvat cu backtraking nerecursiv,deci am construit

fiecare functie : initializarea nivelului in stiva(la urcare in stiva),succesor,validare succesor,solutie si tiparire.

Problema asezarii a n dame pe o tabla de sah de n*n, a fost una din aplicatiile invatate..

Contributia mea consta in modul de afisare a solutiilor(pentru dame) ; am simulat tabla de sah ca o matrice si am folosit culori pentru scrierea solutiilor ,apelind functia putch(‘caracter’),din biblioteca dos.h

Am facut apel la bibliotecile stdio.h, dos.h , stdlib.h si conio.h, din care am apelat functiile pentru pozitionarea textului, culoare caractere ,apelarea functiei delay(x), pentru mentinerea pe ecran a unui text sau in combinatie cu sound() si nosound() ,pentru a da niste semnale sonore in anumite momente ale programului.

1. Problema parantezelor ,are urmatorul enunt :

-se citeste de la tastatura un numar intreg n,reprezentand numarul de paranteze ;sa se afiseze toate modalitatile de asezare a lor(deschide-inchide) intr-o expresie , astfel ca expresia sa fie corecta (cate paranteze deschid, atitea voi si inchide)..

Problema am rezolvat-o astfel :

• am codificat pozitia celor doua paranteze,deschis si inchis, cu valorile 1 si 2,deci

functia succesor va alege doar din doua valori,1 sau 2.

• functia de initializare are valoare 0 ca si la sezarea damelor
• functia de validare-verifica doua conditii si anume :
• prima valoare asezata  pe stiva va fi intotdeauna -1- adica paranteza deschisa si ultima valoare din stiva va fi -2- adica inchisa
• cand se  ajunge pe nivelul (k=n) ultima paranteza trebuie sa se inchida(valoare 2)

• functia solutie , va avea valoare adevarata(1) atunci cand ajungem pe ultimul nivel, si suma dintre parantezele deschise este identica cu suma dintre parantezele inchise si ultima paranteza este de tip 2, adica inchisa.
• Functia de tiparire, foloseste culori si functiile sound () si nosound() pentru afisarea fiecarei stive(solutie) pe cate un rand.Afisarea stivelor se face stiva cu stiva, prin apasarea unei taste,folosind functia cin.get().

• foarte important este validarea citirii numarului de paranteze, pentru ca el trebuie sa fie un numar par, adica cate paranteze deschid,atatea si inchid.
• Toate functiile definite mai sus se apeleaza in functia void btk(),nerecursiva,care este identica pentru orice program.

2.Problema asezarii a n dame pe o tabla de sah de n*n,

este rezolvata asa cum am invatat la curs ,adica:

• Functia de initializare a nivelului in stiva este zero.
• Functia succesorului , alege dama din cele n dame existente
• Functia de validare cuprinde:
• Conditia de nerepetabilitate a succesorului
• Conditia ca doua dame sa  nu se atace (ele se ataca pe diagonala sip e verticala)

• Functia solutie, va lua valoare 1(adica adevarat), daca au fost asezate toate cele n dame(k=n)
• Functia de tiparire, am construit o matrice patratica , ce simuleaza tabla de sah,

si am folosit culori pentru dame (litera D) si pentru linie,spatiul gol.Solutiile se obtin pe rand,apasand cate o tasta,astfel ca sa putem analiza fiecare solutie.

Toate functiile definite mai sus se apeleaza in functia standard void btk1().

Pentru apelarea functiilor btk(),btk1(), am folosit o structura switch(c)

care permite selectarea uneia din problemele prezentate

Datele problemei ca si meniul sunt pozitionate pe ecran cu functia textcolor() si gotoxy(),(trimite textul la linia y si coloana x),iar scrierea este realizata cu cout. Deci monitorul lucreaza in mod text,doar ca am folosit niste functii mai prietenoase din bibliotecile amintite mai sus.

2.RESURSE HARD SI SOFT NECESARE RULARII PROGRAMULUI

Pentru rularea programului nu este necesar decat softul complet(cu toate bibliotecile)

ale Borland C, sau a programului Turbo C++.

3.DATE DE RULARE

-pentru rularea damelor folositi un numar mic,n=4,5,6, ca sa vedeti pe ecran toate solutiile, pentru ca numarul solutiilor creste foarte mult,de exemplu la n=8 sunt 98 de solutii

- pentru paranteze puteti rula si valori mai mari :6,8,10,12…..

Observati ca daca alegeti un numar impar de parateze,veti repeta citirea pana obtineti un numar par.

4.POSIBILITATI DE EXTINDERE A PROGRAMULUI

In meniul cu cele 2 optiuni, se mai pot adauga oricate alte functii btk() de probleme ce se rezolva cu aceasta metoda in mod text, utilizand oricare din bibliotecile limbajului de programare

5.CONCLUZII

Lucrarea poate fi folosita ca material didactic ,la INFORMATICA, in predarea Tehnicilor de programare,clasele X si XI.

Am facut aceasta problema deoarece mi s-a parut cam grea de rezolvat in timpul anului ,dar m-am ambitionat si a iesit bine.

6. BIBLIOGRAFIE UTILIZATA

-manualul de INFORMATICA-clasa a XI-a , editura Niculescu

7. LISTINGUL PROGRAMULUI

#include<iostream.h>

#include<conio.h>

#include<dos.h>

#include<math.h>

#include<stdlib.h>

#include<stdio.h>

//problema parantezelor

int s[10],n,k;

void init(int k)

int succesor()

else return 0;}

int valid()

int sol()

void tip()

cout<<endl;

cin.get();

void btk()

while ((as=succesor())&&!valid());

if( as) if( sol())tip();

else

else k--;

//problema asezarii damelor pe tabla de sah

int suces1()

else return 0;}

int valid1()

int sol1()

//am pus toate damele pe tabla

void tip1()

else

cout<<endl;}

cout<<endl;

cout<<'.alta solutien';}

void btk1()

while((as=suces1())&& !valid1());

if (as) if (sol1()) tip1();

else

else k--;}}

// programul principal-functia main()

void main()

while(n%2==1); btk(); sound(800);delay(800);nosound(); ;break;

case 2: cout<<'nr dame=';cin>>n;btk1();sound(600) ;delay(100) ;nosound() ;break;

getch();}