2015. 2. 10. 18:21 Programing/Algorithm
프로젝트 오일러 4번
문제: 앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.
두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 x 99) 입니다.
세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까 ?
#include <stdio.h>
int main() {
int i, j;
int x;
int sol = 0;
int n1, n2, n3, n4, n5, n6;
for (i = 999; i > 100; i - )
for (j = 999; j > 100; j - ){
x = i * j;
n1 = x / 100000;
x = x % 100000;
n2 = x / 10000;
x = x % 10000;
n3 = x / 1000;
x = x % 1000;
n4 = x / 100;
x = x % 100;
n5 = x / 10;
x = x % 10;
n6 = x / 1;
if ((n1 == n6) && (n2 == n5) && (n3 == n4)){
printf("n1 = %d,n2 = %d,n3 = %d,n4 = %d,n5 = %d,n6 = %d \n", n1, n2, n3, n4, n5, n6);
x = i*j;
if (x > sol){
sol = x;
break;
}
}
}
printf("%d \n", sol);
}
3자리 x 3자리로 이루어진 가장 큰 대칭수는 6자리라고 단정 짓고 짠 알고리즘,
해답:
대칭수 P는 x,y,z로 구성 가능. P= a x b(a와 b는 100보다 크고 999보다 작은 정수)
P는 반드시 적어도 6자리로 긴 정수 일것이다. 왜냐하면 111111=143 x 777 이기 때문(P는 3자리 x 3자리로 이루어진 대칭수 111111보다 크거나 같을 것)
따라서,
P=100000x+10000y+1000z+100z+10y+x
P=100001x+10010y+1100z
P=11(9091x+910y+100z)
11은 소수로 반드시 a, b는 11을 약수로 가짐
따라서 11로 나누어 지지 않는다면 대칭수가 아님.
largestPalindrome = 0
a = 999
while a >= 100
if a mod 11 = 0
b = 999
db = 1
else
b = 990 //The largest number less than or equal 999
//and divisible by 11
db = 11
while b >= a
if a*b <= largestPalindrome
break
if isPalindrome(a*b)
largestPalindrome = a*b
b = b-db
a = a-1
output largestPalindrome
'Programing > Algorithm' 카테고리의 다른 글
프로젝트 오일러 6번 (0) | 2015.02.10 |
---|---|
프로젝트 오일러 5번 (0) | 2015.02.10 |
프로젝트 오일러 3번 (0) | 2015.02.10 |
프로젝트 오일러 2번 (0) | 2015.02.10 |
Kadane's Algorithm (0) | 2015.02.10 |