Ce urmarim in urma acestui proiect?

• Aflarea a cat mai multe despre aceasta metoda• Gasirea unei atribuiri in viata practica• Luarea unei note bune la informatica

Minotaurul !? Ce cauti tu in filmul meu?

Credeam ca-i filmu meu…ma rog!

Sincer sa fiu m-am ratacit!

Am tot luat-o stanga, stanga,stanga si nimic…

Eu am luat-o dreapta dreapta dreapta…si tot nimic. Eu vreau sa ajung in mijloc, sa gasesc Pocalul de Foc.

N-am nimic mai bun de facut asa ca voi impartasi cu tine aceast papirus pe care l-am gasit acum mult timp. Poate intelegi tu ceva…

Uau!!! Este tehnica de mult pierduta. Tehnica Backtracking!!! Care genereaza toate solutiile posibile unei probleme ca aceasta.

#include<iostream.h>#include<conio.h>int sol[100][2],l[10][10],m,n,i,j,lin,col;

int vizitat(int k, int lin,int col){int v=0;for(i=1;i<=k;i++)if(sol[i][0]==lin && sol[i][1]==col) v=1;return v;}void tipar(int k,int lin,int col){cout<<"solutie "<<endl;for(i=1;i<=k-1;i++) cout<<sol[i][0]<<" "<<sol[i][1]<<endl; if(lin==0) cout<<"iesirea prin nord"<<endl; else if(lin==m+1) cout<<"iesirea prin sud"<<endl; else if(col==0) cout<<"iesirea prin vest"<<endl; else cout<<"iesirea prin est"<<endl;} void back(int k, int lin, int col) { if(lin==0 ||lin==m+1 || col==0 ||col==n+1) tipar(k,lin,col); else{ sol[k][0]=lin; sol[k][1]=col; for(int i=1;i<=4;i++) switch(i)

          

{case 1: if(l[lin][col] &8&& !vizitat(k,lin-1,col)) back(k+1,lin-1,col); break; case 2: if(l[lin][col]&4 &&! vizitat(k,lin,col+1)) back(k+1,lin,col+1); break; case 3: if(l[lin][col] && ! vizitat(k,lin+1,col)); back(k+1,lin+1,col); break; case 4: if(l[lin][col]&1&& ! vizitat(k,lin,col-1)) back(k+1,lin,col-1); break; } } }main() {cout<<"M="; cin>>m; cout<<"N="; cin>>n; for(i=1;i<=m;i++) for(j=1;j<=n;j++) {cout<<"l["<<i<<","<<j<<"]="; cin>>l[i][j]; } cout<<"linie="; cin>>lin; cout<<"coloana="; cin>>col; back(1,lin,col); getch();

}Program.exe

Minotaur sa fi sa nu intelegi…

Sa ne uitam cu atentie la schema labirintului.

Observam ca peretii si drumul sunt inlocuite de numere

6 10 14 11 2

8 9 13 5 7

1 12 11 6 4

4 2 3 15 9

Fiecare numar este un set de 4 cifre in baza 2! 1 ne indica faptul ca e un perete, iar 0 ca este drum liber.

Acum ca am inteles cum functioneaza, putem genera solutii pana cand ajungem la destinatie.

Daca vrei sa treci de mine va

trebui sa-mi raspunzi la

urmatoarea intrebare:

Zeii vor sa afle cum te-a

ajutat aceast papirus,

Potter?

Am aflat ca tehnica are

intrebuintare si in viata reala.

Am inteles cum functioneaza

tehnica mai bine

Am generat mai multe solutii

false alegand-o in final pe cea

buna.

Si in caz ca ne vom pierde intr-un

labirint vom sti mereu cum sa

gasim calea!

Ohoo!

Daca a-ti inteles atatea

lucruri despre tehnica zeilor

meritati sa treceti de mine(si

la informatica)!!

In tot acesti ani nu am reusit sa inteleg aceasta tablita!

Mersi Potter mai luminat!

Acum ca ti-ai gasit Pocalul ne putem intoarce fiecare la filmul lui!

Si asa a fost descoperita si inteleasa

metoda Backtracking care ne bantuie

si in zilele noastre !