一段你永远无法知道其运行时间上限的代码

类别:软件工程 点击:0 评论:0 推荐:

今天上数据结构课,老师给了我们下面这段暴经典的代码。你也可以看一看。

你可以毫无障碍地分析出它的下限为log2(n),但是问题在于,似乎没有人能够证明,对于任意的正整数n,这个程序都不会陷入死循环。于是,你也就无法分析出它的上限了。

你可以吗?

#include "iostream"

bool IsOdd(int n) {

 if(n % 2 == 0)
  return false;
 else
  return true;

}

int main() {

 int n;
 std::cin>>n;
 std::cout<<std::endl;

 while(n > 1) {

  if(IsOdd(n))
   n = 3 * n + 1;
  else
   n /= 2;
  std::cout<<n<<std::endl;
 
 }

 return 0;

}

本文地址:http://com.8s8s.com/it/it33612.htm