PROBLEME BACKTRACKING
IN PLAN
1. Sa se completeze o
tabla de 5*5 cu saritura calului.
Iata doua solutii:
|
1 |
14 |
9 |
20 |
3 |
|
24 |
19 |
2 |
15 |
10 |
|
13 |
8 |
25 |
4 |
21 |
|
18 |
23 |
6 |
11 |
16 |
|
7 |
12 |
17 |
22 |
5 |
|
1 |
14 |
9 |
20 |
3 |
|
24 |
19 |
2 |
15 |
10 |
|
13 |
8 |
23 |
4 |
21 |
|
18 |
25 |
6 |
11 |
16 |
|
7 |
12 |
17 |
22 |
5 |
Aflati numarul de solutii si afisati tablele.
2.Se
da un tablou bidimensional (m linii, n coloane si m*n componente) cu elemente distincte.
Se dau si coordonatele primului punct. Ss se genereze un traseu in matrice
pornind de la punctul dat astfel incat suma ∑ k*a[i][j] (unde k=1 → n*m ) sa fie maxima. In
matrice se poate avansa numai la elemente vecine (pe cele 8 directii).
Ex: n=m=4;pozitia initiala : linia 3,coloana
2;
|
13 |
14 |
3 |
4 |
|
12 |
2 |
15 |
5 |
|
11 |
1 |
16 |
6 |
|
10 |
9 |
8 |
7 |
Suma maxima va fi:
1*1+2*2+3*3+…+16*16.
3.Ali Baba
Ali Baba i-a surprins pe cei 40 de hoti, in timp
ce cotrobaiau printre comorile lui. Hotii erau multi, el era singur, asa ca a
incercat sa negocieze cu ei. Avea o ladita speciala, pe care era notat numarul
de diamante aflate in aceasta, un numar avnd cel mult 40 de cifre, intr-o baza b.
Ali Baba a propus conducatorului hotilor sa elimine din numar b cifre,
dupa care poate sa plece cu atatea diamante cate reprezinta numarul ramas.
Hotul, mai intai a stabilit valoarea cea mai mica posibila b, deoarece a vrut sa
stabileasca un numar cat mai mic posibil de cifre pe care urmeaza sa le
elimine. Apoi a inceput tierea cifrelor. In timpul eliminarii a urmarit ca
numarul ramas sa fie cat se poate de mare.
Scrieti un program care il ajuta pe hot(Ali Baba are destule comori…).
Pe prima linie a fisierului de intrare ALIBABA.IN se afla un sir
de cifre, nedespartite prin spatii.
Pe prima linie a fisierului de iesire ALIBABA.OUT se va scrie pe fiecare cate un numar,
reprezentand numasrul ramas dupa eliminarea unei cifre.
Un
labirint dreptunghiular cu m linii si n coloane contine culoare (reprezentate
prin 0) si pereti (reprezentati prin 1). Se dau coordonatele initiale ale unui
soricel si coordonatele finale , unde trebuie sa ajunga. Soricelul poate avansa sus, jos , stanga sau
dreapta.(Incercati si cu cele 8 directii)
1. Sa
se genereze toate solutiile.
2. Sa
se afiseze soultia cea mai lunga (scurta)
Un
labirint dreptunghiular cu m linii si n coloane contine culoare (reprezentate
prin 0) si pereti (reprezentati prin 1). Se dau coordonatele initiale ale unui
soricel care trebuie sa iasa din labirint.SA se genereze toate solutiile
Un
labirint dreptunghiular cu m linii si n coloane contine culoare (reprezentate
prin 0) si pereti (reprezentati prin -1). Se dau coordonatele initiale ale unui
soricel si coordonatele finale , unde trebuie sa ajunga. Pe culoare se gasesc bucati de branza pt care
se cunoaste greutatea in grame.
1. Sa
se genereze toate solutiile., pt fiecare se afiseaza cantitatea consumata
2. Sa
se afiseze soultia cea mai „consistenta”
Un
broscoi se gaseste pe o frunza de nufar pe un lac. Broscoiul poate sari numai
sub forma sariturii calului si nu trebuie sa cada in apa. Pe lac se gasesc mai
multe frunze. Se da dimensiunea lacului (ca matrice mxn) si coordonatele
frunzelor. Ajutati-l pe roscoi sa iasa din lac. (si alte variante: de la o
frunza la alta etc)
Problema
fotografiei-