工学1号馆

home

Project Euler 57–Square root convergents

By Wu Yudong on August 20, 2018

Square root convergents

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…
By expanding this for the first four iterations, we get:

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…

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

2的平方根可以用一个无限连分数表示：

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

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…

//（Problem 57）Square root convergents
// Completed on Wed, 12 Feb 2014, 04:45
// Language: C
//
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com
#include<stdio.h>

int add(int des[],int n1,int src[],int n2){
int i,f;
for(i=0 , f = 0 ; i < n1 || i < n2 ; i++){
des[i] += ( f + src[i] ) ;
f = des[i]/10 ;
des[i] %= 10 ;
}
if(f)
des[i++] = f ;
return i;
}
int main(){
int num = 1 ,sum = 0 , k;
int array[2][500] = {0} ;
int nn = 1 ,dn = 1 , f = 0 ;//nn分子长度,dn分母长度,f分子位置

array[0][0] = 3 ;
array[1][0] = 2 ;
while(num<1000){
//分子加分母放到分子位置成为下一个分母
//分子加分母放到分母位置成为下一个分子
nn = add( array[1-f],dn,array[f],k ) ;
dn = k ;
f = 1 - f ;
if(nn > dn) sum++;
num++;
}
printf("%d\n",sum);
return 0;
}

Completed on Wed, 12 Feb 2014, 12:45