Ce ştiu despre aceasta metodă?

Tehnică utilizată în cazul în care este necesară generarea mai multor soluţii, alcătuită dintr-o succesiune de subprograme menite să uşureze sarcina programatorului.

Ce este backtracking-ul ?Exemplu

Cătălina este o studentă în anul I la facultatea de informatică din Bucureşti. Ea trebuie să-şi aleagă 5 cursuri opţionale din cele 10 propuse, printre care unul trebuie să fie de programare vizuală şi unul de limba spaniolă. Ce ar putea să aleagă pentru a-şi completa programul de opţionale ?

Programare vizuală

Inteligenţă artificială

Limba spaniola

Limba engleză

Educaţie fizică

Analiză matematică

Inginerie software

Criptografie si teoria codurilor

Baze de date şi tehnologii web

Algoritmi şi bioinformatică

Posibilitatea nr. 1Posibilitatea nr. 2

Ce vreau să ştiu!

Cum functionează backtracking-ul?

La ce tip de probleme îl pot aplica?

Cum mă ajută în viaţa de zi cu zi?

Cum ne ajută logica dobândită după lucrul cu backtraking-ul?

Un altfel de backtracking

Atilla şi Theodoric I

Era odată un rege nemilos şi însetat după putere pe nume Atilla. Ca urmare a multor cuceriri barbare şi violente el a fost închis într-o temniţă.

Era odată un rege nemilos şi însetat după putere pe nume Atilla. Ca urmare a multor cuceriri barbare şi violente el a fost închis într-o temniţă.

Tot atunci mai era şi un cal tânăr ce încă din copilărie auzise de marele rege Atilla şi îşi dorea să-l slujească graţie admiraţiei ce i-o purta. Credea că va învăţa multe lucruri de la un asemenea lider eminent care a reuşit să-şi mărească regatul fără probleme.

Tot atunci mai era şi un cal tânăr ce încă din copilărie auzise de marele rege Atilla şi îşi dorea să-l slujească graţie admiraţiei ce i-o purta. Credea că va învăţa multe lucruri de la un asemenea lider eminent care a reuşit să-şi mărească regatul fără probleme.

Pentru a-i putea fi de folos lui Atilla, calul s-a dus la un vrăjitor pentru a-i cere o putere supranaturală. Acesta i-a dat copite de foc cu care putea alerga ca vântul, dar în acelaşi timp ardea tot ceea ce călca astfel nemaiputând să se întoarcă pe acelaşi drum.

Pentru a-i putea fi de folos lui Atilla, calul s-a dus la un vrăjitor pentru a-i cere o putere supranaturală. Acesta i-a dat copite de foc cu care putea alerga ca vântul, dar în acelaşi timp ardea tot ceea ce călca astfel nemaiputând să se întoarcă pe acelaşi drum.

De cum l-a întâlnit, Atilla a acceptat calul ca noul său prieten credincios. Chiar avea nevoie de ajutor întrucât avea planuri mari pentru o regiune pe care dorea de mai mult timp să o cotropească. Văzând cât de naiv este fanul său imparicopitat, Atilla l-a tratat ca atare pentru a-l feri de adevăr.

De cum l-a întâlnit, Atilla a acceptat calul ca noul său prieten credincios. Chiar avea nevoie de ajutor întrucât avea planuri mari pentru o regiune pe care dorea de mai mult timp să o cotropească. Văzând cât de naiv este fanul său imparicopitat, Atilla l-a tratat ca atare pentru a-l feri de adevăr.

Imediat ce a evadat, Atilla a pornit neîntârziat spre castelul lui Theodoric, regele ale cărui pământuri le vroia, lăsând în urma sa câmpii şi păduri arse de copitele înflăcărate ale calului său.

Imediat ce a evadat, Atilla a pornit neîntârziat spre castelul lui Theodoric, regele ale cărui pământuri le vroia, lăsând în urma sa câmpii şi păduri arse de copitele înflăcărate ale calului său.

Când Atilla l-a prins pe Theodoric, calul şi-a dat seama cât de mare a fost greşeala pe care a făcut-o ajutându-l pe Atilla. Până atunci crezuse că acesta este un rege puternic, dar nu şi tiran.

Când Atilla l-a prins pe Theodoric, calul şi-a dat seama cât de mare a fost greşeala pe care a făcut-o ajutându-l pe Atilla. Până atunci crezuse că acesta este un rege puternic, dar nu şi tiran.

Aşa că l-a înşfăcat pe Atilla şi l-a purtat până la închisoarea sa atât de repede că regele nici nu şi-a dat seama ce i se întâmplă.

Aşa că l-a înşfăcat pe Atilla şi l-a purtat până la închisoarea sa atât de repede că regele nici nu şi-a dat seama ce i se întâmplă.

O dată ajunşi şi Atilla închis, calul a rămas să-l păzească pe prizonier pentru a-şi ispăşi păcatele dar şi din motivul că arsese totul în jurul său şi nu mai putea pleca.

O dată ajunşi şi Atilla închis, calul a rămas să-l păzească pe prizonier pentru a-şi ispăşi păcatele dar şi din motivul că arsese totul în jurul său şi nu mai putea pleca.

1

2

3

4

5

6

7

8

1 2 3 4 5 6 7 8

5 4

6 6

7 8

5 7

4 5

3 3

Vectorul stivă

6

5

4

3

2

1

Theodoric! Pregăteşte-te! Vin după tine!

Codul sursă#include<fstream.h>#include<stdlib.h>ifstream f (“atilla.in”);int dx[]={-2,-1,1,2,2,1,-1,-2}; int dy[]={1,2,2,1,-1,-2,-2,-1};

int t[100][100],st[100][2],i,j,n,k,xc,xr,yc,yr;

Bibliotecile

Fişierul

Mişcările

calului

void main()

{f>>n;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

f>>t[i][j];

f>>xc>>yc;

f>>xr>>yr;

f.close();

back(1,xc,yc); }

Citirea matricei

Coordonate cal

Coordonate rege

Daţi clickDaţi click

void back(int k, int lin, int col)

{int i, l, c;

if( solutie (k) ) tipar(k);

else{

st[k][0]=lin;

st[k][1]=col;

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

{l=lin+dx[i];

c=col+dx[i];

if(l<=n&&l>=1&&c<=n&&c>=1&&t[l][c]==0)

{t[l][c]=1;

back(k+1,l,c)

t[l][c]=0;

}}}

}

Se pun în stivă coordonatele calului

Se execută mişcarea calului

Daţi clickDaţi click

int solutie(int k)

{ int ok=0;

for(j=1;j<k;j++)

if(st[j][0]==xr&&st[j][1]==yr)

ok=1;

if(k>1&&st[k][0]==xc&&st[k][1]==yc&&ok==1)

return 1;

else

return 0;

}Verifica dacă Atilla(calul) a ajuns la rege!

Ce am invatat!!!

Să lucrez mai uşor cu backtracking-ul!

Când anume trebuie să folosesc backtracking-ul!

Să gândesc logic şi să rezolv problemele pe rând!

Bibliografie!Pozele – internet

Algoritmul – “Manual de Informatică Profil real clasa a XI-a”, Vlad Huţanu şi Tudor Sorin, editura L&S Soft, 2006

MULTUMIM PENTRU ATENTIA ACORDATA!!

CAST:

Grozavu Elena as The Horse

Murariu Ana Maria as King Theodoric I

Stoica Maria as Atilla the hun

CAST:

Grozavu Elena as The Horse

Murariu Ana Maria as King Theodoric I

Stoica Maria as Atilla the hun