下面是题目 和 我想到的最优算法，大家看看有没有更好的算法

/*编写一个应用程序，验证以下等式是成立的：
3^3+4^3+5^3=6^3;
6^3+7^3+...+69^3=180^3;
找到更多的这样的整数：一些相续正整数的立方和正好等于另一个整数的立方。*/

#include <stdio.h>
#define N 1200 //大于1200后就快越界了

int main(void)
{
    int x[N];
    long sum = 0;
    for (int i = 0; i < N; i++)// 把0到N之间的的数的3次方赋值到对应下标的数组内，以提高运算速度
        x[i] = i * i * i;
    for (int i = 2; i < N; i++)//作为数组下标
        for (int j = 1; j < i; j++)//作为开始算的最小值
            for (int k = j; k < i; k++)//不断提高最左边值
            {
                sum += x[k];
                if (sum == x[i])
                {
                    printf("%d^3 + ...... + %d^3 = %d^3\n", j, k, i);
                    sum = 0;
                    break;
                }
                if (sum > x[i])//当前面的整数和大于目标值，中断循环以提高效率
                {
                    sum = 0;
                    break;
                }
            }

    return 0;
}

----------------------上面的算法有问题，更正为下面的------------------------------

#include <stdio.h>
#define N 5000 

int main(void)
{
    long x[N];
    long sum = 0;
    for (int i = 0; i < N; i++)// 把0到N之间的的数的3次方赋值到对应下标的数组内，以提高运算速度
        x[i] = i * i * i;
    for (int i = 2; i < N; i++)//作为数组下标
        for (int j = 1; j < i; j++)//作为开始算的最小值
            for (int k = j; k < i; k++)//不断提高最左边值
            {
                sum += x[k];
                if (sum == x[i])
                {
                    printf("%d^3 + ...... + %d^3 = %d^3\n", j, k, i);
                    sum = 0;
                    break;
                }
                if (k + 1 == i)// 修改了这里
                {
                    sum = 0;
                    break;
                }

            }

    return 0;
}

[此贴子已经被作者于2017-9-25 10:26编辑过]

我就发一幅图片,看看有没有启发~

并不是都从1开始，所以不能套用这个公式，比如3的立方+4的立方+5的立方 = 6的立方

所以说啊,不是从1开始的可以相减啊~之后就判断是否存在整数解集就可以啦~

时间复杂度理论上可以优化一个几何级别~

有道理啊，是一个新思路，我想想怎么写一下。不过时间复杂度应该是一样的

判断一个数N是否能分解成若干个连续的立方和……

第一次直接用公式判断是否存在解集……


第二次 n=N-1^3;
第三次 n=N-(1^3+2^3);
第四次 n=N-(1^3+2^3+3^3);
……
化了一下好像可以化出

根号((根号(1+8n)-1)/2)要为整数~

恕我不方便截图手写只能用这表达方式说明哈~

这方法理论上判断单个数时间复杂度为o(n);
总时间复杂度理论上为o(n^2);~

[此贴子已经被作者于2017-9-24 22:19编辑过]

还有一种逆向思维~

那公式是否是一个数的立方?~

感觉这样更加简单~

不过如果要按顺序输出的话要另外处理例如要另外找个存储结构进行保存才行~