Project Euler 25
フィボナッチ数列は以下の漸化式で定義される: Fn = Fn-1 + Fn-2, ただし F_1 = 1, F_2 = 1. 最初の12項は以下である. F_1 = 1 F_2 = 1 F_3 = 2 F_4 = 3 F_5 = 5 F_6 = 8 F_7 = 13 F_8 = 21 F_9 = 34 F_10 = 55 F_11 = 89 F_12 = 144 12番目の項, F12が3桁になる最初の項である. 1000桁になる最初の項の番号を答えよ.
Mathematica
i = 1; While[ True, tmp1 = Length[IntegerDigits[Fibonacci[i]]]; If[tmp1 >= 1000, Break[], {}] i++; ] i
1000桁になったらループを終了、というだけですね。
C/C++
#pragma comment(lib,"mpir.lib") #include <iostream> #include <mpir.h> using namespace std; // n番目のフィボナッチ数を返す。(mpir版) /* void fibonacci(mpz_t* num, int n){ if(n>2){ mpz_t a,b; fibonacci(&a, n-1); fibonacci(&b, n-2); //a = a+b; mpz_add(a, a, b); mpz_init_set(*num, a); } else mpz_init_set_ui(*num, 1); } */ // mpz_t型の桁数を返す。 int mpz_digit(mpz_t* num){ mpz_t a; mpz_init_set(a, *num); int count = 0; while(mpz_cmp_si(a,0)!=0){ // a = a/10; mpz_div_ui(a, a, 10); count++; } return count; } int main(){ //old1 -> n-1番目, old2 -> n-2番目 mpz_t old1, old2, n; mpz_init_set_ui(old1, 1); mpz_init_set_ui(old2, 1); mpz_init_set_ui(n, 0); int dig, order = 3; while(1){ //n = old1+old2; mpz_add(n, old1, old2); dig = mpz_digit(&n); /* cout << order << "th -> "; mpz_out_str(stdout, 10, n); cout << ", digit -> " << dig << endl; */ if(dig >= 1000) break; order++; mpz_set(old2, old1); mpz_set(old1, n); } cout << order << "th -> "; mpz_out_str(stdout, 10, n); cout << ", digit -> " << dig << endl; return 0; }
最初にフィボナッチ数列の関数を再起で作ったんですが、これがもう糞のように遅かった。(当たり前)