日复一日

厚积薄发|跳跃的人生
  IT博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  25 随笔 :: 2 文章 :: 6 评论 :: 0 Trackbacks
微软面试技术题（12）

三柱汉诺塔最小步数。

 1 int  f3(n) {
  2      if (f3[n])  return  f3[n];
  3      else   {
  4          if (n == 1 ) {
  5             f3[n] = 1 ;
  6              return   1 ;
  7         }
 8         f3[n] = 2 * f3(n - 1 ) + 1 ;
  9          return  f3[n];
 10     }
11 }


四柱汉诺塔最小步数。
 1int f4(n){
 2    if(f4[n]==0){
 3        if(n==1) {
 4            f4[1]==1;
 5            return 1;
 6        }
 7        min=2*f4(1)+f3(n-1);
 8        for(int i=2;i<n;++i){
 9            u=2*f4(i)+f3(n-i);
10            if(u<min) min=u;
11        }
12        f4[n]=min;
13        return min;
14    } else return f4[n];
15}
posted on 2006-06-16 20:41 GwQ 阅读(181) 评论(0)  编辑 收藏 引用 所属分类: 微软面试技术题
只有注册用户登录后才能发表评论。