PALMA junior
Úloha o tom, koľko pra...prarodičov má trúd

Autorské riešenie
[stiahni]

Nakreslime rodostrom nášho trúda - vyznačíme v ňom niekoľko generácií jeho predkov:

(M - včelia matka, T - trúd)

Zapíšeme si počty predkov:

Ak by sme pri skúmaní rodostromu skončili pri n=2, mohlo by nás to viesť k nesprávnemu záveru, že počet pra...prarodičov (počet pra je rovný n) sa rovná n+1. Hľadáme však inú závislosť - ak je to potrebné, vykreslime ďalších predkov nášho trúda (pre n=6).

Ak sa na vzniknutú postupnosť čísel (1, 2, 3, 5, 8, 13, 21, ...) pozrieme, zbadáme, že nový člen postupnosti je súčtom dvoch predchádzajúcich čísel: 3 = 1 + 2, 5 = 2 + 3, 8 = 3 + 5, 13 = 5 + 8, 21 = 8 + 13 atď. Ako získame prvé dve čísla, ktoré nemajú dvoch predchodcov? Tie určíme ako vopred dané a všetky ďalšie vypočítame pomocou nich.

Uvádzame jedno z možných riešení.

Samostatne sme ošetrili situácie pre n=0 a n=1. Pre ostatné prípady použijeme premenné a, b, v ktorých budú uložené hodnoty dvoch známych členov postupnosti. Do premennej z uložíme hodnotu nového vypočítaného člena (a+b). V tejto chvíli budú v premenných a, b, z uložené postupne tri po sebe idúce členy našej postupnosti. Pre ďalšie výpočty upravíme hodnoty premenných a, b tak, aby obsahovali aktuálne dva najväčšie členy postupnosti (a<b).

Počet opakovaní súvisí s počtom sčítaní, ktoré je potrebné vykonať», aby sme získali hľadanú hodnotu. Napr. pre n=4 (1, 2, 3, 5, 8) sčítame predchodcov čísla 8, teda vykonáme tri operácie sčítania. Všeobecne pre ľubovoľné n - hľadaná hodnota má n predchodcov, ktorých spočítame pomocou vykonania n-1 operácií sčítania.

Poznámka: Existuje možnosť, ako sa zaobísť bez premennej z. Cyklus opakuj potom vyzerá nasledovne:

     opakuj :n-1 [urobtu "b :a+:b
                        urobtu "a :b-:a
                        ]

Hľadaná hodnota sa po ukončení cyklu nachádza v premennej b, teda pis :z nahradíme príkazom pis :b.

Najčastejšie chyby, komentár k vašim riešeniam