Matematická olympiáda – kategorie P

Řešení úloh domácího kola 49. ročníku

Tento pracovní materiál není určen primárně přímo studentům - účastníkům olympiády. Má pomoci učitelům na školách při přípravě konzultací a pracovních seminářů pro řešitele soutěže, členům oblastních výborů MO slouží jako podklad pro opravování úloh domácího kola MO kategorie P. Studentům je možné tyto komentáře poskytnout až po termínu stanoveném pro odevzdání řešení úloh domácího kola MO kategorie P jako informaci, jak bylo možné úlohy správně řešit, a pro jejich odbornou přípravu na účast v oblastním kole soutěže.

P-I-1

Pro výrobní operaci i označíme jako hi nejkratší čas od spuštění výroby, v němž může být operace i dokončena. Protože v továrně lze vykonávat najednou libovolný počet výrobních operací, můžeme výrobu uspořádat tak, že každá operace i bude skutečně dokončena v čase hi. Na zhotovení celého výrobku potřebujeme dokončit všechny stanovené výrobní operace, takže výrobek je možné dokončit nejdříve v čase max {h1, h2, ..., hn}.

Zbývá nám spočítat čas hi. Jestliže výrobní operace i nemá žádné předcházející operace, můžeme ji okamžitě spustit. Hodnota hi je v takovém případě přímo rovna délce trvání operace i. Pokud operace i má nějaké předcházející operace p1,p2,...,pk, je třeba vykonat nejprve tyto předcházející operace. Výrobní operace i může začít nejdříve v čase, který je maximem z časů hp1, hp2,..., hpk. Když víme, kdy operace i začne a známe délku jejího trvání, umíme triviálně spočítat, kdy skončí.

Hodnoty hi budeme počítat rekurzívně. Program obsahuje rekurzívní funkci urci_cas(i), která spočítá hodnotu hi. Pokud operace i nemá předchůdce, bude to jednoduše čas jejího trvání. Jestliže operace i má nějaké předchůdce, spustí se funkce urci_cas pro každého předchůdce operace i, z takto získaných časů se vezme maximum a k němu se připočítá čas trvání operace i. Navíc, jakmile vypočítáme hodnotu hi pro nějaké i, uložíme si ji do pomocného pole. Když později zavoláme funkci urci_cas pro stejné i znovu, tato funkce už nebude znovu počítat, ale jednoduše vrátí už vypočítanou hodnotu z pole.

Nejprve dokážeme, že popsaný program vždy skončí. Předpokládejme, že bychom počítali nějakou hodnotu hi a při jejím výpočtu bychom potřebovali vypočítat nějakou hodnotu hj1 pro předcházející operaci j1. Při vśpočtu hj1 bychom potřebovali vypočítat nějakou hodnotu hj2 a tak bychom se vnořovali hlouběji a hlouběji, až bychom zjistili, že k výpočtu nějakého hjk potřebujeme znát hi. To by způsobilo nekonečné volání rekurze. Takovýto případ však může nastat jedině tehdy, jestliže není možné vykonat operaci i, protože operace i se může provést až po skončení j1 a j1 lze provést až po skončení j2 atd., a jk je možné vykonat až po skončení i. Dostali jsme tedy cyklus, takže i není možné provést vůbec. V zadání je však uvedeno, že všechny operace lze provést, takže tento případ nemůže nastat a náš algoritmus vždy skončí.

Na závěr zhodnotíme výpočtovou složitost algoritmu. Předpokládejme, že pro každou operaci máme seznam předcházejících operací uložen ve spojovém seznamu. Označme n počet výrobních operací a m celkový počet předcházejících operací pro všechny operace v technologickém plánu výrobku. V první části algoritmu načítáme a ukládáme potřebné údaje. Tato část má časovou složitost O(m+n).

V druhé části algoritmu zavoláme funkci urci_cas(i) pro každé i od 1 do n. V rámci každého takového volání se funkce může ještě dále rekurzívně volat. Funkci urci_cas(i) voláme pro každé i jednou z hlavní části algoritmu a pro každou operaci, pro níž je operace i předchůdcem, tuto funkci opět zavoláme. Celkem se tedy vykoná m+n volání funkce urci_cas. Pro každou hodnotu i se ale hodnota urci_cas(i) počítá pouze jednu a při dalších voláních se jen najde výsledek v poli v konstantním čase. Máme tedy přesně m volání funkce urci_cas, která proběhnou v konstantním čase. Zbývajících n volání počítá hodnotu. Při volání, které počítá hodnotu, se projde seznam všech předcházejících operací a hledá se maximum z časů. Délka takovéhoto volání je tedy úměrná počtu předcházejících operací (pokud zanedbáme čas potřebný na vnořená rekurzivní volání). Celkový čas všech n volání, která počítají hodnotu, bude tedy O(m+n). Všech m+n volání bude také trvat dobu O(m+n). Celková časová složitost algoritmu je proto O(m+n). Paměťová složitost je rovněž O(m+n).

Dvě poznámky na závěr. Pokud bychom vypočítané hodnoty ve funkci urci_cas neukládali do pole, ale počítali bychom je vždy znovu, dostaneme algoritmus s exponenciální časovou složitostí. Všimněte si, že úlohu je možné jednoduše přetransformovat do teorie grafů - operace budou představovat vrcholy grafu a hrany (orientované) povedou vždy od operace k jejímu předchůdci. Úkolem je potom nalézt orientovanou cestu s největším součtem časů ve vrcholech. Algoritmus, který jsme uvedli, je v grafové terminologii pouze jednoduchou modifikací prohledávání do hloubky.

program P_I_1; type ppostupy=^postupy; postupy=record {seznam operací} postup:integer; dalsi:ppostupy; end; var predpostupy:array[1..100] of ppostupy; {seznam předcházejících operací pro každou výrobní operaci} cas,hotovo:array[1..100] of integer; {cas[i] je čas, kolik trvá operace i, hotovo[i] je nejnižší čas, kdy může být operace i hotova} n:integer; {počet operací} procedure nacti; var t:text; i,j:integer; novy:ppostupy; begin assign(t,'TOVARNA.IN'); reset(t); readln(t,n); {načtení počtu operací} for i:=1 to n do begin read(t,cas[i]); {načtení času jednotlivých operací} predpostupy[i]:=nil; {seznam předcházejících operací} read(t,j); while j<>-1 do begin new(novy); {vložit operaci j do seznamu} novy^.postup:=j; novy^.dalsi:=predpostupy[i]; predpostupy[i]:=novy; read(t,j); end; end; close(t); end; function urci_cas(postup:integer):integer; {vrátí nejmenší čas, v němž může být operace hotova} var max,kdy:integer; pom:ppostupy; begin if hotovo[postup]=-1 then begin {pokud jsme čas ještě nepočítali, vypočítáme ho a uložíme do pole "hotovo", jinak neděláme nic} max:=0; pom:=predpostupy[postup]; while pom<>nil do begin kdy:=urci_cas(pom^.postup); if kdy>max then max:=kdy; pom:=pom^.dalsi; end; {max je čas, kdy jsou hotove všechny předcházející operace} hotovo[postup]:=cas[postup]+max; end; urci_cas:=hotovo[postup]; end; procedure vypocitej; var i,max,kdy:integer; t:text; begin for i:=1 to n do {inicializace} hotovo[i]:=-1; max:=0; {zjistíme, kdy skončí poslední operace} for i:=1 to n do begin kdy:=urci_cas(i); if kdy>max then max:=kdy; end; assign(t,'TOVARNA.OUT'); rewrite(t); writeln(t,max); close(t); end; begin nacti; vypocitej; end.

P-I-2

Je známo více algoritmů na konstrukci řetězce obsahujícího všechny permutace znaků dané abecedy jako podřetězce. Nejprve uvedeme příklad jednoduchého algoritmu, který pro N-prvkovou abecedu sestrojí řetězec délky N2-N+1. Potom ukážeme komplikovanější algoritmus, který sestrojí řetězec délky pouze N^2-2N+4 (pro N>= 3). Není známo, zda existuje i nějaký kratší řetězec (existuje dolní odhad počtu znaků takovéhoto řetězce, tento odhad je však nižší než N2-2N+4).

Nejprve si ukážeme jednodušší konstrukci řetězce. Mějme N-prvkovou abecedu {a1, a2, ..., aN}. Řetězec bude tvořen N-1 úseky tvaru a1a2...aN a ukončen bude znakem a1. Například pro abecedu {a,b,c} sestrojíme řetězec abcabca. Tento řetězec obsahuje celkem (N-1) N +1 = N2 - N +1 znaků. Pro N=15 tedy dostáváme řetězec délky 211.

Zbývá dokázat, že takto sestrojený řetězec skutečně obsahuje každou permutaci znaků abecedy jako vybraný podřetězec. Rozdělíme si tedy řetězec na N-1 úseků tvaru a2a3...aN. Mezi každými dvěma těmito úseky, stejně jako za posledním a před prvním z nich, se nachází znak a1. Vezměme nyní libovolnou permutaci znaků abecedy. Nejprve z této permutace vynecháme znak a1. Zbytek permutace je jistě vybraným podřetězcem našeho řetězce, neboť z každého úseku tvaru a2a3...aN můžeme vybrat právě jeden znak tak, abychom z j-tého úseku vybrali j-tý znak permutace různý od a1.

Nechť je nyní znak a1 umístěn v permutaci na i-tém místě, tzn. před ním leží i-1 znaků. Potom z řetězce vybereme v pořadí i-tý výskyt znaku a1. Před ním se nachází i-1 úseků tvaru a2a3...aN, a tedy a1 bude i ve vybraném podřetězci na i-tém místě. Dokázali jsme, že pro libovolnou permutaci znaků abecedy můžeme nalézt takový vybraný podřetězec našeho řetězce, který se této permutaci rovná.

Nyní si popíšeme jinou, složitější konstrukci. Budeme vytvářet posloupnost řetězců T(1), T(2), T(3),..., přičemž T(N) obsahuje všech N! permutací N znaků jako podřetězce. Ukážeme si způsob, jak z T(N) sestrojit T(N+1) (pro N >= 3).

Řetězce T(1), T(2) a T(3) zvolíme pevně: T(1)=a1, T(2)=a1a2a1 a T(3)=a1a3a2a1a3a1a2. Jsou to nejkratší možné řetězce pro N=1, 2, 3 (to lze snadno dokázat ověřením všech možností).

Mějme nyní abecedu {a1, a2,... ,aN}. K řetězci T(N) vytvoříme posloupnost základních bodů. První základní bod řetězce T(N) je index prvního výskytu znaku a1 v T(N). Pro i>1 je i-tým základním bodem index prvního výskytu znaku ai za (i-1)-ním základním bodem v řetězci. Například v T(3)=a1a3a2a1a3a1a2 je posloupnost základních bodů (1,3,5).

Algoritmus pro konstrukci řetězce T(N) z řetězce T(N-1):

  1. Pro každé i=2,3,..., N-1 vsunout těsně před i-tý základní bod řetězce T(N-1) znak aN.
  2. Na konec takto vzniklého řetězce připojit úsek
    a2,a3,... ,aN-3,aN,a1,aN-1.
Podle prvního bodu algoritmu jsme vložili N-2 znaků a podle druhého bodu jsme vložili N-1 znaků. Celkově se tedy řetězec prodloužil o 2N-3 znaků. Všechny základní body řetězce T(N-1) budou i základními body řetězce T(N) (jen se posunou kvůli vsouvání znaků aN podle bodu 1) a N-tým základním bodem se stane znak aN přidaný v bodě 2. Například pro N=4 dostáváme pomocí tohoto algoritmu T(4)= a1a3a4a2a1a4a3a1a2a4a1a3.

Řetězec T(N) sestrojený naším algoritmem (pro N >= 3) má délku N2-2N+4. Toto tvrzení dokážeme matematickou indukcí. Délka řetězce T(3) je 7, což je rovno 32-2x3 + 4. Předpokládejme nyní, že délka T(N-1) je (N-1)2-2(N-1)+4 a dokážeme, že potom délka řetězce T(N) je N2-2N+4. Řetězec T(N) vznikl přidáním 2N-3 znaků do řetězce T(N-1), jeho délka je (N-1)2-2(N-1)+4 + 2N-3 = N2 -2N+4. Dokázali jsme tedy, že délka řetězce T(N) je skutečně N2-2N+4.

Nakonec je třeba dokázat, že řetězec T(N) obsahuje všech N! permutací znaků abecedy jako podřetězce. Tento důkaz je poměrně zdlouhavý, takže uvedeme jen základní myšlenku. Řetězec T(N) rozdělíme na úseky. První úsek začíná prvním základním bodem a končí druhým základním bodem. Pro 2 <= i <= N-1 bude i-tý úsek začínat znakem a1, který je hned za i-tým základním bodem, a končit znakem ai, který se vyskytuje poprvé za (i+1)-ním základním bodem.

Matematickou indukcí (vzhledem k N) lze dokázat, že každý z takto vytvořených úseků obsahuje znaky a1,a2... aN a začíná znakem a1. Řetězec obsahuje N-1 takovýchto úseků a každý z nich obsahuje právě jeden základní bod s výjimkou prvního úseku, který obsahuje dva základní body. Další vlastností dvou sousedních úseků i-tého a (i+1)-ního je jejich vzájemné překrytí ve dvou znacích, a to a1 a ai.

Nechť má naše permutace znak a1 na i-tém místě. Uvažujme nejprve případ že i <= N-1. V permutaci vybereme první výskyt znaku a1 z i-tého úseku řetězce T(N). Z i-tého úseku je možné použít ještě jeden znak, neboť se v něm vyskytují všechny znaky, a to až za vybraným znakem a1. Před i-tým úsekem je i-1 úseků a za ním je N-i-1 úseků. Při výběru jednoho znaku z každého úseku tedy dostaneme všechny permutace se znakem a1 v i-té pozici. Překrytí sousedních úseků nezpůsobí problémy, protože při výběru znaku a1 z i-tého úseku je možné všechny ostatní znaky a1 ignorovat a další společné znaky se stávají hraničními prvky úseků. Hraniční prvek je považován za prvek patřící jen do jednoho úseku.

Zbývá dokázat tvrzení v případě, že a1 je v permutaci na N-tém místě. V tomto případě řetězec T(N) rozdělíme na úseky se základními body jako hraničními body úseků. Počet úseků je N-1 a každý z nich obsahuje znaky a1, a2,... aN. Jestliže na poslední místo vybereme poslední výskyt znaku a1 v řetězci T(N), tento znak nepatří do žádného z výše uvedených úseků. Řetězec T(N) tedy obsahuje všechny permutace se znakem a1 na posledním místě.

Uvedený algoritmus pro N=15 dává následující řetězec délky 199:

a-c-d-e-f-g-h-i-j-k-l-m-n-o-b-a-d-e-f-g-h-i-j-k- l-m-n-o-c-a-b-e-f-g-h-i-j-k-l-m-n-o-d-a-c-b-f-g- h-i-j-k-l-m-n-o-e-a-d-b-c-g-h-i-j-k-l-m-n-o-f-a- e-b-c-d-h-i-j-k-l-m-n-o-g-a-f-b-c-d-e-i-j-k-l-m- n-o-h-a-g-b-c-d-e-f-j-k-l-m-n-o-i-a-h-b-c-d-e-f- g-k-l-m-n-o-j-a-i-b-c-d-e-f-g-h-l-m-n-o-k-a-j-b- c-d-e-f-g-h-i-m-n-o-l-a-k-b-c-d-e-f-g-h-i-j-n-o- m-a-l-b-c-d-e-f-g-h-i-j-k-o-n-a-m-b-c-d-e-f-g-h- i-j-k-l-o-a-n Na závěr uvádíme program, který řetězec T(15) generuje výše popsaným způsobem.

program P_I_2; const N=15; {počet prvků abecedy} abeceda:string='abcdefghijklmno'; {abeceda řetězce} var T: string; {hledaný řetězec} BB: array[1..N] of integer; {indexy základních bodů} i: integer; ff: text; function Dalsi(n: integer; T:string):string; {funkce dostane řetězec všech permutací prvních n-1 prvků a vrátí řetězec všech permutací prvních n prvků (n>3)} var i, j: integer; TN: string; begin TN:=''; i:=BB[1]; j:=2; {přidání nových prvků před základní body} while j<n do begin TN:=TN+copy(T,i,BB[j]-BB[j-1]); i:=BB[j]; j:=j+1; TN:=TN+abeceda[n]; end; TN:=TN+copy(T,BB[n-1],length(T)); {přidání prvků na konec řetězce} for i:=2 to n-3 do TN:=TN+abeceda[i]; TN:=TN+abeceda[n]; {nový základní bod} TN:=TN+abeceda[1]+abeceda[n-1]; {úprava základních bodů} BB[n]:=length(TN)-2; {nový základní bod} for i:=2 to n-1 do {původní body se posunuly} BB[i]:=BB[i]+i-1; Dalsi:=TN; end; {Dalsi} procedure VytvorT3; {vytvoří řetězec všech permutací pro tříprvkovou abecedu} begin T:=abeceda[1]+abeceda[3]+abeceda[2]+abeceda[1] +abeceda[3]+abeceda[1]+abeceda[2]; BB[1]:=1; BB[2]:=3; BB[3]:=5; end; begin assign(ff,'P-1-2.TXT'); rewrite(ff); VytvorT3; for i:=4 to N do T:=Dalsi(i,T); writeln(ff,T); close(ff); end.

P-I-3

Tuto úlohu si můžeme představit tak, že máme dáno pole n navzájem různých čísel a[1], a[2], ..., a[n] (preference politických stran) a máme za úkol nalézt nejmenší a největší prvek tohoto pole, přičemž ale k poli můžeme přistupovat pouze prostřednictvím funkce pruzkum(i,j), která nám říká, zda je a[i]<a[j] nebo a[j]<a[i].

Ukážeme si nejprve řešení pro sudé n. Rozdělíme všechny prvky pole do dvojic a v každé dvojici prvky porovnáme (pomocí funkce pruzkum). Prvky se nám rozdělí na dvě podmnožiny -- do množiny X dáme ty, které byly při porovnávání v dvojici větší a do množiny Y ty, které byly při porovnávání menší. Je zřejmé, že žádný prvek z množiny X nebude nejmenším prvkem v poli, neboť existuje aspoň jeden menší prvek (ten, který s ním byl ve dvojici). Proto při hledání minima stačí hledat mezi prvky množiny Y. Podobně žádný prvek z Y nebude největším prvkem pole a proto stačí maximum hledat mezi prvky množiny X.

Nejmenší z prvků množiny Y najdeme jednoduše. V proměnné min si budeme pamatovat nejmenší dosud nalezený prvek. Na začátku to bude libovolný prvek množiny Y. Potom budeme nejmenší dosud nalezený prvek porovnávat vždy s dalším a dalším prvkem množiny Y. Pokaždé, když bude porovnávaný prvek menší než prvek uložený v proměnné min, stane se on dosud nejmenším nalezeným prvkem (uloží se do proměnné min). Podobně budeme hledat i největší prvek v množině X.

V případě, že n je liché, budeme postupovat stejným způsobem, jenom do dvojic rozdělíme jen prvních n-1 prvků a poslední prvek nakonec přidáme do množiny X i do množiny Y. V některých případech můžeme ještě jedno porovnávání ušetřit -- pokud se tento poslední prvek stane nejmenším prvkem množiny Y (a tudíž i nejmenším prvkem celého pole), pak ho můžeme z množiny X vynechat, neboť jistě nebude současně největším prvkem. Případ n=1 ošetříme zvlášť. V tomto případě není třeba nic porovnávat - jediná strana má současně nejvyšší i nejnižší preference.

Nyní spočítáme, kolik porovnání v nejhorším případě vykonáme pro dané n. Je-li n sudé, vznikne nám n/2 dvojic. Pro každou dvojici provedeme jedno porovnání, abychom zjistili, který prvek je větší. Množiny X a Y budou mít každá n/2 prvků. Pro nalezení minima (nebo maxima) v množině s x prvky použijeme x-1 porovnání (do proměnné min uložíme nejprve první prvek, potom tuto proměnnou postupně porovnáme se všemi ostatními x-1 prvky). K nalezení minima v množině Y tedy potřebujeme n/2-1 porovnání a k nalezení maxima v množině X dalších n/2-1 porovnaní. Celkový počet porovnání tedy bude n/2+(n/2-1)+(n/2-1)=(3n-4)/2

Pro liché n budeme mít (n-1)/2 dvojic, takže na začátku vykonáme (n-1)/2 porovnání ve dvojicích. Množiny X a Y však budou mít (n-1)/2+1 prvků, takže k nalezení minima nebo maxima z takovéto množiny potřebujeme (n-1)/2 porovnání. Celkový počet provedených porovnání proto bude (n-1)/2+(n-1)/2+(n-1)/2=(3n-3)/2

Došli jsme k závěru, že pro n sudé vykonáme nejvýše (3n-4)/2 porovnání a pro n liché nejvýše (3n-3)/2 porovnání. Tento výsledek lze zapsat i jedním vzorcem s použitím horní celé části ({}) a dolní celé části ([]) takto: 2{n/2} + [n/2] - 2

Na závěr pár slov o implementaci popsaného algoritmu. Množiny X a Y nebudeme vytvářet na začátku výpočtu celé, ale průběžně. Nejprve vezmeme první dva prvky v poli, porovnáme je a menší z nich se stane počáteční hodnotou proměnné min, zatímco větší bude počáteční hodnotou proměnné max. Potom budeme brát vždy další a další dvojici, porovnáme vždy její prvky navzájem, následně menší z nich porovnáme s proměnnou min (a pokud bude třeba, tak obsah min změníme) a větší porovnáme s proměnnou max. Pro lichá n je třeba nakonec zvlášť zpracovat poslední prvek. Takto naprogramovaný algoritmus bude mít lineární časovou složitost (tzn. O(n)) a konstantní paměťovou složitost.

program P_I_3; var n,i,min,max,a,b,pom:integer; procedure pruzkum(i,j:integer; var min, max:integer); {provede průzkum pro i a j stranu s menšími preferencemi vrátí v min, s většími v max} begin writeln('Proveď průzkum ',i,',',j); write('> '); readln(max); if max=i then min:=j else min:=i; end; begin writeln('Zadej počet stran:'); write('> '); readln(n); if n=1 then begin {speciální případ} min:=1; max:=1; end else begin {inicializace - porovnáme první pár} pruzkum(1,2,min,max); end; i:=3; while i+1<=n do begin {ostatní páry} pruzkum(i,i+1,a,b); {porovnáme navzájem} pruzkum(min,a,min,pom); {menší porovnáme s minimem} pruzkum(max,b,pom,max); {větší s maximem} i:=i+2; end; if i=n then begin {poslední prvek pro liché n} pruzkum(min,n,min,pom); {porovnáme s min i s max, pokud je třeba} if min<>n then pruzkum(max,n,pom,max); end; writeln('Nejvyšší preference má strana ',max,', nejnižší ',min); end.

P-I-4

  1. Úkolem bylo sestrojit stroj, který pro vstup n vypočítá číslo 2^n. Číslo n máme uloženo v registru R1. Na začátku výpočtu uložíme do R0 číslo 1 (tj. 20). Potom budeme postupovat tak, že v každém kroku snížíme R1 o 1 a registr R0 vynásobíme 2. To provádíme tak dlouho, dokud v R1 není 0. Tehdy máme v R0 uloženo hledané číslo 2n.

    Zbývá už jen popsat, jak násobíme registr R0 dvěma. Jednou možností by bylo uložit do některého dalšího registru hodnotu 2 a potom použít algoritmus násobení uvedený v příkladu ve studijním textu. My však využijeme trochu zjednodušený algoritmus, který lze použít pouze pro násobení konstantou. V cyklu budeme po jedné snižovat hodnotu R0, dokud neklesne na nulu, a při každém snížení R0 dvakrát zvýšíme o 1 hodnotu registru R2. Po skončení cyklu máme v R2 dvojnásobek hodnoty, kterou jsme měli původně v R0. Zbývá už jen přesunout hodnotu z R2 zpět do R0, což provedeme dalším cyklem, který vždy jednou sníží R2 a zvýší R0, dokud nebude v R2 nula.

  2. Úkolem je vypočítat n-té Fibonacciho číslo Fn. Podle definice F0=F1=1 a Fn=Fn-1+Fn-2 pro n >= 2. Jestliže si však zavedeme pomocný člen této posloupnosti F-1=0, bude platit, že Fn=Fn-1+Fn-2 i pro n=1, což sníží počet případů, které je třeba v programu pro Minského stroj speciálně ošetřit.

    Náš stroj bude pracovat tak, že v cyklu bude snižovat registr R1 a počítat další člen Fibonacciho posloupnosti, dokud nebude v R1 nula. Po k průchodech tohoto cyklu bude registr R0 obsahovat Fk a registr R2 bude obsahovat Fk-1. Celkem se provede n průchodů, takže stroj správně vypočítá hodnotu Fn.

    Před prvním prováděním cyklu (tj. po nula průchodech) potřebujeme mít v registru R0 číslo F0=1 a v registru R2 číslo F-1=0. Toho dosáhneme snadno příkazem R0++.

    Zbývá nám prozkoumat, co potřebujeme provádět v těle cyklu. V registru R0 máme číslo Fk a v registru R2 číslo Fk-1. Chceme dosáhnout toho, aby v registru R0 bylo Fk+1=Fk+Fk-1, tj. součet registrů R0 a R2, a v registru R2 aby bylo Fk, tj. číslo, které bylo původně v R0. Budeme postupovat tak, že hodnotu v R0 přičítáme k registrům R2 a R3 (a to tak, že budeme v cyklu R0 snižovat, dokud neklesne na nulu, a pokaždé při tom zvýšíme R2 a R3). Po skončení této operace máme v R0 nulu, v R2 máme Fk+1 a v R3 máme Fk. Potřebujeme nyní ještě obsahy registrů přemístit tak, abychom do R0 dostali obsah R2 a do R2 obsah R3. To provedeme opět obvyklým způsobem (dvěma "přesýpacími" cykly).