VYŠŠÍ ODBORNÁ ŠKOLA a STŘEDNÍ PRŮMYSLOVÁ ŠKOLA Mariánská 1100, 407 47 Varnsdorf
PROGRAMOVÁNÍ FUNKCE, REKURZE, CYKLY Jméno a příjmení: Školní rok:
Petr VOPALECKÝ Číslo úlohy:
2007/2008
Třída:
Počet listů:
VI2
1 6
Název úlohy a zadání:
Funkce, rekurze, cykly ZADÁNÍ: Naprogramujte funkce pro výpočet Fibonacciho posloupnosti. Použijte jak sekvenční, tak i rekurzivní metodu výpočtu. Porovnejte operační složitost těchto metod. Požadavky: Úlohu zpracujte komplexně. Nejprve proveďte studii problému Fibonacciho posloupnosti a zhodnoťte možnosti úlohy v PHP. Dále provedete vytvoření algoritmů. Nakonec úlohu zhodnoťte. Odevzdat v digitální podobě (DOC, DOCX, PDF, ODT). Program bude vystaven na veřejné adrese, která bude součástí protokolu.
Použitá literatura:
Datum odevzdání: Odevzdáno dne:
Hodnocení:
PEVNÝ DISK 1
Podpis vyučujícího:
Obsah Zadání...................................................................................................................... .............................2 Analýza............................................................................................................................ .....................2 Popis algoritmu........................................................................................................................ .............2 Program v PHP.............................................................................................................. .......................3 Tabulka........................................................................................................................................... .......5 Graf............................................................................................................................... ........................6 Závěr............................................................................................................................... ......................6
Zadání Naprogramujte funkce pro výpočet Fibonacciho posloupnosti. Použijte jak sekvenční, tak i rekurzivní metodu výpočtu. Porovnejte operační složitost těchto metod. Požadavky: Úlohu zpracujte komplexně. Nejprve proveďte studii problému Fibonacciho posloupnosti a zhodnoťte možnosti úlohy v PHP. Dále provedete vytvoření algoritmů. Nakonec úlohu zhodnoťte. Odevzdat v digitální podobě (DOC, DOCX, PDF, ODT). Program bude vystaven na veřejné adrese, která bude součástí protokolu.
Analýza Fibonacciho posloupnost je v matematice označována jako nekonečná posloupnost přirozených čísel začínajících 0, 1, 1, 2, 3, 5, 8, 13, 21, …, kde každé číslo je součtem předchozích dvou čísel. V našem případě je vstupem n-tý prvek již zmíněné Fibonnaciho posloupnosti. Výstupem jsou čísla n-tého prvku posloupnosti a počet kroků sekvenčně a rekurzivně. Rekurzivní znamená volající sama sebe. Algoritmus tedy musí na začátku přijmout číslo, které bude udávat n-tý prvek Fibonnaciho posloupnosti. Výpočet proběhne nejprve sekvenční formou,která nám umožní spočítat i počet kroků. Po té algoritmus bude počítat rekurzivní formou. Pro názorné porovnání obou případů přiložíme tabulku 1.0 a graf 1.0, kde výsledné výpočty mezi sebou porovnáme.
Popis algoritmu Vstupní formulář odešle číslo do proměnné řada. Budeme počítat sekvenční i rekurzivní počet a následné i počet kroků jak sekvenčních tak i rekurzivních. Budeme sčítat předchozí a před předchozí číslo, které bylo zadané do vstupního formuláře. Pokud uživatel zadá číslo 0 tak se na výstupu nic neobjeví. Pokud do pole vložíme například číslo 5, tak se provede maximálně 5 kroků, přičemž první krok v řadě odpovídá číslu 0, jelikož Fibonnaciho posloupnost začíná právě na číslo 0. Sekvenční a rekurzivní počet se nesmí od sebe lišit a proto v se druhý a třetí sloupec tabulky 1.0 sobě rovná. Čtvrtý a pátý sloupec se zabývá vyjádřením kroků. Jak je vidět sekvenční krokování je postupné (v grafu je naznačeno červenou barvou), naproti tomu rekurzivní (volající samo sebe) má tendenci spíše exponenciální (v grafu je naznačeno modrou barvou). Je tedy zcela zřejmé, že pro volbu kroků Fibonnaciho posloupnosti je lepší užití sekvenčního krokování. Funkční program nalezneme na adrese: http://petr-vopalecky.xf.cz/skola/programovani/prvni_prace.php
2
Program v PHP
"; for($rada=0;$rada<$pole;$rada++) { $sekvencne=sekvence($rada); $rekurzivne=rekurze($rada); 3
echo "| $rada $sekvencne | $rekurzivne | $kroksekvence | $krokrekurzivne | ";
?>
4
Tabulka
řada
sekvenčně 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
rekurzivně
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229
tabulka 1.0
5
krok sekvenčně 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
krok rekurzivně 1 2 5 10 19 34 59 100 167 276 453 740 1205 1958 3177 5150 8343 13510 21871 35400 57291 92712 150025 242760 392809 635594 1028429 1664050 2692507 4356586
Graf Sekvenční a rekurzivní kroky 5000
4500
4000
3500
3000
Řada
2500
2000
1500
1000
500
0 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Kroky
graf 1.0
Sekvenční krokování je naznačeno červenou barvou. Rekurzivní krokování je naznačeno modrou barvou.
Závěr Úloha byla poněkud složitější díky tomu, že jsem zpočátku nevěděl co je rekurze. Největší problém jsem prozatím nalezl ve vymyšlení projektu, především užití vzorce tak, aby výsledek byl správný. Program jsem upravil tak, aby byl co nejvhodnější pro web a zdrojový kód jsme zkopíroval do této práce.
6
28
29
