PALMA junior
Úloha o tom, koľko torty ostalo Jankovi

Autorské riešenie
[stiahni]

Pri riešení tejto úlohy sa nezaobídeme bez znalosti práce so zlomkami - budeme ich násobiť, sčítavať, odčítavať.

Najprv sa zorientujme v textových riadkoch, ktorých je na obrazovke hneď niekoľko:

• riadky c1 a m1 reprezentujú zlomok c1/m1, ktorý vyjadruje časť torty od tety Anky,
• riadky c2 a m2 reprezentujú zlomok c2/m2, ktorý vyjadruje časť torty, ktorá bola na stole u tety Betky pri príchode Janka,
• riadky c3 a m3 reprezentujú zlomok c3/m3, ktorý vyjadruje časť zo zvyšku torty od tety Betky pre Janka,
• riadky c4 a m 4 reprezentujú zlomok c4/m4, ktorý vyjadruje časť Jankovej "výslužky", s ktorom sa podelil s tetou Cecilkou,
• riadky vc a vm reprezentujú zlomok vc/vm, ktorý vyjadruje časť torty, ktorú Janko priniesol domov. Hodnoty týchto riadkov vypočítame na základe hodnôt predchádzajúcich riadkov.

Výpočet najprv popíšme slovne aj pomocou matematických operácií, použijeme premenné, ktoré sa objavia v procedúre:

• Janko od tety Anky dostal c1/m1 z celej torty.
• Od tety Betky dostal Janko (c2/m2).(c3/m3) z celej torty. Vynásobením dvoch zlomkov získame nový zlomok c5/m5, ktorý vyjadruje, akú časť celej torty získal Jano u tety Betky.
• Zatiaľ má teda (c1/m1) + (c5/m5) z celej torty. Sčítaním týchto dvoch zlomkov získame nový zlomok c6/m6, ktorý vyjadruje, akú časť celej torty získal Janko spolu od tety Anky a tety Betky.
• U tety Cecilky vybral z balíčka (c4/m4).(c6/m6) z celej torty. Výsledkom tohto súčinu je zlomok c7/m7, ktorý vyjadruje, akú časť celej torty zjedli Janko a teta Cecilka.
• Jankovi v balíčku zostalo z torty (c6/m6) - (c7/m7). Výsledkom rozdielu je zlomok c8/m8, ktorý vyjadruje časť celej torty, ktorú si Janko priniesol domov.

Keďže výsledok máme vypísať v tvare zlomku, počas výpočtu budeme pracovať s čitateľmi a menovateľmi zlomkov.

Po správnom výpočte založenom na predchádzajúcom postupe získame zlomok c8/m8, ktorý vyjadruje časť celej torty, ktorú Jano priniesol domov. Podľa zadania úlohy musíme upraviť tento zlomok na základný tvar.

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

Použili sme novú premennú d. Jej hodnotou sa budeme snažiť deliť hodnotu čitateľa (c8) a menovateľa (m8) (samozrejme, ak ňou budú zároveň obidve hodnoty deliteľné bezo zvyšku).

Potrebujeme ohraničiť hodnotu d, ktorú budeme postupne zvyšovať. Tou hranicou bude menšia z hodnôt c8 a m8, ktorú budeme uchovávať v premennej mensi.

Cyklus ukončíme, ak hodnota premennej d presiahne hodnotu premennej mensi. Inak zistíme, či sú čitateľ i menovateľ zlomku deliteľné hodnotou premennej d. Ak áno, predelíme ich a určíme novú hodnotu premennej mensi. Ak čitateľ a menovateľ nie sú deliteľné hodnotou premennej d, zväčšíme hodnotu o 1.

Možno sa pýtate, prečo nezväčšujeme hodnotu premennej d aj po predelení čitateľa a menovateľa. Odpoveď je jednoduchá - aj po predelení hodnotou d môžu byť čitateľ a menovateľ opäť deliteľné hodnotou d.

Možné vylepšenie - Euklidov algoritmus

Pomocou Euklidovho algoritmus vieme nájsť najväčšieho spoločného deliteľa dvoch čísel A, B. Postup je založený na postupnej úprave hodnôt A a B postupným odpočítavaní vždy menšej z hodnôt A a B od väčšej. Tento postup sa opakuje, kým sa hodnoty A a B nerovnajú. Po ukončení tohto postupu je hodnota A (a aj B) hľadaným najväčším spoločným deliteľom.

Príklad: V ľavej časti môžete sledovať hľadanie najväčšieho spoločného deliteľa čísel 42 a 12, v pravej časti čísel 7 a 2.

Zlomok c8/m8 teda upravíme tak, že nájdete najväčšieho spoločného deliteľa čísel c8, m8. Samozrejme, ak je čitateľ rovný nule, nie je potrebné hľadať najväčšieho spoločného deliteľa. V opačnom prípade použijeme pomocné premenné a, b, ktoré budú na začiatku obsahovať hodnoty premenných c8 a m8. Robíme to preto, lebo v závere budeme ešte potrebovať pôvodné hodnoty c8 a m8.

Výhodou tohto algoritmu je to, že základný tvar zlomku získame podstatne rýchlejšie.

Úpravou Euklidovho algoritmu získame ešte rýchlejší postup riešenia úlohy. Namiesto odčítania použijeme zvyšok po delení dvoch čísel. Deliť budeme vždy väčšie číslo menším dovtedy, kým jedna z premenných nenadobudne hodnotu 0.

Ak porovnáme tabuľku s príkladom postupu klasického Euklidovho algoritmu s touto novou tabuľkou, vidíme, že už pri malých číslach dosahujeme výrazne zrýchlenie. Pri číslach, ktoré vznikajú v našej úlohe, je tento rozdiel ešte výraznejší.

Ak pozorne študujete autorské riešenia, určite si spomeniete na podobnú výmenu hodnôt dvoch premenných z úlohy o predkoch trúda - dokážete výmenu hodnôť premenných vacsi a mensi zrealizovať bez použitia pomocnej premennej p?

Vaše zaujímavé riešenia a najčastejšie chyby

Niektorí z vás zaviedli nové premenné, do ktorých uložili hodnoty textových políčok - nebolo to potrebné, mohli ste pracovať priamo s c1, m1 atď.

Pri hľadaní výsledného zlomku ste zvládli výpočet jeho menovateľa, pri čitateli sa objavili preklepy (namiesto mínus ste napísali plus) alebo ste pri jeho výpočte používali delenie (/) - výsledkom však už potom bolo nesprávne číslo.

Do hľadania najväčšieho spoločného deliteľa sa pustili len niekoľkí z vás. Použili ste postup, ktorý nájdete v autorskom riešení pod názvom "Euklidov postup hľadania NSD". Jeden tím dokonca použil vylepšenie tohto postupu (namiesto odpočítavania delil). Zaujímavé je, že niektoré tímy použili pri zápise tohto postupu rekurziu - úloha je vyriešená správne, no ak je možné vyriešiť ju bez použitia rekurzie, skúste to. V tomto prípade je možné nahradiť rekurziu obyčajným cyklom.

Náznak postupu, o ktorom sme predpokladali, že bude najčastejší, sa objavil v jednom riešení (postupné skúmanie deliteľnosti čitateľa a menovateľa číslami 2, 3, 5 atď.), len nebol úplne dotiahnutý do úspešného konca.