Problema Problema săsăriturii riturii ccaluluialului

ELEV: CIORA FLAVIU

CLASA:a XI-a B

Enunţul problemeiEnunţul problemei

Se dă o tablă de şah cu dimensiunea n*n. Un cal se găseşte în linia 1 şi coloana 1. Găsiţi un şir de mutări ale calului astfel încât acesta să acopere întreaga tablă fără a trece

printr-o căsuţă de două ori.

Pentru n=5 avem o tablă de dimensiunea 5 linii şi 5 coloane

Algoritmul de rezolvareAlgoritmul de rezolvare

Cele 8 poziţii în care poate sări calul sunt:

i-2 i-2 j-1j-1

i-2 i-2 j+1j+1

i-1 i-1 j-2j-2

i-1 i-1 j+2j+2

i,ji,j

i+1 i+1 j-2j-2

i+1 i+1 j+2j+2

i+2 i+2 j-1j-1

i+2 i+2 j+1j+1

Toate elementele la început sunt egale cu 0 asta însemnând că Toate elementele la început sunt egale cu 0 asta însemnând că iniţial nu s-a trecut pe la nici un pătrat. Calul porneşte de pe poziţia iniţial nu s-a trecut pe la nici un pătrat. Calul porneşte de pe poziţia aa[1,1][1,1] care va fi egal cu 1. care va fi egal cu 1.

Numărul soluţiilor notat cu ns este la început 0 şi se măreşte cu 1 Numărul soluţiilor notat cu ns este la început 0 şi se măreşte cu 1 când se apelează procedura de afişare a matricii. când se apelează procedura de afişare a matricii.

De la elementele aDe la elementele a[i,j][i,j] sare dacă poate într-una dintre cele 8 direcţii sare dacă poate într-una dintre cele 8 direcţii adică dacă trebuie să nu sară în afara tablei şi să nu mai fi trecut pe adică dacă trebuie să nu sară în afara tablei şi să nu mai fi trecut pe acolo.acolo.

Dacă sare pe una din cele 8 poziţii se procedează astfel:Dacă sare pe una din cele 8 poziţii se procedează astfel:

1. Elementele din matrice de pe acea poziţie primeşte ca valoare 1. Elementele din matrice de pe acea poziţie primeşte ca valoare pas.pas.

2. Dacă pasul la care s-a ajuns este n*n, adică pas=n*n, atunci se 2. Dacă pasul la care s-a ajuns este n*n, adică pas=n*n, atunci se afişează matricea altfel se autoapelează asupra acestui element.afişează matricea altfel se autoapelează asupra acestui element.

3. Elementele din matrice de pe acea poziţie primeşte valoarea 0.3. Elementele din matrice de pe acea poziţie primeşte valoarea 0. Pentru a ajunge de la aPentru a ajunge de la a[i,j][i,j] la una din cele 8 poziţii se folosesc la una din cele 8 poziţii se folosesc

vectorii de direcţie: pentru linie di (-2,-1,1,2,2,1,-1,-2), pentru vectorii de direcţie: pentru linie di (-2,-1,1,2,2,1,-1,-2), pentru coloană dj (1,2,2,1,-1,-2,-2,-1).coloană dj (1,2,2,1,-1,-2,-2,-1).

Implementarea algoritmului

ns - numărul soluţiilor n – numărul de linii şi coloane a – matrice pătratică i,j – indicii elementului la care s-a ajuns di – vector de poziţie pentru linie dj – vector de poziţie pentru coloană pas – pasul la care s-a ajuns k – direcţiile

i1, j1 – coordonatele noii poziţii

Programul:

Program cal;

Type sir=array[1..8] of integer; mat=array[1..20,1..20] of integer; const di: sir=(-2,-1,1,2,2,1,-1,-2); dj: sir=(1,2,2,1,-1,-2,-2,-1); Var a:mat; i,j,n,ns,pas:integer; Procedure afis_mat; Begin ns:=ns+1;

writeln (‘solutia cu numarul’, ns, ‘este:’); for i:=1 to n do begin for j:=1 to n do write(a[i,j]:3);writeln;end;

end;

procedure calul(var a:mat; i,j,pas:integer); var k,i1,j1:integer; cond:boolean;begin for k:=1 to 8 do begin i1:=i+di[k]; j1:=j+dj[k]; cond:=(i1 in [1..n]) and (j1 in [1..n]) and (a[i1,j1]=0); if cond then begin a[i1,j1]:=pas; if pas=n*n then afis_mat

else calul(a,i1,j1,pas+1); a[i1,j1]:=0; end;

end;Begin

write(‘n=‘);readln(n); For i:=1 to n do for j:=1 to n do a[i,j]:=0; a[1,1]:=1; ns:=0;

pas:=2; calul(a,1,1,pas); readln; End.