Matematické Fórum

byk7 · 19. 01. 2016 19:52

Zdravím, mějme algoritmus

Code:

input x;                    // x je prirozene cislo
p:=x;   res:=0;
while p > 0 do
   while (res+p)^2 =< x do 
      res:=res+p;
   done;
   p:=⌊p/2⌋;                // dolni cela cast
done;
output res;

Dokažte, že
1) algoritmus skončí,
2) určete, kolik zhruba udělá kroků,
3) po průběhu algoritmu je $\mathtt{res}=\lfloor\sqrt{x}\rfloor$ .

To, že skončí, je celkem zřejmé, hodnota parametru $p$ klesá, a proto jednou bude $p=0$ a vnější while cyklus skončí. S dalšími dvěma úkoly už si ale nevím moc rady.

Stýv · 19. 01. 2016 22:28

ta podmínka

Code:

while (res+p)^2 =< x do

se mi moc nezdá...

byk7 · 19. 01. 2016 23:14

Podle skript je to správně.

Stýv · 20. 01. 2016 08:16

jo už tomu rozumim. zkus si rozmyslet speciální případ, kdy p je mocnina dvou

Matematické Fórum

#1 19. 01. 2016 19:52

Analýza algoritmu

Code:

#2 19. 01. 2016 22:28

Re: Analýza algoritmu

Code:

#3 19. 01. 2016 23:14

Re: Analýza algoritmu

#4 20. 01. 2016 08:16

Re: Analýza algoritmu

Zápatí