Matematické Fórum

RonFreedom · 23. 03. 2016 11:34

Zdravím,

potřeboval bych pomoci s následujícím příkladem:
//forum.matweb.cz/upload3/img/2016-03/28668_nasobeni.PNG

A) Pomocí Věty Master Theorem jsem vypočetl složitost na: $n^{log_2(3)}$
B) Nevím, ale jak dokázat správnost algoritmu. Je tento algoritmus vůbec obecně správný?
Například číslo: 1000 do tvaru $10^N*A + B$ nikdy nerozložím, neb pro B nemohu splnit podmínku, že bude dvojciferné. Mohu tedy říct, že toto je protipříklad? A algoritmus není správný?

Díky moc.

Honzc · 23. 03. 2016 13:29

↑ RonFreedom:
Proč myslíš?
$1000=10^{2}\cdot 10+00=10^{2}\cdot 10+0$
a tedy $A=10,B=0$

RonFreedom · 23. 03. 2016 13:35

↑ Honzc:
Díky, to jsem uvažoval, ale nebyl jsem si zcela jistý zda to je možné. Takže algoritmus obecně tedy funguje. Jak tedy udělat/směrovat důkaz správnosti? Díky.

Matematické Fórum

#1 23. 03. 2016 11:34

Násobení čísel

#2 23. 03. 2016 13:29

Re: Násobení čísel

#3 23. 03. 2016 13:35

Re: Násobení čísel

Zápatí