Minimum i maximum w ciagu n-elementowym.

[stone80]

Witam!

1.Zadanie znalezienia minimum i maksimum w danym n-elementowym ciagu mozna rozwiazac stosujac
nastepujacy algorytm rekurencyjny:
Krok 1. jesli ciag ma tylko 2 elementy, to porównaj je i ustal rozwiazanie,
Krok 2. w przeciwnym przypadku, znajdz rekurencyjnie minimum i maksimum dla kazdej z \(\displaystyle{ \frac{n}{2}}\)
elementowych połówek ciagu i ustal wynik ostateczny porównujac znalezione maksima i porównujac
znalezione minima.

Narysuj drzewo wywołan rekurencyjnych rozwazanego algorytmu. Przedstaw równanie rekurencyjne
opisujace liczbe wykonanych porównan przy załozeniu, ze liczba n elementów ciagu jest potega
dwójki, n = 2k, gdzie k 2 N+. Zaproponuj rozwiazanie tego równania i udowodnij indukcyjnie jego
poprawnosc ze zwgledu na k.

Wydaje mi sie ze drzewo wywolan bedzie linia ciagla skoro jest to ciag. Jednak nie wiem jak moge to przedstawic i zapisac poszczegolne warunki.
Obliczenia:
\(\displaystyle{ 0 => (a_{1})=a_{1}}\)
\(\displaystyle{ 1 => (a_{1},a_{2})=min(a_{1},a_{2})}\)
\(\displaystyle{ 2 => (a_{1},a_{2},a_{3},a_{4})=min(min(a_{1},a_{2}), min(a_{3},a_{4}))}\)

\(\displaystyle{ a(0)=a_{1}}\)
\(\displaystyle{ a(1)= a(0) a(0)}\)

[Grzesio_]

PARI/GP

Kod: Zaznacz cały

ident()=for(i=1,depth,print1("."));

minimax(p,k)={ my(c,L,R, Res);
	depth++;
	ident();print(licz++"	("p","k,")");
	if( k-p < 2, 
		depth--;
		return( [ max(a[p],a[k]) , min(a[p],a[k]) ])
	,
		c=(p+k)2;
		L= minimax(  p, c);
		R= minimax(c+1, k);
		Res=[ max(L[1],R[1]) , min(L[2],R[2]) ];
		depth--;
		return(Res);
		
	);
}

N=30;
a=vector(N,i, random)
depth=1; licz=0
minimax(1, #a)

wynik

Kod: Zaznacz cały

..1             (1,30)
...2            (1,15)
....3           (1,8)
.....4          (1,4)
......5         (1,2)
......6         (3,4)
.....7          (5,8)
......8         (5,6)
......9         (7,8)
....10          (9,15)
.....11         (9,12)
......12        (9,10)
......13        (11,12)
.....14         (13,15)
......15        (13,14)
......16        (15,15)
...17           (16,30)
....18          (16,23)
.....19         (16,19)
......20        (16,17)
......21        (18,19)
.....22         (20,23)
......23        (20,21)
......24        (22,23)
....25          (24,30)
.....26         (24,27)
......27        (24,25)
......28        (26,27)
.....29         (28,30)
......30        (28,29)
......31        (30,30)