Matematické Fórum

Predstavme si, že máme kalkulačku, ktorá má na začiatku na displeji číslo 1 a má práve dve tlačítka: [-1], ktoré zníži hodnotu na displeji o 1 ale iba ak hodnota na displeji ja väčšia ako 1 a [*3], ktoré hodnotu na displeji vynásobí tromi.

Úloha: Určite ako sa dá nejaké prirodzené číslo n získať stlačením tlačítiek čo najmenej krát.

Riešenie (moje):

if (n = 1)
  terminate
else
  while n <> 1 do
    if n mod 3 = 0
      print "[*3]"
      n := n / 3
    else
      printf "[-1]"
      n := n + 1

Pseudokód vypíše postupnosť odzadu. Hľadám postupnosť, pri ktorej sa snažím čo najmenej odčítavať a čo najviac násobiť. Preto pričítam 1, kým nedostanem číslo deliteľné číslom 3 a potom ho vydelím atď.

Mám pocit, že tento algoritmus nájde najkratšiu postupnosť ale neviem to dokázať. Vedel by mi niekto pomôcť? Ďakujem.