工学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…

接下来的三个迭代展开式分别是99/70、239/169和577/408,但是直到第八个迭代展开式1393/985,分子的位数第一次超过分母的位数。

在前一千个迭代展开式中,有多少个分数分子的位数多于分母的位数?

//(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){ 
//分子加分母放到分子位置成为下一个分母
    k = add(array[f],nn,array[1-f],dn);
//分子加分母放到分母位置成为下一个分子
    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;
}

Answer:153

Completed on Wed, 12 Feb 2014, 12:45

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)