Description
For hundreds of years Fermat's Last Theorem, which stated simply that for n > 2 there exist no integers a, b, c > 1 such that a^n = b^n + c^n, has remained elusively unproven. (A recent proof is believed to be correct, though it is still undergoing scrutiny.) It is possible, however, to find integers greater than 1 that satisfy the "perfect cube" equation a^3 = b^3 + c^3 + d^3 (e.g. a quick calculation will show that the equation 12^3 = 6^3 + 8^3 + 10^3 is indeed true). This problem requires that you write a program to find all sets of numbers {a,b,c,d} which satisfy this equation for a <= N.
Input
One integer N (N <= 100).
Output
The output should be listed as shown below, one perfect cube per line, in non-decreasing order of a (i.e. the lines should be sorted by their a values). The values of b, c, and d should also be listed in non-decreasing order on the line itself. There do exist several values of a which can be produced from multiple distinct sets of b, c, and d triples. In these cases, the triples with the smaller b values should be listed first.
Sample Input
24
Sample Output
Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)
代码如下：
版本1：
#include<stdio.h>
int main()
{
int i, j, k, l, n, s[101];
while (scanf("%d", &n)!= EOF)
{
for (i = 2; i <= n; i++)
{
s[i] = i * i * i;
}
for (i = 6; i <= n; i++)
{
for (j = 2; j < i; j++)
{
for (k = j; k < i; k++)
{
for (l = k; l < i; l++)
{
if (s[i] == s[j] + s[k] + s[l])
{
printf("Cube = %d, Triple = (%d,%d,%d)\n", i, j, k, l);
}
}
}
}
}
}
system("pause");
return 0;
}
版本2：
#include<stdio.h>
#define max 101
int L[3], s[max];
void Dfs(int x, int i, int n, int depth)
{
int j, sum = 0;
if (depth + 1 < 4)
{
L[depth++] = i;
for (j = 0; j < depth; j++)
{
sum += s[L[j]];
}
if (sum > s[x])
{
return;
}
else if(depth == 3 && s[x] == sum)
{
printf("Cube = %d, Triple = (%d,%d,%d)\n", x, L[0], L[1], L[2]);
}
else
{
for (j = i; j < x; j++)
{
Dfs(x, j, n, depth);
}
}
}
}
int main()
{
int i, n, j;
for (i = 0; i < max; i++)
{
s[i] = i * i * i;
}
while (scanf("%d", &n) != EOF)
{
n++;
for (i = 6; i < n; i++)
{
for (j = 2; j < i; j++)
{
Dfs(i, j, n, 0);
}
}
}
system("pause");
return 0;
}