（Problem 57）Square root convergents

时间：2021-08-25 23:45:03

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

（Problem 57）Square root convergents 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的平方根可以被表示为无限延伸的分数：

（Problem 57）Square root convergents 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, and 577/408, 但是第八次迭代的展开, 1393/985, 是第一个分子的位数超过分母的位数的例子。

在前1000次迭代的展开中，有多少个的分子位数超过分母位数？

//（Problem 57）Square root convergents

// Completed on Wed, 12 Feb 2014, 04:45

// Language: C

//

// 版权所有（C）acutus   (mail: acutus@126.com)

// 博客地址：http://www.cnblogs.com/acutus/

#include<stdio.h>

int add(int des[],int n1,int src[],int n2){

    int i,f;

    for(i= , f =  ; i < n1 || i < n2 ; i++){

        des[i] += ( f + src[i] ) ;

        f = des[i]/ ;

        des[i] %=  ;

    }

    if(f)

        des[i++] = f ;

    return i;

}

int main(){

    int num =  ,sum =  , k;

    int array[][] = {} ;

    int nn =  ,dn =  , f =  ;//nn分子长度,dn分母长度,f分子位置

    array[][] =  ;

    array[][] =  ;

    while(num<){

//分子加分母放到分子位置成为下一个分母

    k = add(array[f],nn,array[-f],dn);

//分子加分母放到分母位置成为下一个分子

    nn = add( array[-f],dn,array[f],k ) ;

    dn = k ;

    f =  - f ;

    if(nn > dn) sum++;

    num++;

    }

    printf("%d\n",sum);

    return ;

}
Answer:
 153

相关文章