Rešitev: Trikotnik števil (Mathematica)

Iz MaFiRaWiki

Naloga: Trikotnik števil

(*trikotnike bom sprogramiral kot spodnje-trikotne matrike*)

aij[l_List,i_Integer,j_Integer]:=l[[i]][[j]] (*element v i-ti vrstici in j-tem stolpcu matrike*)

vsota[l_List,1,j_Integer]:=aij[l,Length[l],j] (*elementi v n-ti vrstici*)

vsota[l_List,i_Integer,j_Integer]:=vsota[l,i,j]=aij[l,Length[l]+1-i,j]+Max[vsota[l,i-1,j],vsota[l,i-1,j+1]]

(*največja vsota vrige, ki se začne v (n+1-i)j-tem koeficientu matrike (začel sem v spodnji vrstici in nato potoval proti vrhu)*)

s[l_List,1,j_Integer]:={aij[l,Length[l],j]} (*elementi v n-ti vrstici*)

s[l_List,i_Integer,j_Integer]:=s[l,i,j]=If[vsota[l,i-1,j]>vsota[l,i-1,j+1], Prepend[s[l,i-1,j],aij[l,Length[l]+1-i,j]],Prepend[s[l,i-1,j+1],aij[l,Length[l]+1-i,j]]]

(*vriga, ki se začne v (n+1-i)j-tem koeficientu matrike in ima največjo vsoto*)

maxVsota[l_List]:={s[l,Length[l],1],vsota[l,Length[l],1]} (*rezultat je veriga, ki se začne v zgornjem levem elementu*)

Primeri

A={{1,0,0,0,0},{2,3,0,0,0},{26,5,6,0,0},{11,8,9,10,0},{11,12,13,1,15}};

MatrixForm[A]

image:matrika1.JPG

maxVsota[A]

{{1,2,26,11,12},52}

Kako sprogramiramo poljuben trikotnik z naravnimi števili od 1 do 100?

stevilo[i_Integer, j_Integer]:= If[j ≤ i, Random[Integer, {1, 100}], 0]

trikotnik[n_Integer]:=Table[Table[stevilo[i, j], {j, n}], {i,n}] (*spodnje-trikotna matrika, ki ima od diagonale navzdol naključna števila med 1 in 100*)

trikotnik=trikotnik[10];

MatrixForm[trikotnik]

image:matrika2.JPG

maxVsota[trikotnik]

{{64,84,92,80,79,79,88,83,87,78},814}

Osebna orodja