프로젝트 오일러 45
projecteuler, cpp문제가 친절하다. 40755가 각각 몇 번째 triangular/pentagonal/hexagonal 인지 알려줬고 바로 이 다음수만 구하면 되니까..
세 종류의 수 중 한 수가 다른 두 수보다 크거나 같아질 때까지 증가시켜가며, 같은지 비교해보고, 같지 않으면 또 수를 증가시키는 방식으로 짰다.
/*
Problem 45 - Triangular, pentagonal, and hexagonal
*/
#include <iostream>
#include <ctime>
using namespace std;
unsigned int getTriangular( unsigned int n)
{
return n*(n+1)/2;
}
unsigned int getPentagonal( unsigned int n)
{
return n*(3*n-1)/2;
}
unsigned int getHexagonal( unsigned int n)
{
return n*(2*n-1);
}
int main(int argc, char** argv)
{
clock_t begin = clock();
/* starting code */
unsigned int h = 143 + 1;
unsigned int p = 165;
unsigned int t = 285;
unsigned int hn = getHexagonal( h);
unsigned int pn = getPentagonal( p);
unsigned int tn = getTriangular( t);
while( true) {
if ((hn == pn) && (hn == tn)) {
break;
}
if( hn < pn) {
while( hn < pn) {
h++;
hn = getHexagonal( h);
}
continue;
}
if( pn < tn) {
while( pn < tn) {
p++;
pn = getPentagonal( p);
}
}
if( tn < hn) {
while( tn < hn) {
t++;
tn = getTriangular( t);
}
}
}
/* end of code */
cout << "found number '" << hn << "' at h=" << h << ", p=" << p << ", t=" << t << endl;
clock_t end = clock();
std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
return 0;
}
구글링을 해보니 더 효율적으로 풀려면 hexagonal 과 triangular 의 성질을 이용할 수 있다. 하지만 0.002초로 충분히 빨라서 딱히 안 고쳤다.