Problem Description
It is possible to show that the square root of two can be expressed as an infinite continued fraction.
sqrt(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?
C++
Get the pseudo-code of calculating the numerator and denominator of the fraciton first from the expression above. Then you could easily write the main code:
Main()
void Problem_57()
{
int count = 0;
for(int i=1; i<= EXPANSION_TIME; i++)
{
Fraction fra(1, 2);
int loop = 1;
while(loop <i)
{
fra.Add(2);
fra.Reciprocal();
loop++;
}
fra.Add(1);
if(fra.IsOKForProblem())
{
count++;
// fra.Display();
}
}
printf("result = %d\n", count);
}
You may need a Fraction class which manages two fields numerator and denominator.
Plealse note that the numbers in the calculation are far beyond the maxnium of a 4 bytes integer, you need a Big Integer type.
I would like to show my simple implementation below:
Fraction and BigInteger
class BigInteger
{
public:
BigInteger(int a)
{
memset(m_digits, 0, 1000);
int index = 0;
while(a != 0)
{
m_digits[index] = a % 10;
a = a/ 10;
index++;
}
m_length = index;
}
void Add(const BigInteger& other)
{
int maxLength = max(m_length, other.m_length);
for(int i=0; i<maxLength; i++)
{
int temp = m_digits[i] + other.m_digits[i];
if(temp >= 10)
{
m_digits[i+1]++;
m_digits[i] = temp % 10;
}
else
{
m_digits[i] = temp;
}
}
m_length = (m_digits[maxLength] == 0) ? maxLength : (maxLength + 1);
}
void Multiply(int num)
{
BigInteger other(*this);
for(int i=0; i<num - 1; i++)
{
Add(other);
}
}
int GetLength()
{
return m_length;
}
void Display()
{
char str[1000] = {0};
for(int i = m_length - 1; i>=0; i--)
{
str[m_length - i - 1] = (char)(m_digits[i] + '0');
}
printf("%s", str);
}
private:
BYTE m_digits[1000];
int m_length;
};
class Fraction
{
public:
Fraction(int numerator, int denominator)
: m_bi1(numerator), m_bi2(denominator), m_isBI1Numerator(true)
{
}
void Reciprocal()
{
m_isBI1Numerator = !m_isBI1Numerator;
}
void Add(int addend)
{
BigInteger temp(GetDenominator());
temp.Multiply(addend);
GetNumerator().Add(temp);
}
void Display()
{
GetNumerator().Display();
printf("/");
GetDenominator().Display();
printf("\n");
}
bool IsOKForProblem()
{
return GetNumerator().GetLength() > GetDenominator().GetLength();
}
private:
BigInteger& GetNumerator()
{
return m_isBI1Numerator ? m_bi1 : m_bi2;
}
BigInteger& GetDenominator()
{
return m_isBI1Numerator ? m_bi2 : m_bi1;
}
bool m_isBI1Numerator;
BigInteger m_bi1;
BigInteger m_bi2;
};
原文链接: https://www.cnblogs.com/quark/archive/2012/08/06/2624733.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/58307
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!