프로젝트 오일러 문제 #93, Arithmetic Expressions는 네 개의 숫자를 이용해 가능한 모든 정수 값을 만들고, 그 중 가장 긴 연속된 정수 집합을 찾는 문제입니다. 이 문제의 목표는 네 개의 서로 다른 숫자를 선택한 후, 사칙연산과 괄호를 자유롭게 조합하여 만들 수 있는 모든 가능한 정수를 계산하는 것입니다. 예를 들어, 주어진 숫자가 1, 2, 3, 4라면, 이 네 숫자를 사용해 다양한 수식을 만들어내고, 그 수식을 통해 결과로 얻을 수 있는 모든 정수를 구하게 됩니다.
문제의 규칙은 다음과 같습니다.
1. 네 개의 숫자는 모두 서로 달라야 합니다.
2. 각 숫자는 한 번만 사용할 수 있습니다.
3. 사칙연산(+, -, *, /)과 괄호를 사용하여 가능한 많은 정수를 만들어냅니다.
4. 음수나 분수가 나오면 그 수는 무시되며, 양의 정수로 된 결과만을 집합에 포함합니다.
5. 그 후, 생성된 정수들 중에서 가장 긴 연속된 정수 시퀀스를 찾아야 합니다.
예를 들어 숫자 1, 2, 3, 4를 사용한다면, 가능한 수식들은 다음과 같습니다:
• (1 + 2) * (3 + 4) = 21
• (4 / (1 - (3 / 2))) = 양의 정수가 아니므로 무시
• (3 + 4) * (1 + 2) = 21
이렇게 네 숫자를 조합한 다양한 수식을 통해 만들어진 정수 집합에서 가장 긴 연속된 정수 시퀀스를 찾습니다.
제가 작성한 소스입니다.
//------------------------------------------------
// Project Euler #93 - Arithmetic Expressions
// - by Aubrey Choi
// - created at 2015-10-21
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
void calc(char values[], int a[], int ps[], int ni, int oi, int mask)
{
if( ni+oi == 7 )
{
double stack[10];
int sp = 0;
for( int i = 0 ; i < 7 ; i++ )
{
if( ps[i] < 10 ) stack[sp++] = ps[i];
else
{
double b = stack[--sp];
double a = stack[--sp];
if( ps[i] == '+' ) stack[sp++] = a+b;
else if( ps[i] == '-' ) stack[sp++] = a-b;
else if (ps[i] == '*') stack[sp++] = a * b;
else if (ps[i] == '/') { if( b == 0.0 ) return; stack[sp++] = a / b; }
}
}
if( stack[0] < 1 || stack[0] > 1000 ) return;
int out = stack[0];
if( stack[0] != out ) return;
values[out]++;
//for( int i = 0 ; i < 7 ; i++ )
//{
// if( ps[i] < 10 ) putchar(ps[i]+'0');
// else putchar(ps[i]);
//}
//printf("=%d\n", out);
return;
}
if( ni < 4 )
{
for( int i = 0 ; i < 4 ; i++ )
{
if( mask & (1<<i) ) continue;
ps[ni+oi] = a[i];
calc(values, a, ps, ni+1, oi, mask | (1<<i));
}
}
if( ni > oi + 1 )
{
int op[4] = { '+', '-', '*', '/' };
for( int i = 0 ; i < 4 ; i++ )
{
ps[ni+oi] = op[i];
calc(values, a, ps, ni, oi+1, mask);
}
}
}
void solve1()
{
char values[1024];
int ps[10];
int a[4];
int maxn = 1, maxv = 0;
for (a[0] = 1; a[0] < 10 ; a[0]++)
{
for (a[1] = a[0] + 1; a[1] < 10; a[1]++)
{
for (a[2] = a[1] + 1; a[2] < 10; a[2]++)
{
for( a[3] = a[2]+1; a[3] < 10 ; a[3]++ )
{
memset(values, 0, sizeof(values));
calc(values, a, ps, 0, 0, 0);
int c;
for( c = 1 ; values[c] ; c++ ) ;
if( maxn < c ) { maxn = c; maxv = a[0]*1000+a[1]*100+a[2]*10+a[3]; }
}
}
}
}
printf("Ans = %d (%d)\n", maxv, maxn);
}
int main()
{
clock_t t;
t = clock();
solve1();
printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}
이 코드는 프로젝트 오일러 문제 #93 “Arithmetic Expressions”의 해답을 찾는 프로그램입니다. 목표는 서로 다른 네 개의 숫자를 이용하여 사칙연산과 괄호를 사용해 가능한 모든 정수를 만들고, 연속된 가장 긴 정수 시퀀스를 찾는 것입니다. 이 프로그램은 가능한 조합과 연산을 모두 시도하고, 그 결과를 기반으로 가장 긴 연속된 정수 시퀀스를 만드는 네 개의 숫자 조합을 찾습니다. 각 부분을 자세히 설명하겠습니다.
주요 함수 및 변수 설명
1. calc 함수
void calc(char values[], int a[], int ps[], int ni, int oi, int mask)
{
if( ni+oi == 7 )
{
double stack[10];
int sp = 0;
for( int i = 0 ; i < 7 ; i++ )
{
if( ps[i] < 10 ) stack[sp++] = ps[i];
else
{
double b = stack[--sp];
double a = stack[--sp];
if( ps[i] == '+' ) stack[sp++] = a+b;
else if( ps[i] == '-' ) stack[sp++] = a-b;
else if (ps[i] == '*') stack[sp++] = a * b;
else if (ps[i] == '/') { if( b == 0.0 ) return; stack[sp++] = a / b; }
}
}
if( stack[0] < 1 || stack[0] > 1000 ) return;
int out = stack[0];
if( stack[0] != out ) return;
values[out]++;
//for( int i = 0 ; i < 7 ; i++ )
//{
// if( ps[i] < 10 ) putchar(ps[i]+'0');
// else putchar(ps[i]);
//}
//printf("=%d\n", out);
return;
}
if( ni < 4 )
{
for( int i = 0 ; i < 4 ; i++ )
{
if( mask & (1<<i) ) continue;
ps[ni+oi] = a[i];
calc(values, a, ps, ni+1, oi, mask | (1<<i));
}
}
if( ni > oi + 1 )
{
int op[4] = { '+', '-', '*', '/' };
for( int i = 0 ; i < 4 ; i++ )
{
ps[ni+oi] = op[i];
calc(values, a, ps, ni, oi+1, mask);
}
}
}
• 이 함수는 주어진 네 개의 숫자 조합으로 가능한 모든 수식을 계산하고 그 결과를 values 배열에 기록합니다.
• ni는 숫자의 개수를, oi는 연산자의 개수를 의미합니다.
• ps 배열은 숫자와 연산자들의 순서를 저장하는 배열입니다.
• mask는 숫자의 중복 사용을 방지하기 위해 비트를 이용해 사용된 숫자를 기록하는 역할을 합니다.
함수는 네 개의 숫자를 사용해 가능한 모든 수식을 재귀적으로 생성합니다. 숫자를 먼저 선택하고, 연산자를 뒤이어 선택하여 스택을 이용해 결과를 계산하는 방식입니다. 스택의 맨 위 두 값을 연산자로 계산하고 다시 스택에 넣는 형태로 계산을 진행합니다.
2. solve1 함수
void solve1()
{
char values[1024];
int ps[10];
int a[4];
int maxn = 1, maxv = 0;
for (a[0] = 1; a[0] < 10 ; a[0]++)
{
for (a[1] = a[0] + 1; a[1] < 10; a[1]++)
{
for (a[2] = a[1] + 1; a[2] < 10; a[2]++)
{
for( a[3] = a[2]+1; a[3] < 10 ; a[3]++ )
{
memset(values, 0, sizeof(values));
calc(values, a, ps, 0, 0, 0);
int c;
for( c = 1 ; values[c] ; c++ ) ;
if( maxn < c ) { maxn = c; maxv = a[0]*1000+a[1]*100+a[2]*10+a[3]; }
}
}
}
}
printf("Ans = %d (%d)\n", maxv, maxn);
}• values 배열을 초기화하고, 가능한 네 자리 조합 (1부터 9까지 숫자 중 네 개) 전체를 반복하여 calc 함수로 전달합니다.
• a[4] 배열은 네 개의 숫자를 저장하는 배열입니다.
• 각 조합에 대해 calc 함수로부터 얻은 결과를 values 배열에 저장하고, 결과값이 연속된 최대 길이를 확인합니다.
• maxn과 maxv 변수는 각각 최대 연속 길이와 해당 숫자 조합을 기록하는 역할을 합니다.
3. main 함수
• solve1 함수를 호출하여 문제의 답을 구하고, 최종 결과와 프로그램 실행 시간을 출력합니다.
코드 실행 흐름
• main 함수에서 solve1 함수가 호출됩니다.
• solve1 함수는 가능한 네 개의 숫자 조합을 반복하여 각각 calc 함수로 전달합니다.
• calc 함수는 네 개의 숫자와 사칙연산을 조합하여 가능한 모든 수식을 생성하고 결과값을 values 배열에 저장합니다.
• 연속된 정수의 최대 길이를 확인하여, 가장 긴 시퀀스를 가진 숫자 조합을 찾습니다.
• 최종 결과는 네 자리 숫자와 연속된 정수의 최대 길이로 출력됩니다.
요약하면, 가능한 모든 네 자리 숫자 조합과 수식을 계산하여 가장 긴 연속된 정수 시퀀스를 만들 수 있는 숫자 조합을 찾습니다.
'Programming > Project Euler' 카테고리의 다른 글
| [C/C++] 프로젝트 오일러 #95 Amicable Chains(수학) (2) | 2024.11.17 |
|---|---|
| [C/C++] 프로젝트 오일러 #94 Almost Equilateral Triangles(수학) (4) | 2024.11.16 |
| [C/C++] 프로젝트 오일러 #91 Right Triangles with Integer Coordinates(전체 탐색) (0) | 2024.11.11 |
| [C/C++] 프로젝트 오일러 #90 두개의 주사위로 제곱수 만들기(전체 검색) (0) | 2024.11.09 |
| [C/C++] 프로젝트 오일러 #89 Roman Numerals(계산) (0) | 2024.11.01 |
댓글