Friday 18 October 2013

PROJECT EULER SOLUTION # 57




Solution to problem number 57 of Project Euler.
Question # 57
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?

Solution # 57
/**********************************************************************************/
#include<stdio.h>
#include<time.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>

int n[1000],d[1000],tmp[1000];
void new_d();
void new_n();

int countDigits(int*);

int main()
{
       int i,j,k,counter=0;
       for(i=0;i<1000;i++)
              n[i]=d[i]=tmp[i]=0;

       n[999]=3;
       d[999]=2;
       for(k=1;k<1000;k++)
       {
             
              new_d();
              new_n();
              for(j=0;j<1000;j++)
                     d[j]=tmp[j];
              if(countDigits(n)>countDigits(d))
                     counter++;
       }
       printf("\nANSWER = %d\n",counter);
       printf("\nEXECUTION TIME = %f\n",clock()/(float)CLK_TCK);
       system("pause");
}

void new_n()
{
       int i;
       for(i=0;i<1000;i++)
              n[i]=d[i]+tmp[i];
       for(i=999;i>0;i--)
       {
              if(n[i]>9)
              {
                     n[i]%=10;
                     n[i-1]+=1;
              }
       }
}     

/* this function stores the
new denominator in tmp array*/
void new_d()
{
       int i;
       for(i=0;i<1000;i++)
              tmp[i]=n[i]+d[i];
       for(i=999;i>0;i--)
       {
              if(tmp[i]>9)
              {
                     tmp[i]%=10;
                     tmp[i-1]+=1;
              }
       }
}     

int countDigits(int *arr)
{
       int i;
       for(i=0;i<1000;i++)
              if(arr[i]!=0)
                     break;
       return (1000-i);
}
/**********************************************************************************/

No comments:

Post a Comment