纳金网

标题: C#递归求解楼梯问题优化方案 [打印本页]

作者: 刀锋狼 时间: 2015-1-28 23:48
标题: C#递归求解楼梯问题优化方案
Q : 楼梯有N（小于50的整数）阶，上楼可以一步上一价，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。(递归实现)

方法一、
public long ladder(int num)
{
   if (num == 1) return 1;
   if (num == 2) return 2;
   return ladder(num - 1) + ladder (num - 2);
}
方案一简单粗暴，也是网上大部分解决此问题的方法，但是，当num值超过50时，就需要等待一分多钟才能求出结果，数值越大，越慢。
因此，必须对递归算法进行优化。方案：用数组arr[n] 记录当num = n时，递归调用后的返回值（此返回值确保不为0），当下次递归调用方法时判断 arr[n]是否不为0（因为arr初始化为0），如过不为0，说明已经递归计算过arr[0]的值了，没有必要再次进行漫长的递归计算，直接返回arr[n]的值即可。
C#代码如下，优化后，速度提高 n 倍：

class MainClass
{
      public long[] arr;
      public static void Main(string[] args)
      {
//输入的数越大越明显，如：50
         Console.Write("请输入阶梯数 : ");
         MainClass mc = new MainClass();
         int n = Convert.ToInt32(Console.ReadLine());
         mc.arr = new long[n + 1];
         long m = mc.TaiJie(n);
         Console.WriteLine(n + " 个阶梯，共有 " + m + " 种不同走法");
      }
      public long TaiJie(int num)
      {
         if(num == 1){
            return 1;
         }
         if(num == 2){
            return 2;
         }
         if(0 != arr[num]){
            return arr[num];
         }
         arr[num - 1] = TaiJie(num - 1);
         arr[num - 2] = TaiJie(num - 2);
         return arr[num - 1] + arr[num - 2];
      }
}

作者: HIDEOKOJIMA 时间: 2015-1-29 00:13
Thanks for sharing this one !

欢迎光临纳金网 (http://go.narkii.com/club/)