如何优化for循环？

Question

我有一个问题,让我们说:找到所有两对数字(x,y)和(z,t),使x³+y³=z³+t³,其中(x,y)!=(z,t)和x³ +y³<10,000.

取10,000 10,000的立方根21.544 - >向下舍入到21,所以我得到:

#include <iostream>

using namespace std;

int main() {
    for( int x = 1; x <= 20; ++x ) {
        for( int y = x + 1; y <= 21; ++y ) {
            for( int z = x + 1; z <= y - 1; ++z ) {
                for( int t = z; t <= y - 1; ++t ) {
                    if( x*x*x + y*y*y == z*z*z + t*t*t ) {
                        cout << x << ", " << y << ", " << z << ", " << t << endl; 
                    }
                }
            } 
        }
    }
    return 0;
}

我知道这个代码可以进行更多优化,这就是我正在寻找的东西.另外,我的一个朋友告诉我y可能是x + 2而不是x + 1,我怀疑这是因为如果
x = 1,那么我们永远不会有y = 2,在这种情况下错过了一个可能的解决方案.

任何想法？

Answer 1

那么在给定当前循环结构的情况下可以进行一种明显的算法优化,通过将范围限制为10,000的立方根,可以非常正确地进行优化.但是,根据10,000 - x的立方根,您可以更进一步限制y的范围.这是你可以做的一件事.

另一个优化是,地球上没有理由认为这应该是4个循环.只需做2个循环并计算x ^ 3 + y ^ 3的值并检查重复.(这很好,如果你没有深入研究多维数据集根的功能.)这实际上并没有正确使用API​​,但你明白了:

multimap<int, std::pair<int, int> > map;
for (int i = 1; i < 21; i++) {
    (for int j = x; j < cube_root(10000 - i^3); j++ {
        multimap.insert (i^3 + j^3, std::pair<int, int>(i,j);

然后,您只需遍历多图并查找重复.