Wu Yudong's Blog

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

Project Euler 57–Square root convergents

Comments