B - Opäť FibonacciČasový limit: 10000000 steps, Pamäťový limit: 10000000 charsProgramovací jazyk: Turing MachinePočet bodov: 6 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] ÚlohaNa páske je uložené jedno unárne kódované prirodzené číslo X. Tvojou úlohou je zostrojiť Turingov stroj, ktorý pre daný vstup N pripraví konfiguráciu zloženú z N blokov kódujúcich postupne Fibonacciho čísla F0, F1, ... FN (teda v unárnom kódovaní). F0 = 0F1 = 1 FN+2 = FN+1 + FN VstupPáska je ohraničená z ľava. Počiatočný stav je s0. Hlava je nastavená na prvý znak, ktorý je vždy nula. Prvý znak čísla N začína napravo od nej. Naľavo od hlavy už nie je páska. Povolené páskové písmená sú len 0 a 1. Na páske sa nachádzajú práve jedno číslo N v unárnom kódovaní.VýstupUnárne kódované Fibonacciho čísla treba začať zapisovať v blokoch od F0 až po FN, oddelené vždy jednou nulou. Prvý znak bloku F0 má začínať na rovnakom mieste, ako začínal prvý znak vstupu, teda oddelený jednou nulou od ľavého okraja pásky. Vstupný blok bude teda celý nahradený výstupom. Konečný stav a pozícia hlavy po skončení vykonávania algoritmu nie je podstatná, no nikdy sa nesmie dostať mimo pásku.PrikladVstup:-t1 -ot 01 011111111 Výstup:0101101101110111101111110111111111011111111111111 Vysvetlenie:N je 7. Výstup bude teda 0, 1, 1, 2, 3, 5, 8 a 13, všetko v unárnom kódovaní. Poznámka:Vo vstupe sú uvedené parametre použité na testovanie pomocou programu palma_ts, môžete ich umiestniť do vstupného súboru. Pozor! Zmenil sa spôsob zápisu Turingovho stroja! Aktuálny spôsob nájdete popísaný v sekcii Dokumenty. |