C - Fibonacciho číslo

Časový limit: 10000000 steps, Pamäťový limit: 10000000 chars

Programovací jazyk: Turing Machine

Počet bodov: 8

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Úloha

Na páske je uložené jedno unárne kódované prirodzené číslo n. Vypočítajte F(n), Fibonacciho číslo, keď platí, že:

F(0)=0
F(1)=1
F(n)=F(n-1)+F(n-2)

Vstup

Pá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ádza práve jedno číslo n v unárnom kódovaní.

Výstup

Na páske treba ponechať počet jednotiek rovnajúci sa F(n). Nemusia tvoriť súvislý blok. Nie je dôležité, v akom stave skončí stroj a kde zastane hlava.

Priklad 1

Vstup:

-t1 -oc
01
01

Výstup:

Vysvetlenie:

F(0)=0, na páske nemajú teda zostať žiadne jednotky.

Priklad 2

Vstup:

-t1 -oc
01
01111111

Výstup:

Vysvetlenie:

F(6)=8, na páske má teda zostať presne osem jednotiek.

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.

Turing 2009