根据 Böhm-Jacopini 定理,可以仅使用三个语句来编写算法:
- 顺序
- 选择
- 迭代
很多老师都认为定理是一种信仰行为,他们教导不要使用(goto、jump、break、multiple return 等),因为这些指令是邪恶的。
但是当我要求解释时,没有人能够提供定理的证明。
我个人不认为这个定理是错误的,但我认为它在现实世界中的适用性并不总是更好的选择。
所以我做了一个小小的搜索,这些是我的疑问:
该定理已在流程图结构上进行归纳证明,但它真的适用于计算机程序吗?
根据维基百科,“Böhm 和 Jacopini 的作为程序转换算法并不真正实用,因此为在这个方向上的进一步研究打开了大门”。定理的一个结果证明每个“goto”都可以通过归纳转化为选择或迭代,但效率呢?我找不到任何证据表明可以重写每个算法以保持相同的性能。
递归,递归算法真的可以只使用序列、选择和迭代来编写吗?我知道一些递归算法可以优化为循环(想想尾递归),但真的可以适用于所有人吗?
干净的代码,我知道滥用跳转会产生可怕的代码,但我认为在某些情况下正确使用循环中的中断可以提高代码的可读性。
样本:
n = 0;
while (n < 1000 || (cond1 && cond2) || (cond3 && cond4) || (cond5 && cond6))
{
n++;
//The rest of code
}
可以改写为:
for (n = 0; n < 1000; n++)
{
if (cond1 && cond2) break;
elseif (cond2 && cond3) break;
elseif (cond4 && cond5) break;
elseif (cond6 && cond7) break;
//The rest of code
}
就我个人而言,我认为这个定理并不是为了编写更好的代码而创建的,干净的代码必须遵循这个定理的想法已经因为一个奇怪的主观原因传播到了世界上。
- 我发现了这篇有趣的文章:https :
//www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf 我认为这证明了不能强迫真正的程序遵循 Jaopini 定理。
你有同样的结论吗?
总结这个问题,我需要知道一个只使用(序列、选择和迭代)的程序是否真的比任何其他使用不同语句的程序更好,以及是否有证明或者是否都是主观的。