笔试题求答案

iptabler

假设有一台迷你计算机，有1KB内存和1MHZ处理器（假定1MHZ处理器能够每秒改变10^6次状态）。能够在这台计算机上运行且确定性终止（即运行到某种状态时必然终止，不存在死循环）的所有程序中，最长的运行时间可能是多少？（写出你的推理过程，可以做出任意你需要的假定）

yikaikai

∞∞∞∞∞∞∞∞∞∞∞

foolishx

一点思路都没有……

ameihualudeai1

关注中……

mcemil

猜测一下，大概的考点是不是：1KB的内存，存放任意cpu的指令，使得运行时间尽可能长。就是考察你对某种cpu构架的指令集以及他们的运行周期、指令长度、对齐方式是否了解。

随便说说，大家别砰

pagx

什么叫做死循环？ 循环100万次算么，1000万次算么？ N重循环呢？

rain_fish

gz

lemoncookie

1KB内存＝8K bit内存
这个限制应该是说明这台机器最多能够表示2^8K个不同状态
超出这个数目的状态就是不可控制的了，也就是说会出现死循环
那么结果应该就是2^8k / 10^6 (second)

[ 本帖最后由 lemoncookie 于 2009-10-15 13:39 编辑 ]

kouu

原帖由 lemoncookie 于 2009-10-15 13:12 发表
1KB内存＝8K byte内存
这个限制应该是说明这台机器最多能够表示2^8K个不同状态
超出这个数目的状态就是不可控制的了，也就是说会出现死循环
那么结果应该就是2^8k / 10^6 (second)

嗯，赞同。
实际上最长的运行时间就是把每一种状态都遍历一次，如果某种状态出现不止一次，那必定是死循环了。（因为同一状态下，必定有相同的下一状态。1+1就等于2，不会一会等于2，一会等于3。）

[ 本帖最后由 kouu 于 2009-10-15 13:42 编辑 ]

kouu

原帖由 kouu 于 2009-10-15 13:18 发表

嗯，赞同。
实际上最长的运行时间就是把每一种状态都遍历一次，如果某种状态出现不止一次，那必定是死循环了。

不过，感觉还是漏了一点。机器的状态除了内存状态以外，还有CPU本身的状态（可以看成是CPU寄存器的状态）。
那么，CPU有几个寄存器？ 这个就扯远了，可以做的假设太多。总之，CPU有多少寄存器，总的位宽度是多少，这些宽度所能表达的状态数跟内存本身所能表达的状态数乘在一起，就是总的状态数了。

另外，我们还可以做假设，假设CPU没有寄存器，内存的指定部分被当作CPU寄存器使用。 这样就能得出前面的结论。