20111218

ACM 386 Perfect Cubes

由題目給的答案可以發現:
n^3 = a^3 + b^3 + c^3,
a <= b <= c。
所以迴圈就這樣寫即可!
a從2開始,b從a開始,c從b開始。
當a^3 + b^3 + c^3 < n^3時,c + 1。
a^3 + b^3 + c^3 == n^3時,找到一組,
a^3 + b^3 + c^3 > n^3時,b + 1。
a^3 + b^3 > n^3時,a + 1。
a == n時,終止。

/* ACM 386 Perfect Cubes
 * mythnc
 * 2011/12/18 12:17:31   
 * run time: 0.132
 */
#include <stdio.h>

#define CUBIC(X) (X * X * X)

void cal(int);

int main(void)
{
    int i;

    for (i = 6; i <= 200; i++)
        cal(i);

    return 0;
}

/* cal: calculate answer */
void cal(int n)
{
    int i, j, k, value;

    for (i = 2; i < n; i++)
        for (j = i; CUBIC(i) + CUBIC(j) < CUBIC(n); j++)
            for (k = j; ; k++) {
                value = CUBIC(i) + CUBIC(j) + CUBIC(k);
                if (value < CUBIC(n))
                    continue;
                else if (value == CUBIC(n))
                    printf("Cube = %d, Triple = (%d,%d,%d)\n", n, i, j, k);
                else
                    break;
            }
}

沒有留言: