アルゴリズム入門編:フィボナッチ数に挑戦しよう vol.4 - 再帰1回編 | プログラミング学習サイト【paizaラーニング】

// フィボナッチ数 - 再帰1回
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
public class Main {
    public static void main(String[] args) throws Exception {
        int number = 0;
        System.out.println(i + ":" + fibonacci(i));
    }

    public static long fibonacci(int num) {
        return num;
    }
}

// フィボナッチ数 - 再帰1回
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
public class Main {
    public static void main(String[] args) throws Exception {
        int number = 0;
        System.out.println(i + ":" + fibonacci(i));
    }

    public static long fibonacci(int num) {
        return num;
    }
}

// トリボナッチ数
// 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149
// 再帰を用いて作成
public class Main {
    public static void main(String[] args) throws Exception {
        int number = 50;
        for (int i = 0; i <= number; i++) {
            System.out.println(i + ": " + tribonacci(i));
        }
    }
    public static long tribonacci(int num) {
        // トリボナッチ数の最初の3項(0, 0, 1)を用いて，再帰呼び出し
        return tri2(0, 0, 1, num);
    }
    public static long tri2(long a, long b, long c, long d) {
        // 再帰の深さがd
        if (d < 2) {
            return a;
        }
        // 再帰呼び出し
        return tri2(, , , d - 1); // この行を修正
    }
}

// トリボナッチ数
// 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149
// 再帰を用いて作成
public class Main {
    public static void main(String[] args) throws Exception {
        int number = 50;
        for (int i = 0; i <= number; i++) {
            System.out.println(i + ": " + tribonacci(i));
        }
    }
    public static long tribonacci(int num) {
        // トリボナッチ数の最初の3項(0, 0, 1)を用いて，再帰呼び出し
        return tri2(0, 0, 1, num);
    }
    public static long tri2(long a, long b, long c, long d) {
        // 再帰の深さがd
        if (d < 2) {
            return a;
        }
        // 再帰呼び出し
        return tri2(, , , d - 1); // この行を修正
    }
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「50までのトリボナッチ数を求める - 再帰」

右のプログラムをベースにして、0から50までのトリボナッチ数を出力してください。
ただし、本チャプターで使った方法を参考にして、再帰を用いて計算します。
コードの実行をして、エラーが出なければ、演習課題クリアです。

トリボナッチ数とは、次のように定義される数列です。

T(0) = 0
T(1) = 0
T(2) = 1
T(n) = T(n - 1) + T(n - 2) + T(n - 3)

たとえば、4番目のトリボナッチ数は、次のように計算します。

T(4) = T(3) + T(2) + T(1) = 1 + 1 + 0 = 2

※wikipediaの「フィボナッチ数」(https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0) を参照

期待する出力値

0: 0
1: 0
2: 1
3: 1
4: 2
5: 4
6: 7
7: 13
8: 24
9: 44
10: 81
11: 149
...

Tips

動画へ戻る

次のチャプターへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃06:フィボナッチ数に挑戦しよう vol.4 - 再帰1回編

フィボナッチ数を表示するプログラムを作成してみたいと思います。ここでは、前回のプログラムとは違って、再帰呼び出しの回数を2回から1回に減らすように、プログラムを改良します。

計算手順の追跡

num = 3の場合

(0 1 3)
(1 0 2)
(1 1 1)
(2 1 0)

→フィボナッチ数は、2

num = 4の場合

(0 1 4)
(1 0 3)
(1 1 2)
(2 1 1)
(3 2 0)

→フィボナッチ数は、3

num = 5の場合

(0 1 5)
(1 0 4)
(1 1 3)
(2 1 2)
(3 2 1)
(5 3 0)

→フィボナッチ数は、5

num = 6の場合

(0 1 6)
(1 0 5)
(1 1 4)
(2 1 3)
(3 2 2)
(5 3 1)
(8 5 0)

→フィボナッチ数は、8

num = 7の場合

(0 1 7)
(1 0 6)
(1 1 5)
(2 1 4)
(3 2 3)
(5 3 2)
(8 5 1)
(13 8 0)

→フィボナッチ数は、13

num = 8の場合

(0 1 8)
(1 0 7)
(1 1 6)
(2 1 5)
(3 2 4)
(5 3 3)
(8 5 2)
(13 8 1)
(21 13 0)

→フィボナッチ数は、21

プログラミング学習 > アルゴリズム入門編 > アルゴリズム入門編: FizzBuzzとフィボナッチ数を学ぶ > フィボナッチ数に挑戦しよう vol.4 - 再帰1回編

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：