Rešitev: Fibonaccijevo drevo (Mathematica)

Iz MaFiRaWiki

Naloga: Fibonaccijevo drevo

V funkciji fibonaccijevoDrevo bomo uporabili naslednjo implementacija dvojiškega drevesa:

 Clear[Pripravi,DDrevo,Sestavi,Koren,LeviSin,DesniSin,JePrazno]
 Pripravi[]:= DDrevo[]
 Sestavi[p_,ls_,ds_]:=DDrevo[ls,p,ds]
 Koren[DDrevo[_,k_,_]]:=k
 LeviSin[DDrevo[l_,_,_]]:=l
 DesniSin[DDrevo[_,_,d_]]:=d
 JePrazno[d_DDrevo] := Length[d]==0

Rešitev naloge:

 Clear[fibonaccijevoZaporedje]
 fibonaccijevoZaporedje[1]:=1
 fibonaccijevoZaporedje[2]:=1
 fibonaccijevoZaporedje[n_Integer]:= fibonaccijevoZaporedje[n-1] + fibonaccijevoZaporedje[n-2]
 fibonaccijevoZaporedje::usage="Funkcija fibonaccijevoZaporedje[n] vrne n-ti člen fibonaccijevega zaporedja.";

 Clear[pristej]
 pristej[Pripravi[],a_]:=Pripravi[]
 pristej[d_DDrevo,a_]:=Sestavi[Koren[d]+a, pristej[LeviSin[d],a], pristej[DesniSin[d],a]]
 pristej::usage="Funkcija pristej[d,a] vrne drevo d, v katerem so vsi podatki povečani za a.";

 Clear[fibonaccijevoDrevo]
 fibonaccijevoDrevo[0]:=Pripravi[]
 fibonaccijevoDrevo[1]:=Pripravi[]
 fibonaccijevoDrevo[n_Integer]:=Sestavi[fibonaccijevoZaporedje[n],fibonaccijevoDrevo[n-1],
   pristej[fibonaccijevoDrevo[n-2],fibonaccijevoZaporedje[n]]]
 fibonaccijevoDrevo::usage="Funkcija fibonaccijevoDrevo[n] vrne n-to fibonaccijevo drevo.";

Preizkusimo na primeru:

 In[22]:= fibonaccijevoDrevo[6];
 Out[22]:= DDrevo[DDrevo[DDrevo[DDrevo[DDrevo[DDrevo[],1,DDrevo[]],2,DDrevo[]],3,DDrevo[DDrevo[],4,DDrevo[]]],5,DDrevo[DDrevo[
  DDrevo[],6,DDrevo[]],7,DDrevo[]]],8,DDrevo[DDrevo[DDrevo[DDrevo[],9,DDrevo[]],10,DDrevo[]],11,DDrevo[DDrevo[],12,DDrevo[]]]]

Če pa pred primerom potrdimo še naslednjo funkcijo Risi, nam Mathematica drevo tudi nariše.

 Clear[RisiDrevo,Risi]
 RisiDrevo[d_]:=If[!JePrazno[d], Show[Graphics[Risi[d,0,{0,0}]]]]
 Risi[d_,n_,{x_,y_}]:=
   If[JePrazno[d],{},Join[{Point[{x,y}],Text[Koren[d],{x+0.1,y}]},
       If[JePrazno[LeviSin[d]], {}, {Line[{{x,y},{x-2^(-n),y-1}}]}], If[JePrazno[DesniSin[d]], {}, {Line[{{x,y},{x+2^(-n),y-1}}]}],
       Risi[LeviSin[d],n+1,{x-2^(-n),y-1}], Risi[DesniSin[d],n+1,{x+2^(-n),y-1}]
      ]
   ]

 (* Poskrbimo, da vedno dobimo izrisano drevo. *)
 Format[d_DDrevo]:=RisiDrevo[d]

Glej tudi

Osebna orodja