4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

C++でトリボナッチ数列の問題を問いてみた&再起関数で書いたときの関数呼び出し回数(pythonもあるよ)

Last updated at Posted at 2020-06-22

#はじめに
はじめての記事です。面白そうな記事を見つけたのでチャレンジしてみました。
Rubyでトリボナッチ数列の問題を解いてみた(制限時間10分)
先駆者様

#C++で10分チャレンジ(失敗)
まず真っ先に再帰でやる方法を思いついてそのまま書きました。
要は初項[1,3,7]のトリボナッチ数列の50番目を求めよっていう問題です。

tribonacci_recursive.cpp
#include <iostream>
#include <chrono>
using namespace std;

long long tri_r(int num){
    if(num<=3){
        int templist[3] = {1,3,7};
        return templist[num-1];
    }
    else{
        return tri_r(num-1)+tri_r(num-2)+tri_r(num-3);
    }
}

int main(){
    chrono::system_clock::time_point  start, end;
    start = std::chrono::system_clock::now();
    cout << tri_r(51) << endl;
    end = std::chrono::system_clock::now();
    double e_time = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
    cout << e_time << " ms" << endl;
}

はい、これではマトモな時間では計算が終わりません。というわけで、無駄な計算をさせずに済むように書き直しです。この時点で10分は経っていたので、チャレンジ失敗です。

#C++で30分チャレンジ(クリア)

tribonacci.cpp
long long tri(int num){
    if(num<3){
        int templist[3] = {1,3,7};
        return templist[num-1];
    }
    else{
        long long tri_list[num] = {1,3,7};
        for(int i=3; i<num; i++){
            tri_list[i] = tri_list[i-1] + tri_list[i-2] + tri_list[i-3];
        }
        return tri_list[num-1];
    }
}
int main(){
    chrono::system_clock::time_point  start, end;
    start = std::chrono::system_clock::now();
    for(int i=1; i<51; i++){
        cout << i << "  " << tri(i) << endl;
    }
    end = std::chrono::system_clock::now();
    double e_time = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
    cout << e_time << " ms" << endl;
}

3以下のときの処理がダサいですが、一瞬で計算できるようになりました。
tri(1)~tri(50)まで出力するコードになっていますが、これでも20 msです。十分でしょう。

#再帰で書いたときの関数呼び出し回数
さて、再帰で書いた際ですが、無駄な計算をしまくっているのはわかりますが、この関数の呼び出し回数はどのように膨れ上がっていくのでしょうか。

計算式 tri_r呼び出し回数
tri_r(1) 1 1
tri_r(2) 1 1
tri_r(3) 1 1
tri_r(4) tri_r(1) + tri_r(2) + tri_r(3) = 1+1+1 3
tri_r(5) tri_r(2) + tri_r(3) + tri_r(4) =1+1+3 5
tri_r(6) tri_r(3) + tri_r(4) + tri_r(5) = 1+3+5 9

見えてきましたね。呼び出し回数は初項{1,1,1}のトリボナッチ数列により求められます。考えてみればあたりまえなんですが、ちょっと気持ちが良い事実ですね。

再帰のほうで、計算時間を計測してみました。
マトモな計算時間で終わるところだけピックアップ(10回計測して平均取ってます)。

num 時間(ms)
34 825.2
35 1524.2
36 2856.1

34~36項では、それぞれ計算時間は1.85倍、1.87倍程度になっています。
呼び出し回数はどうでしょうか。慣れてるPythonで書いてきました。

tri_calc.py
def tri(num):
    ans_list = [1,1,1]
    if num > 3:
        for i in range(3, num):
            ans_list.append(ans_list[i-3] + ans_list[i-2] + ans_list[i-1])
    return ans_list

calc_num = tri(50)
print(calc_num[35]/calc_num[34])  #1.8392867552142929
print(calc_num[36]/calc_num[35])  #1.8392867552141035

ということで、関数の呼び出し回数は、1項増えるたびに1.84倍程度だとわかると思います。計算時間の増加は、ほとんどが呼び出しのオーバーヘッドっぽいですね。

#おわりに
初めての投稿で、Markdownとかナニソレ状態でした。ここをこういうふうに書くと読みやすいよ、とかあったら是非教えて下さい。
まだまだプログラミング、コーディング初心者ですが、こういう問題を解いて、いろいろ検証してくのって楽しいものですね。
読んでくださりありがとうございました。

4
1
10

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?