Ve sbírkách matematických úloh bývají takovéto úlohy značeny *. Dnes ale i ty nejběžnější hotely mívají *** a tak jsem ji tak neoznačil.
V některých případech je vhodné zakódovat přirozená čísla (v antické módu ‑ tedy > 0)
pomocí Fibonacciovy posloupnosti ‑ Zeckendorfův theorém.
Vyberou se vždy největší členové Fibonacciovy posloupnosti, jejichž součet bude roven zakódovanému číslu.
Přesněji: od kódovaného čísla se odečte nejmenší jemu ≧ člen Fibonacciovy posloupnosti. A totéž opakovaně od onoho kódovaného čísla
zmenšovaného postupně odečtáním dokud není rovno 0.
V kódu je za každého člena postupně vzrůstající Fibonacciovy posloupnosti účastněného v právě popsaném
součtu 1 a za ty vynechané 0.
Vlastnosti takovéhoto kódu jsou:
-
na konci je vždy 1.
-
je v něm vždy nejméně jedna 1.
-
nemohou v něm být dvě 1 za sebou.
Kdyby byly, pak by to byly 1
přináležející Fk-2 a Fk-1 a pak by místo nich měla být
jen jedna 1 patřící Fk pro příslušné
k.
-
z předchoze zmíněného vyplývá, že po poslední 1 můžeme
přidat další 1 jakožto příznak konce zakódovaní jednoho čísla
a začátek dalšího v bitovém proudu.
Napište rekursivní funkci, která bude onen kód postupně tisknout. Rekursivní i proto, protože výpočet probíhá od největšího (nejmenší ≧ x) člena dolů,
ale tisknout se musí od nejmenšího (patřícího k F2 ≡ 1).
Příklad běhu programu s požadovanou funkcí:
Zadejte: 1
Cislo 1 je zakodovano: 1
Zadejte: 2
Cislo 2 je zakodovano: 01
Zadejte: 3
Cislo 3 je zakodovano: 001
Zadejte: 4
Cislo 4 je zakodovano: 101
Zadejte: 12
Cislo 12 je zakodovano: 10101
Zadejte: 33
Cislo 33 je zakodovano: 1010101
Zadejte: 66
Cislo 66 je zakodovano: 001010001
Zadejte: 100
Cislo 100 je zakodovano: 0010100001
Zadejte: 144
Cislo 144 je zakodovano: 00000000001
Zadejte: 255
Cislo 255 je zakodovano: 100000100001
Poznámka:
V binárním kódováním čísel se musí volit pevná velikost bitového řetězce ≡ k.
Binárním kódování: x = a12k-1 + a22k-2 + … +
ai2k-i + … + ak20, kde ai ∈ {0, 1}
má dvojkové ‑ binární ‑ vyjádření čísla x (v pravidelné posiční soustavě se základem 2)
a1a2…ai…ak.
Délka bitového řetězce k musí být alespoň tak velká
(⌈log2max(x)⌉), aby se zakódovalo největší číslo v danném kontextu.
V případě, že ono maximum je o hodně větší než průměr kódovaných čísel, pak je velké část binárních k-tic
vyplněna levostrannými 0mi.
U nahoře uvedeného kódování pomocí Fibonacciovy posloupnosti platí: x = b1F2 + b2F3 + … +
biFi+1 + … + bkFk+1, kde bi ∈ {0, 1}.
Toto kódování je sice ∽1.5 krát delší než binární, ale pro menší čísla je na délku šetrnější. Jak geometrická, tak Fibonacciova posloupnost
rostou exponenciálně, ale ta členů Fibonacciovy posloupnosti je méně strmá ‑ s quocientem ∽1.6 (zlatý řez).
Musím se pochválit za vzorně provedenou poznámku pod čarou.