Fibonacciho posloupnost

Zadání

Program, který vypíše (podle výběru) n-tý člen Fibonacciho posloupnosti (na který přijde buď rekurzivně, nebo iteračně), n členů posloupnosti, nebo poměr dvou po sobě následujících členů (n+1) člen / n-tý člen.



Teorie

Fibonacciho posloupnost je jednoduchá posloupnost, ve které platí, že každý člen je roven součtu dvou členů předchozích (kromě prvních dvou členů, které jsou 0 a 1). Rekurzivní zápis vypadá takto:

Tím bychom měli rekurzivní zápis vymyšlený, iterační bude ještě jednodušší. Stačí nám uchovávat pouze dvě poslední hodnoty, díky kterým dokážeme spočíst hodnotu dalšího členu. Je jasné, že iterační zápis bude o mnoho rychlejší než rekurze, protože nám stačí projít n-krát cyklem pro spočtení následujícího členu, zatímco při rekurzi bude metoda volána pro tu samou hodnotu několikrát. Například pro výpočet čtvrtého členu Fibonacciho posloupnosti bude platit:

Posledním úkolem je vypsat poměr dvou po sobě následujících členů. Poměr (n+1) členu a n-tého členu je u Fibonacciho posloupnosti zajímavý tím, že konverguje ke zlatému řezu - pro limitu jdoucí do nekonečna jde přímo o hodnotu zlatého řezu:

Řešení

Začneme prvním úkolem, kterým je výpočet n-tého členu. Vytvoříme si metodu, které předáme n - pořadí hledaného členu. Napíšeme jednoduchý cyklus, který bude neustále dopočítávat další členy z předchozích dvou hodnot (které budeme mít uloženy v proměnných typu long pojmenovaných first a second).

public static long nthMember(int n){
    long ret = 0;
    long first = 0, second = 1;
    for(int i = 1; i < n; i++){
        ret = first + second;
        first = second;
        second = ret;
    }
    if(n < 2) return n;
    else return ret;
}

Budeme pokračovat s tím samým úkolem, ale vyjádřeným rekurzivně (zápis je velice jednoduchý, ale platíme za něj velice pomalým průběhem). Rekurzivní metoda nám bude volat samu sebe, pouze předávaný argument se bude lišit - protože se snažíme vypsat součet dvou předchozích členů. Jakmile se dostaneme k hodnotě "1" nebo "0", jsme na konci a vracené hodnoty se začnou sčítat.

public static long nthMemberRecursively(int n){
    if(n < 2) return 1;
    else return (nthMemberRecursively(n - 1) + nthMemberRecursively(n - 2));
}

Samotný výpis n členů posloupnosti můžeme vyřešit takto krátkým zápisem:

public static void nMembers(int n){
    for(int i = 0; i < n; i++)
        System.out.print(nthMember(i) + " ");
    System.out.println();
}

a nebo poněkud delším, ale zato rychlejším (protože není třeba pro každou hodnotu volat funkci) zápisem:

public static void nMembers(int n){
    long ret = 0;
    long first = 0, second = 1;
    System.out.print("0 1 ");
    for(int i = 1; i < n; i++){
        ret = first + second;
        first = second;
        second = ret;
        System.out.print(ret + " ");
    }
    System.out.println();
}

Výpis přibližné hodnoty zlatého řezu už je snadný, stačí použít některou metodu vracející hodnotu n-tého členu, jen musíme spočtený poměr převádět na typ desetinný double:

public static void goldenRatio(int n){
    System.out.println((double)nthMember(n+1)/(double)nthMember(n));
} 

Samotná aplikace pak bude obsahovat pouze volání těchto metod s celočíselným argumentem, nebo můžete nechat zadání hodnoty n přímo na uživateli.