Fie o matrice cu n linii si m coloane, (n=11, m=8). In cate moduri se poate ajunge din coltul stanga-sus (coordonatele 1, 1), in coltul dreapta jos (coordonatele n m), cu un numar minim de pasi. Te poti deplasa doar pe verticala/orizontala, cu o pozitie.
Răspunsuri la întrebare
Trebuie sa facem n pasi in jos si m pasi la dreapta, indiferent de ordinea in care facem aceste instructiuni, iar distanta Manhattan va fi minima.
Numarul de moduri in care putem alege traseul este numarul de moduri in care putem ordona n operatii de mers in jos (notate cu "jos") si m instructiuni de mers la dreapta (notate cu "dreapta").
Cate astfel de permutari unice ale vectorului A = { "jos","jos","jos","jos","jos","jos","jos","jos","dreapta","dreapta","dreapta","dreapta","dreapta","dreapta","dreapta","dreapta","dreapta","dreapta","dreapta" }; exista ?
Putem gandi problema altfel :
Avem la dispozitie 19 locuri si trebuie sa alegem 11 dintre acestea in care sa punem cuvantul "jos". Ordinea in care punem cuvantul "jos" nu conteaza.
In acest caz putem observa usor ca avem o problema care se rezolva prin combinari. Astfel, numarul de permutari unice ale vectorului A este
Acelasi rezultat il avem si daca generam permutarile intr-un program C++. Ai codul sursa atasat. Iti sugerez sa nu deschizi fisierul rezultat cu notepdad daca decizi sa rulezi programul, o sa se blocheze.
