Rešitev: Uredi števila s pomočjo dveh vrst

Iz MaFiRaWiki

Naloga: Uredi števila s pomočjo dveh vrst

1) V našo vhodno vrsto bomo najprej vstavil "stražarja", da ga bomo lahko smiselno uporabljali.

2) Potem bomo iz naše vhodne vrste premikali elemente (brisali čelo v vhodni vrsti in ga kot rep vstavili v željeno vrsto). Prvi element prestavimo v pomožno vrsto, vsakega naslednjega pa:

-če je manjši (ali enak) od repa pomožne vrste, ga prestavimo v pomožno vrsto;

-če je večji od repa pomožne vrste ga prestavimo v vhodno vrsto;

-ko pridemo do stražarja, preverimo rep vhodne vrste in:

2a) če rep ni stražar (=stražar ni edini element vrste) , vse elemente pomožne vrste prestavimo v vhodno vrsto, potem v vhodno vrsto prestavimo še stražarja in ponovimo postopek 2);

2b) če je tudi rep stražar (=stražar je edini element vrste) zaključimo postopek 2);

3) Potem le še izpišemo pomožno vrsto, ki je naša rešitev;


Primeri so najprej prikazani na prosti implementaciji vrste, kasneje pa še na implementaciji vrste s seznamom, da lahko lažje podajamo in pregledujemo našo vrsto.


Povezava do originalnega zvezka Mathemetice: Uredi stevila s pomocjo dveh vrst.nb


Prosta Implementacija vrste:

In[1]:= Clear[Pripravi,Vstavi,JePrazna,Celo,Rep, Odstrani];
        JePrazna[Pripravi[]]:=True;
        JePrazna[Vstavi[v_,e_]]:=False;
        Celo[Pripravi[]]:=Null;
        Celo[Vstavi[v_,e_]]:=If[JePrazna[v],e,Celo[v]];
        Rep[Pripravi[]]:=Null;
        Rep[Vstavi[v_,e_]]:=e;
        Odstrani[Pripravi[]]:=Pripravi[];
        Odstrani[Vstavi[v_,e_]]:=If[JePrazna[v],Pripravi[],Vstavi[Odstrani[v],e]];

Pomožne funkcije:

In[10]:=Premakni12:=( v2=Vstavi[v2, Celo[v1]]; v1=Odstrani[v1];)
        Premakni12::usage  = "Premakni12 v vrsti v1 odstrani svoje čelo in ga vstavi na rep v vrsto v2.";

        Premakni21:=( v1=Vstavi[v1, Celo[v2]]; v2=Odstrani[v2];)
        Premakni21::usage  = "Premakni21 v vrsti v2 odstrani svoje čelo in ga vstavi na rep v vrsto v1.";

        Premakni11:=( v1=Vstavi[v1, Celo[v1]]; v1=Odstrani[v1];)
        Premakni11::usage  = "Premakni11 v vrsti v1 odstrani čelo in ga ponovno vstavi na svoj rep.";

        Premikaj1211 := While [Celo[v1] =!= Stražar,
    				If[¬ NumberQ[Celo[v1]], Print["Ni vrsta ali vsaj en element 
					vrste ni število -> ne morem nadaljevati."] ; Abort[];];
    				If[Celo[v1] ≤ Rep[v2], Premakni12;, Premakni11;]
    				]
        Premikaj1211::usage  = "Premikaj1211 iz vrste v1 premika elemente v vrsto v2 
		(če je čelo vrste v1 manjše od repa vrste v2) oziroma nazaj v vrsto v1 (če čelo vrste v1 
		ni manjše od repa vrste v2). Funkcija ne stori nič, če je čelo vrste v1 stražar. Funkcija 
		se prekine in izpiše napako, če čelo vrste v1 ni število (za števila štejemo vse 
		elemente, ki jih prepozna funkcija NumberQ) ali če je vrsta podana napravilno.";

Funkcija UrediVrsto:

In[18]:=UrediVrsto[v_]:=(
        v1=Vstavi[v,Stražar];
        v2=Pripravi[];
        Premakni12;
        Premikaj1211;
        While[Rep[v1]=!=Stražar,
      	     While[v2=!=Pripravi[],
        	   Premakni21;
        	   ];
      	     Premakni11;
      	     While[Celo[v1]=!=Stražar,
        	  Premakni12; 
        	  Premikaj1211;
        	  ];
      	     ] ;
        v2
        )

        UrediVrsto::usage = "UrediVrsto dano vrsto števil uredi po velikosti. Največji število 
		je na čelu vrste, najmanjše pa na repu. Če podana vrsta vsebuje element, ki 
		ni število, funkcija vrne napako.";

Primeri pri prosti implementaciji:

In[20]:=test= Pripravi[];
        test=Vstavi[test, 4];
        test=Vstavi[test, 2];
        test=Vstavi[test, 8];
        test=Vstavi[test, 1];
        test=Vstavi[test, 6];
        test=Vstavi[test, 5];
        test=Vstavi[test, 3];
        test=Vstavi[test, 7]
        UrediVrsto[test]

Out[28]=Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Pripravi[],4],2],8],1],6],5],3],7]
Out[29]=Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Pripravi[],8],7],6],5],4],3],2],1]
In[30]:=Celo[UrediVrsto[test]]
        Rep[UrediVrsto[test]]

Out[30]=8
Out[31]=1
In[32]:=test1= Pripravi[];
        test1=Vstavi[test1, 8];
        test1=Vstavi[test1, 6];
        test1=Vstavi[test1, 2];
        test1=Vstavi[test1, 11];
        test1=Vstavi[test1, 10];
        test1=Vstavi[test1, 3];
        test1=Vstavi[test1, 12];
        test1=Vstavi[test1, 5];
        test1=Vstavi[test1, 1];
        test1=Vstavi[test1, 7];
        test1=Vstavi[test1, 4];
        test1=Vstavi[test1, 56];
        test1=Vstavi[test1, 34];
        test1=Vstavi[test1, 43];
        test1=Vstavi[test1, 65];
        test1=Vstavi[test1, 47];
        test1=Vstavi[test1, 28];
        test1=Vstavi[test1, 98];
        test1=Vstavi[test1, 456];
        test1=Vstavi[test1, 35587689];
        test1=Vstavi[test1, -30];
        test1=Vstavi[test1, 9]
        UrediVrsto[test1]

Out[54]=Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi
		[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[
		Pripravi[],8],6],2],11],10],3],12],5],1],7],4],56],34],43],65],47],28],98],456],
		35587689],-30],9]
Out[55]=Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi
		[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[
		Pripravi[],35587689],456],98],65],56],47],43],34],28],12],11],10],9],8],7],6],5]
		,4],3],2],1],-30]
In[56]:=Celo[UrediVrsto[test1]]
        Rep[UrediVrsto[test1]]

Out[56]=35587689
Out[57]=-30

Implementacija vrste s seznamom:

In[58]:=Clear[Pripravi,Vstavi,JePrazna,Celo,Rep, Odstrani];
        Pripravi[]:={};
        Vstavi[v_, e_]:=Prepend[v,e];
        JePrazna[{}]:=True;
        JePrazna[{___}]:=False;
        Celo[v_]:=Last[v];
        Rep[v_]:=v[[1]];
        Odstrani[v_]:=Drop[v,-1];

Primeri pri implementaciji s seznamom:

In[66]:=test1= Pripravi[];
        test1=Vstavi[test1, 8];
        test1=Vstavi[test1, 6];
        test1=Vstavi[test1, 2];
        test1=Vstavi[test1, 11];
        test1=Vstavi[test1, 10];
        test1=Vstavi[test1, 3];
        test1=Vstavi[test1, 12];
        test1=Vstavi[test1, 5];
        test1=Vstavi[test1, 1];
        test1=Vstavi[test1, 7];
        test1=Vstavi[test1, 4];
        test1=Vstavi[test1, 9]
        UrediVrsto[test1]

Out[78]={9,4,7,1,5,12,3,10,11,2,6,8}
Out[79]={1,2,3,4,5,6,7,8,9,10,11,12}
In[80]:=test2={3,4,7,89,4,3,6,5, 8,0,65,2,1,5,7,9,0, 3658, 346758265, 76498663, 7476,
		358, 863, 863, 952, 582, 784, 74, 6, 276, 782, 9, 15, 87, 57, 27,84, 765, 
		36, 76, 14, 768, 35, 87, 4, 57, 325346, 68 ,465 , 564};
        UrediVrsto[test2]

Out[81]={0,0,1,2,3,3,4,4,4,5,5,6,7,7,8,9,9,14,15,27,35,36,57,57,65,68,74,76,76,84,87,
	87,89,276,358,465,564,582,765,768,782,784,863,863,952,3658,7476,325346,76498663,346758265}
In[82]:=test3={5645,7657,5435, 434, 6, -565, 0, 5.678, 89 };
        UrediVrsto[test3]

Out[83]={-565,0,5.678,6,89,434,5435,5645,7657}
In[84]:=Celo[UrediVrsto[test3]]
        Rep[UrediVrsto[test3]]

Out[84]=7657
Out[85]=-565
In[86]:=test4={5645, bla, 4545};
        UrediVrsto[test4]

Out[87]=Ni vrsta ali vsaj en element vrste ni število -> ne morem nadaljevati.
        $Aborted


Glej tudi

Osebna orodja