2 qq 28635543 qq_28635543 于 2017.04.08 18:45 提问

一个算法对于一个输入的循环次数可以事先估计出来吗

一个算法对于一个输入的循环次数可以事先估计出来吗,一个选择题的选项

3个回答

caozhy
caozhy   Ds   Rxr 2017.04.08 23:12

有的可以,有的不可以。
这个问题非常有趣,属于停机问题判断的变种。
如果我们可以观察一个算法,而不执行它,知道它的循环次数(有限次/无限次),那么我们可以把哥德巴赫猜想、费马大定律等这些数论的难题用一个穷举算法表达,如果对于所有的数字都成立(没有反例)显然这个循环是无限的,永远不会执行完。如果能执行完,则证明猜想是错的。
如果真的有这样的办法可以估计,那么所有这类数学难题都可以迎刃而解了。
但是很不幸,停机问题被证明是无解的。

caozhy
caozhy   Ds   Rxr 2017.04.08 23:17

如果你有兴趣,可以进一步看这个视频:http://v.youku.com/v_show/id_XNDkyODExODY0.html

LiuJiuXiaoShiTou
LiuJiuXiaoShiTou   2017.04.16 08:48

图片说明

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!