조띵의지극히개인적인공간


원문

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

[편집]번역

피타고라스 수는 a < b < c 이고 다음을 만족하는 3개의 자연수의 쌍입니다.

a2 + b2 = c2

예를 들어 32 + 42 = 9 + 16 = 25 = 52 입니다.

a + b + c = 1000 인 피타고라스 수는 딱 하나가 있습니다.

곱 a*b*c는 얼마인가요



내맘대로 해설 :
피타고라스 수의 정의상 a가 짝수면 b는 홀수다.

a < b < c
a < b < 1000 - a - b
2a+b < a + 2b < 1000

c의 값은 a,b를 가지고 구할수 있기 때문에 for 루프는 2개만 있으면 된다.



void func()
{
int va=0;
for (int a=1; a<1000; a++)
{
va=a*a;  //반복사용하는 값인 미리계산
for (int b=a+1; b<1000; b+=2)  //a와 b는 서로소 이기때문에 *2씩 증가할 수 있다.
{
if (2*a+b>=1000) break;  // 2a+b < 1000  이 조건문으로 불필요한 루프는 타지 않게 함
if (a+2*b>=1000) break;  // a+2b < 1000  이 조건문으로 불필요한 루프는 타지 않게 함
int c = (1000-a-b);
if (va+b*b == c*c)
{
printf("a[%d], b[%d], c[%d] \n",a,b,c) ;
return;
}
}
}
}










저작자 표시
신고
Posted by 조띵

1000자리 수에서 가장 큰 연속한 자릿수 5개의 곱은 얼마인가요?


Find the greatest product of five consecutive digits in the 1000-digit number.


내맘대로 해설:
 번역이 애매모호해서 원문을 보니 이해가 되었다. 주어진 1000자리 수 중에서 연속한 5개 숫자의 곱 중 가장 큰 값은?

문제를 보고 처응 떠오른 아이디어는 순차적으로 계산하되 다음으로 넘어갈때 처음 숫자를 나누고 다음 숫자를 곱하면 되겠다 했는데... 
중간에 0이라는 놈 때문에 그렇게 할순 없었고...
 
결국 순차적으로 계산하고 대신 0을 만날경우 바로 0 다음부터 계산하는 루틴을 넣었다. 워낙 미비한거라.. 실제 속도에 큰영향을 끼치진 못할듯 하다.






void func()
{
char Numbers[]="73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450";

int MaxValue=0;
for (int i=0; i<sizeof(Numbers)/sizeof(char); i++)
{
bool FoundZero = false;
int Value=1;
for (int o=i; o<i+5; o++)
{
if (Numbers[o]=='0')
{
FoundZero = true;
i=o;
break;
}
Value *= Numbers[o]-'0';
}
if (FoundZero) continue;

MaxValue = max(MaxValue, Value);
}

printf("MaxValue = %d\n", MaxValue);
}


저작자 표시
신고
Posted by 조띵
소수 중 처음 6개를 나열하면 2, 3, 5, 7, 11, 13 이다. 이 때 6번째 소수는 13이다.

10001번째 소수는 무엇인가?



내맘대로 해설 :
 숫자를 증가시키면서 소수 리스트를 만들고 10001째 소수를 검출해낸다. 당연하지만 딱히 다른방법은 떠오르지 않네..





void func()
{
int Prime[20000]={0};
int PrimeCount=0;

for (int i=2; PrimeCount<=10001 ; i++)
{
int n;
for (n=0; n<PrimeCount; n++)
{
if (i%Prime[n]==0) break;
}
if (n!=PrimeCount) continue;

Prime[PrimeCount++]=i;
}
printf("10001st Prime = %d\n", Prime[10001]);

}
저작자 표시
신고
Posted by 조띵

1부터 10까지의 자연수의 제곱의 합은 아래와 같습니다.

12 + 22 + ... + 102 = 385

1부터 10까지의 자연수의 합의 제곱은 아래와 같습니다.

(1 + 2 + ... + 10)2 = 552 = 3025

1부터 10까지의 자연수의 합의 제곱과 제곱의 합의 차는 3025 - 385 = 2640 입니다.

1부터 100까지의 자연수의 합의 제곱과 제곱의 합의 차는 얼마인가요?




내맘대로 해설:
문제가 너무쉬워 출제 의도가 의심스럽다. 뭔가 더 좋은 방법이 있을것 같지만 이문제는 여기까지




void func()
{
int Multiple = 0;
int Sum = 0;
for (int i=1; i<=10; i++)
{
Multiple += i*i;
Sum+=i;
}
Sum=Sum*Sum;

printf("Multiple=%d\n", Multiple);
printf("Sum=%d\n", Sum);
printf("Difference=%d\n", Sum-Multiple);
}
저작자 표시
신고
Posted by 조띵
2520은 1에서 10까지의 모든 수로 나누어 떨어집니다.

1부터 20까지의 수로 모두 나누어 떨어지는 가장 작은 수는 얼마인가요?





내맘대로 해설:
 답은 1부터 20까지의 최소 공배수를 구하는 것이다.  x와 y 두 수가 있다면 이 수는 
  x= a * x'
  y= a * y'
로 표현 할수 있고 여기서 a는 최대 공약수가 된다. 그렇다면 최소 공배수는 x * y' 이다.


void func()
{
int Value = 20;
for (int i=20; i>=1; i--)
{
for (int o=i-1; o>=1; o--)
{
if (Value%o==0 && (i-1)%o==0)
{
Value=Value*(i-1)/o;
break;
}
}
}

printf("Value=%d\n", Value);
}
저작자 표시
신고
Posted by 조띵

대칭수는 앞으로 읽으나 뒤로 읽으나 같은 수를 말합니다. 2자리 수의 곱으로 표현된 가장 큰 대칭수는 9009 = 91 × 99  입니다.

3자리 수 두개의 곱으로 이루어진 대칭수 중 가장 큰 수는 얼마인가요?



내맘대로 해설 :
 for문 두개로 간단히 해결하였으나... 뭔가 더 빠른 방법이 있을듯 하다..





void func()
{
int x, y;

for (x=999; x>=100; x--)
{
for (y=999; y>=100; y--)
{
int value= x*y;

if (value / 100000 == value%10 && value%100000/10000 == value%100/10 && value%10000/1000 == value%1000/100)
break;
}

if (y!=99) break;
}

printf("x=%d y=%d value=%d\n", x, y, x*y);
}
저작자 표시
신고
Posted by 조띵

13195의 소인수는 5, 7, 13, 29 입니다.

600851475143 의 소인수 중 가장 큰 수는 얼마인가요?



내맘대로 해설:

6천억번 루프를 돌렸으나 10분이 지나도 결과가 나오지 않아 다른 방법을 찼게되었다.

의외로 해법은 간단했다. 2부터 값을 증가 시키면서 나누어 떨어질때까지 나누면 된다.



void func()

{

__int64 Number = 600851475143;


for (__int64 i=2; i<Number; i++)

{

while(Number%i==0)

{

Number/=i;

}

}


printf("Number=%d", Number);

}



출처 : http://euler.toepeu.net/

저작자 표시
신고
Posted by 조띵

피보나치 수열의 새 항은 이전의 두 항의 합으로 만들어집니다. 1과 2로 시작한 10개의 항은 아래와 같습니다.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

피보나치 수열의 4백만을 초과하지 않는 항 중 짝수를 모두 더한 값은 얼마인가요?





내맘대로 해설 : 
피보나치 수열은 3번 주기로 짝수가 된다.
F(n) 에서 n이 5보다 크면
F(n) = F(n-1)+F(n-2)          // 각각의 항을 풀면
       = F(n-2)+F(n-3) + F(n-3) + F(n-4)   // 첫번쨰 F(n-2)만 풀면
       = F(n-3) + F(n-4) + F(n-3) + F(n-3) + F(n-4)  // 정리하면
       = F(n-3) * 3 + F(n-4) * 2


다음과 같은 식을 얻을 수 있다.
F(n)*3 + F(n-1)*2 = F(n+3)



int _tmain(int argc, _TCHAR* argv[])
{
unsigned int Sum=2;
int n=2, n_1=1;

for (int i=5; Sum<4000000; i+=3)
{
int oldn = n;
int oldn_1= n_1;
Sum+=oldn*3+oldn_1*2;

n=oldn*3+oldn_1*2;
n_1 = n - (oldn + oldn_1);
}

printf("Sum=%d", Sum);

return 0;
}



저작자 표시
신고
Posted by 조띵

그냥 시간날때마다 한문제씩 풀어보고자 한다.



오일러 프로젝트 1번.

10 미만의 자연수 중 3과 5의 배수를 나열하면 3, 5, 6, 9가 있습니다. 이 배수의 합은 23입니다.

1000 미만의 자연수 중 3과 5의 배수를 모두 더한 값은 얼마인가요?



내맘대로 해설:

for문을 1000번 돌리고 3혹은 5로 나누어 떨어지는 수의 합을 계산해도 되지만 그럼 1000번의 루프동안 2번의 나머지 계산을 해야한다. 총 2000번 나머지 계산.

이를 개선하기 위해 3배수로 합을 구하고, 5배수로 합을 구하고 그리고 최소공배수인 15의 합을 빼는방법으로 총 600번정도의 루프의 계산식으로만 결과를 얻어냈다.


#include <stdio.h>


int _tmain(int argc, _TCHAR* argv[])

{

int Count = 1000;

int Sum = 0;

for (int i=5; i<Count; i+=5) Sum+=i;

for (int i=3; i<Count; i+=3) Sum+=i;

for (int i=15; i<Count; i+=15) Sum-=i;


printf("Sum=%d", Sum);


return 0;

}






출처 : http://euler.toepeu.net/





저작자 표시
신고
Posted by 조띵
명목은 동영상 편집
실제는....................알수없음..


저가로 조립할까 하다가 이것만높여야지 이것만 높여야지 하다가 결국
하드디스크도 안샀는데 데탑만 88만원..-_-;

와우 테스트 결과 1280x1024 풀옵, 필드에서 60프레임이 나온다.
이제 모니터만 사서 1920X1080에서 만 해보면 될듯?



저작자 표시
신고
Posted by 조띵


티스토리 툴바