计算机的最长运行时间

计算机的最长运行时间

题目:假设有一台迷你计算机,1KB的内存,1MHZ的cpu,已知该计算机执行的程序可出现确定性终止(非死循环),问如何求得这台计算机上程序运行的 最长时间,可以做出任何大胆的假设。

分析:任何时候内存状态都不能相同,否则进入死循环:假设某2个时刻t1,t2满足t1小于t2,内存的状态完全相同,那么到达t2时刻又想当于回到了t1的执行位置。1k的内存共有状态 2^(1024*8)个(相当大)每秒cpu为1m,一秒钟改变1m次,所以两者相除即可得CPU的最长运行时间。

网络转载请注明:转载自程序员面试之家

并注明本文链接地址: 计算机的最长运行时间

1 Comment

  • ygm  said:

    首先程序是确定性的,就说明内存的状态不会重复,否则就永远结束不了。从这一点出发,可以知道内存的状态共有 2^8k , 然后CPU每秒改变 2^20 个状态,所以这台计算机最长出现不重复的状态 2^(8k-20)秒。

发表评论

电子邮件地址不会被公开。 必填项已用*标注