Putem ajunge in (4,4) in 252 de moduri distincte.
► In cate moduri putem ajunge pe o pozitie (x,y)?
Putem ajunge in (x,y) de pe orice pozitie (x', y') care are x' <= x si y' <= y (evident fara pozitia curenta).
Numarul de moduri in care se poate ajunge pe o pozitie (x,y) este suma numarului de moduri in care se poate ajunge pe fiecare pozitie (x',y') din care putem sari direct in pozitia curenta (x,y), deci cu x' <= x si y' <= y, fara (x',y')=(x,y).
In tabelul atasat avem pe fiecare celula corespunzatoare unei perechi (x,y) numarul de moduri distincte in care putem ajunge pe acea celula.
Pe scurt, ne deplasam din coltul stanga sus spre coltul din dreapta jos (vezi directia sagetilor din imaginea atasata - nu e singura varianta de parcurgere dar asta e usoara de implementat in program) si valoarea pentru fiecare celula e suma valorilor din dreptungiul care incepe din stanga sus si se termina la celula curenta (din care excludem celula curenta) - vezi a doua si a treia imagine pentru exemplu (pentru a calcula ce e cu rosu adunam toate numerele colorate cu verde).
- Pentru (1,1) avem un singur mod de a ajuge acolo (acolo suntem de la inceput).
- Pentru (1,2) avem un singur mod de a ajunge acolo (prin (1,1))
- Pentru (2,1) avem un singur mod de a ajunge acolo (prin (1,1))
- Pentru (2,2) avem 3 moduri de a ajunge acolo (direct din (1,1), fie prin (1,1)→(1,2), fie prin (1,1)→(2,1)).
- Pentru (1,3) avem doua moduri de a ajunge acolo (direct din (1,1), fie prin (1,1)→(1,2)).
- ...
Dupa ce facem toate calculele obtinem tabelul din prima imagine. In celula (4,4) avem valoarea 252, care e raspunsul la intrebare.
Aceasta problema se rezolva prin programare dinamica (ne folosim de rezultatele calculelor de la pasii anteriori pentru determinarea rezultatului pentru calculul curent), abordare bottom-up (incepem de la datele furnizate initial f(1,1)=1 si ne indreptam catre solutie).
► Observatie:
Observam ca tabelul e simetric fata de prima diagonala, deci cand calculam nu e necesar sa facem adunarile doar pentru o parte din tabel. Util daca avem problema la un concurs/examen.
► Implementare C++:
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int sol[5][5];
int sumaCeluleInainte(int x, int y){
int suma = 0;
for(int i=1; i<=x;i++){
for(int j=1; j<=y;j++){
//Sari peste celula curenta
if(i==x && j==y) continue;
suma += sol[i][j];
}
}
return suma;
}
int main(){
//Initializam in (1,1) cu valoarea 1
sol[1][1] = 1;
//Construim matricea
for (int i=1; i<=4; i++){
for(int j=1; j<=4; j++){
//Sari peste prima celula
if(i==1 && j==1) continue;
//Aduna toate celulele care au fost inainte (din dreptunghi de la stanga sus)
sol[i][j] = sumaCeluleInainte(i,j);
}
}
//Afisam rezultat
cout << sol[4][4];
}
► Verificare:
Daca nu avem o demonstratie formala concludenta e posibil sa nu avem incredere ca algoritmul propus bazat pe programare dinamica este valid. Pentru un backtracking nu avem nevoie de demonstratie. Hai sa facem un backtracking sa vedem daca obtinem acelasi rezultat:
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int solCount = 0;
void printVector(vector<pair<int, int>> solutie){
// Afisam numarul solutiei si solutia
cout << "#" << ++solCount << " ";
for(auto element : solutie){
cout << "(" << element.first << "," << element.second << ") ";
}
cout << endl;
}
void bkt(int x, int y, vector<pair<int, int>> solutie){
// Daca am ajuns la destinatie
if (x==4 && y==4){
//Afiseaza drumul parcurs
printVector(solutie);
//Opreste
return;
}
//Ia toate celulele in care pot sari mai departe si vezi ce drumuri pot sa parcurg de acolo
//Celulele unde pot ajunge au x-ul mai mare sau egal, y-ul mai mare sau egal
//dar nu iar in calcul si celula curenta
for(int i=x; i<=4; i++){
for(int j=y; j<=4; j++){
//Nu lua iar celula curenta
if(i==x && j==y) continue;
//Adauga valoarea la solutie
auto copie_solutie = solutie;
copie_solutie.push_back({i,j});
//Vezi unde pot merge mai departe de aici
bkt(i,j, copie_solutie);
}
}
}
int main(){
bkt(1,1, {{1,1}});
}
►Rezultat obtinut backtracking:
[Vezi fisier atasat]
Am ajuns la aceasi concluzie, sunt 252 de moduri distincte de a ajunge din (1,1) in (4,4).
