聘我网

新概念招聘3.0

停机问题 - 所有存储量为N的机器上的程序最多运行多久?

vote up0vote downstar

有这么一个计算机:

  1. 存储量为N bytes,包含了内存、Cache,等等所有表示状态的东东
  2. CPU为M赫兹

如果在这上面运行一个一定可以结束的程序,这个程序最多可以运行多久?

 

1 个答复

vote up0vote down

贴一下答案:(2^8N)/M秒

理由是这样的:

  1. 一个byte是8个bit,这是8的bit,N个byte,就是8N个bit,代表着 2^8N 种状态
  2. 不论怎么编码,当程序终止的时候,已经是某一个状态,而且这个状态之前没有经过过(否则早就终止了)
  3. 在任意一个时刻,这些所有表示状态的东东,都不会出现重复,也就是说:已经够经过的状态不会再在后面出现了,否则,你已经猜到了,那就是死循环
  4. 所以最厉害的程序最多跑遍2^8N种状态
  5. CPU是M赫兹,也就是一秒会切换M个状态

所以结果就是 (2^8N)/M

链接

您的回答





不是您要找的问题? 浏览其他含有标签 的问题或者 自己问个.