Naloga/Programiranje/Optimalno iskalno drevo
Iz MaFiRaWiki
< Naloga | Programiranje
[spremeni]
Naloga
V Mathematici sprogramiraj algoritem za konstrukcijo optimalnega (statičnega) iskalnega drevesa.
[spremeni]
Rešitev 1
Clear[omega1,g1,r1] omega1[p_List,q_List,i_,j_]:=If[i==j,q[[i+1]],omega1[p,q,i,j-1]+p[[j]]+q[[j + 1]]] g1[p_List,q_List,i_,j_]:=If[i==j,0,Min[Table[g1[p,q,i,k-1]+g1[p,q,k,j],{k,i + 1,j}]]+omega1[p,q,i,j]] r1[p_List,q_List,i_,j_]:=If[i==j, 0, Ordering[Table[g1[p,q,i,k-1]+g1[p,q,k,j],{k,i+1,j}],1][[1]] ]
Clear[tabela1] tabela1[p_List,q_List]:=Module[{n=Length[p]}, MatrixForm[Table[{omega1[p,q,i,j],g1[p,q,i,j],r1[p,q,i,j]},{i,0,n},{j,i,n}]] (*žal ne bo desno poravnana*) ]
[spremeni]
Rešitev 2
Clear[omega2,g2,r2] omega2[p_List,q_List,i_,j_]:=If[i==j, q[[i+1]], If[i<j, omega2[p,q,i,j-1]+p[[j]]+q[[j+1]], Null ] ] g2[p_List,q_List,i_,j_]:=If[i==j, 0, If[i<j, Min[Table[g2[p,q,i,k-1]+g2[p,q,k,j],{k,i+1,j}]]+omega2[p,q,i,j], Null ] ] r2[p_List,q_List,i_,j_]:=If[i==j, 0, If[i<j, Ordering[Table[g2[p,q,i,k-1]+g2[p,q,k,j],{k,i+1,j}],1][[1]], Null ] ]
Clear[tabela2] tabela2[p_List,q_List]:=Module[{n=Length[p]}, MatrixForm[Table[{omega2[p,q,i,j],g2[p,q,i,j],r2[p,q,i,j]},{i,0,n},{j,0,n}]] (*ta bo desno poravnana, vendar bolj nepregledna*) ]