프로젝트 오일러 65

e의 100번째 연분수 확장 값의 분자 자릿수를 모두 더하면?

알고리즘의 방향이 역순이어야 쉽게 풀리는 듯 하다(=100번째 연분수부터 구해내가서 1번째 연분수까지 구하는 식으로). 100번째 연분수 분자값은 꽤 큰 수이므로 큰 수를 다룰 도구 코드도 필요함. 큰 수 클래스 코드는 오일러63 에서 썼던 코드를 가져왔고, 마찬가지로 깃헙 링크 로만 남겨둔다.

실행시간 0.001초.

/*
 	Problem 65 - Convergents of e
*/
	
#include <iostream>
#include <ctime>
#include <vector>
#include <map>
#include <string.h>
#include "BigInt.h"

using namespace std;

int main(int argc, char** argv)
{
	clock_t begin = clock();

	/* starting code */
	std::vector<int> c;
	c.push_back(2);
	for(int i=1; i<35; i++)
	{
		c.push_back(1);
		c.push_back(i*2);
		c.push_back(1);
	}

	int MAX = 99;
	BigInt n;
	BigInt d;
	for(int i=MAX; i>0; i--)
	{
		if( n.getDigitsLen() == 0 && d.getDigitsLen() == 0) {  // first
			n = BigInt(1);
			d = BigInt(c[i]);
		} else {
			// intermediate
			BigInt adding = BigInt(c[i]) * d;
			BigInt in = adding + n;
			BigInt id = BigInt(d);

			// final
			n = id;
			d = in;
		}
	}

	BigInt last = n + BigInt(2) * d;
	int sum = 0;
	for(int i=0; i<last.getDigitsLen(); i++)
	{
		sum += last.getDigits()[i];
	}
	cout << "sum=" << sum << endl;

	/* end of code */
	clock_t end = clock();
	std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
	return 0;
}