1

我写了以下代码：

combinationsstring = "List of Combinations"
for a = 0, 65 do
    for b = 0, 52 do
        for c = 0, 40 do
            for d = 0, 28 do
                for e = 0, 19 do
                    for f = 0, 11 do
                        for g = 0, 4 do
                            if (((1.15^a)-1)+((20/3)*((1.15^b)-1))
                               +((100/3)*((1.15^c)-1))+(200*((1.15^d)-1))
                               +((2000/3)*((1.15^e)-1))+((8000/3)*((1.15^f)-1))
                               +((40000/3)*((1.15^g)-1))) < 10000 then
                                combinationsstring = combinationsstring
                                    .."\n"..a..", "..b..", "..c..", "..d
                                    ..", "..e..", "..f..", "..g
                            end
                        end
                    end
                end
            end
        end
    end
end

local file = io.open("listOfCombinations.txt", "w")
file:write(combinationsstring)
file:close()

我需要找到符合以下等式的所有数据集

(((1.15^a)-1)+((20/3)*((1.15^b)-1))+
((100/3)*((1.15^c)-1))+(200*((1.15^d)-1))+
((2000/3)*((1.15^e)-1))+((8000/3)*((1.15^f)-1))+
((40000/3)*((1.15^g)-1))) < 10000

每个变量 (ag) 都是一个实整数。所以我计算了 7 个中的每一个的最大值（每个变量的最大值将是当所有其他值都为 0 时）。这些最大值分别为 65、52、40、28、19、11 和 4（62 = a，52 = b 等等）

因此，我创建了 7 个嵌套的 for 循环（如上面的代码所示），在中间块中，我测试了 7 个值以查看它们是否符合标准，如果符合，则将它们添加到字符串中。在代码的最后，程序将覆盖一个文件并将最终的字符串放入包含所有可能的组合。

该程序运行良好，但是在此模拟过程中执行了 31 亿次计算，并且通过一些测试，我发现我的计算机平均每秒进行 3000 次计算。这意味着总的模拟时间约为 12 天零 5 小时。我没有任何时间，所以我花了整个上午来简化要测试的方程式，删除不必要的代码，这就是我的最终结果。

我使用嵌套 for 循环完成的这种方法是这里最优化的方法吗？如果是，有没有其他方法可以加快速度，如果没有，你能告诉我另一种方法吗？

PS 我使用 Lua 是因为它是我最熟悉的语言，但是如果您有其他建议/示例，请用您的语言使用它，我可以尝试针对该程序进行优化。

4

4 回答 4

3

我不会说lua，但这里有一些建议：

  • 在开始循环之前b，计算和存储1.15^a-1；也许叫它fooa。
  • 同样，在开始循环之前c，计算fooa+(20/3)*(1.15^b-1); 也许叫它foob。
  • 在开始每个循环之前做类似的事情。
  • 例如，如果foob至少是10000，则跳出循环；里面的东西只会让结果更大。
  • 这在 lua 中可能没用或更糟，但是您真的需要将结果累积到字符串中吗？我不知道 lua 如何表示字符串并进行连接，但连接可能会严重伤害您。尝试使用列表或数组数据结构。

我还要补充一点，嵌套循环是一个非常明智的解决方案，并且通过上述修改，这正是我会做的。

于 2013-09-23T03:08:09.993 回答
2

我会推荐一种静态语言来暴力破解这种性质的事情。我遇到了一个问题（这个），我在使用 python 时遇到了问题，但是 C++ 蛮力 8-for-loop 方法可以在 30 秒内计算出解决方案。

于 2013-09-23T03:50:15.537 回答
0 
local res={}
combinationsstring = "List of Combinations"
--for a = 0, 65 do
        a=0
    for b = 0, 52 do
        for c = 0, 40 do
            for d = 0, 28 do
                for e = 0, 19 do
                    for f = 0, 11 do
                        for g = 0, 4 do
                            if (((1.15^a)-1)+((20/3)*((1.15^b)-1))
                               +((100/3)*((1.15^c)-1))+(200*((1.15^d)-1))
                               +((2000/3)*((1.15^e)-1))+((8000/3)*((1.15^f)-1))
                               +((40000/3)*((1.15^g)-1))) < 10000 then
                                        res[#res+1]={a,b,c,d,e,f,g}
                            end
                        end
                    end
                end
            end
        end
    end
--end

在我的机器上运行 30 秒并填充大约 1 GB 的内存。你不能在 32 位 Lua VM 中放 66 倍，在 64 位 LuaVM 中，表的数组部分仍然限制为 32 位整数键。

我已经评论了最外层的循环，所以你需要大约 30s*66=33min。我可能会将其写入 66 个不同的文件。结果首先保存在一个表中，然后可以将其连接起来。查看：

local res={
    {1,2,3,4,5,6,7},
    {8,9,10,11,12,13,14}
}

for k,v in ipairs(res) do
    -- either concatenate each line and produce a huge string
    res[k]=table.concat(v,", ")
  -- or write each line to a file in this loop
end

local text=table.concat(res,"\n")
print(text)

印刷

1, 2, 3, 4, 5, 6, 7
8, 9, 10, 11, 12, 13, 14
于 2013-09-25T14:30:25.977 回答
0

由于您还要求使用不同语言的解决方案，这是一个快速而肮脏的 C++ 程序，也包含了@tmyklebu 的建议。

#include <iostream>
#include <fstream>
#include <cmath>

int main()
{
    std::ofstream os( "listOfCombinations.txt" );
    using std::pow;
    for( double a = 0; a <= 65; ++a ) {
        double aa = (pow(1.15, a) - 1);
        if ( aa > 10000 ) break;
        for( double b = 0; b <= 52; ++b ) {
            double bb = aa + (20/3) * (pow(1.15, b) - 1);
            if ( bb > 10000 ) break;
            for( double c = 0; c <= 40; ++c ) {
                double cc = bb + (100/3) * (pow(1.15, c) - 1);
                if ( cc > 10000 ) break;
                // The following line provides some visual feedback for the
                // user about the progress (it prints current a, b, and c
                // values).
                std::cout << a << "   " << b << "   " << c << std::endl;
                for( double d = 0; d <= 28; ++d ) {
                    double dd = cc + 200 * ( pow(1.15, d) - 1);
                    if ( dd > 10000 ) break;
                    for( double e = 0; e <= 19; ++e ) {
                        double ee = dd + (2000/3) * (pow(1.15, e) - 1);
                        if ( ee > 10000 ) break;
                        for( double f = 0; f <= 11; ++f ) {
                            double ff = ee + (8000/3) * (pow(1.15, f) - 1);
                            if ( ff > 10000 ) break;
                            for( double g = 0; g <= 4; ++g ) {
                                double gg = ff + (40000/3) * (pow(1.15, g) - 1);
                                if ( gg >= 10000 ) break;
                                os << a << ", " << b << ", " 
                                    << c << ", " << d << ", " 
                                    << e << ", " << f << ", " 
                                    << g << "\n";
                            }
                        }
                    }
                }
            }
        }
    }

    return 0;
}
于 2013-09-24T09:58:22.883 回答