Project Euler 57
2の平方根は無限に続く連分数で表すことができる.
√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
最初の4回の繰り返しを展開すると以下が得られる.
- 1 + 1/2 = 3/2 = 1.5
- 1 + 1/(2 + 1/2) = 7/5 = 1.4
- 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
- 1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
次の3つの項は99/70, 239/169, 577/408である. 第8項は1393/985である. これは分子の桁数が分母の桁数を超える最初の例である.
最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつか?
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2057
#pragma comment(lib, "mpir.lib") #include <iostream> #include <mpir.h> using namespace std; class Frac{ public: // 分母 mpz_t denominator; // 分子 mpz_t numerator; Frac(mpz_t, mpz_t); void inverse(); void Print(); void intPlus(int); }; Frac::Frac(mpz_t a, mpz_t b){ mpz_init_set(numerator, a); mpz_init_set(denominator, b); } void Frac::Print(){ char c[100000], c2[100000]; mpz_get_str(c, 10, numerator); mpz_get_str(c2, 10, denominator); cout << c << "/" << c2 << endl; } void Frac::inverse(){ mpz_t tmp; mpz_init_set(tmp, denominator); mpz_set(denominator, numerator); mpz_set(numerator, tmp); } void Frac::intPlus(int a){ mpz_t m; mpz_init_set_ui(m, a); mpz_mul(m, m, denominator); mpz_add( numerator, numerator, m); } // 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(){ mpz_t numer, denom; mpz_init_set_ui(numer, 1); mpz_init_set_ui(denom, 2); Frac a(numer, denom); int cnt=0; for(int i=0 ; i<1000 ; i++){ mpz_set_ui(a.numerator,1); mpz_set_ui(a.denominator,2); for(int j=i ; j>0 ; j--){ a.intPlus(2); a.inverse(); } a.intPlus(1); //a.Print(); if(mpz_digit(&a.numerator) > mpz_digit(&a.denominator)) cnt++; } cout << cnt << endl; int end; cin >> end; }