はじめに
はじめての記事です。面白そうな記事を見つけたのでチャレンジしてみました。
Rubyでトリボナッチ数列の問題を解いてみた(制限時間10分)
先駆者様
- Elixirでトリボナッチ数列の問題を解いてみた(制限時間10分)
- Rubyでトリボナッチ数列の問題を解いてみた、再帰で。
やったこと
・C++で10分チャレンジ(計算時間が長すぎで失敗)
・C++で30分チャレンジ(クリア)
・再帰で書いたときの関数呼び出し回数について(python実装込)
C++で10分チャレンジ(失敗)
まず真っ先に再帰でやる方法を思いついてそのまま書きました。
要は初項[1,3,7]のトリボナッチ数列の50番目を求めよっていう問題です。
#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分チャレンジ(クリア)
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で書いてきました。
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とかナニソレ状態でした。ここをこういうふうに書くと読みやすいよ、とかあったら是非教えて下さい。
まだまだプログラミング、コーディング初心者ですが、こういう問題を解いて、いろいろ検証してくのって楽しいものですね。
読んでくださりありがとうございました。