为什么用于查找 GCD 的连续整数检查算法被认为是蛮力，而欧几里德算法却不是？我只是对此感到困惑。是不是因为我们在逐一检查？
问问题
1827 次
2 回答
2
蛮力算法尝试每一个可以尝试的候选解决方案，看看哪一个适合，并将其发现作为答案返回。例如，蛮力 GCD 算法将从两个数字中较小的一个开始，然后继续向下，在向下的1过程中逐个检查每一种可能性。
相比之下，欧几里得算法不会一一进行：它会发生跳跃，有时是非常重要的跳跃。此外，它不会在每一步检查每个可能的数字是否是 GCD 问题的解决方案：它的结束条件与典型的蛮力解决方案有很大不同，即检查当前候选者是否是问题的解决方案，并在答案为“是”时停止。欧几里得算法检查不同的条件，即b != 0来决定是否继续。
这两个区别（大步长和不同的停止条件）使欧几里得算法不同于蛮力算法。
于 2013-04-29T01:15:12.123 回答
0
A brute-force search involves trying every (reasonable) possibility. Euclid's algorithm only checks a very small subset of those possibilities.
于 2013-04-29T01:07:38.520 回答