Rešitev: Iskanje največje luknje (Mathematica)

Iz MaFiRaWiki

Naloga: Iskanje največje luknje

 Clear[najvecjaLuknja]
 najvecjaLuknja[t_List]:=
  Module[{n,min,max,luknja,l,minI,MaxI,i,e,I,m,j},
    n=Length[t];
    min=Min[t];
    max=Max[t];
    If[min==max,Return[0]];
    
    luknja=0;
    l=N[(max-min)/(n+1)];            (*Določimo širino enega podintervala.*)
    minI=Table[Infinity, {n+1}];
    MaxI=Table[-Infinity, {n+1}];    (*V tabelah minI in MaxI bodo minimumi in maksimumi vsakega podintervala (le teh je n + 1).*)
    For[i = 1,i ≤ n,i++,
     e=t[[i]];
     I=IntegerPart[(e-min)/l] + 1;   (*I je zaporedna številka intervala, katerem je i - ti element tabele.*)
     If[I>n+1, I=n+1];
     If[e<minI[[I]], minI[[I]]=e];
     If[e>MaxI[[I]], MaxI[[I]]=e];   (*Popravimo minimum in maksimum podintervala, če je to potrebno.*)
    ];
    
    m=MaxI[[1]];
    j=1;
    While[j≤n,
     While[minI[[j]]==Infinity, j++];
     If[minI[[j]]-m>luknja, luknja=minI[[j]]-m];
     m=MaxI[[j]];
     j++;
    ];
    (*Gremo čez tabelo MaxI od prvega do predzadnjega elementa. Na vsakem koraku pogledamo razliko med maksimumom j-tega 
       podintervala in minimumom prvega intervala desno od j-tega, ki ni prazen.*)
    
    Return[luknja];
   ]
 najvecjaLuknja::usage="Funkcija najvecjaLuknja[t] največjo luknjo v tabeli t.(Luknja je razlika med po velikosti sosednjima 
   elementoma v tabeli.)";

Preizkusimo na primeru:

 Clear[t]
 t={1,10,35,14,13,2,11};
 In[32]:= najvecjaLuknja[t]
 Out[32]:= 21

Glej tudi

Osebna orodja