现在的位置: 首页 > 综合 > 正文

C#算法之递推法

2011年12月17日 ⁄ 综合 ⁄ 共 745字 ⁄ 字号 评论关闭

  1:斐波那契数列算法,如:1,1,2,3,5,8,13,21…… ,可以看到这里面的规律吧.就是每一项是前面相邻两项之和.求第N项。

       递归法:  

1 public static int Fibonacci(int n) { 
2                 //参数合法性验证 
3                 if (n < 1)
4                     Console.WriteLine("参数必须大于1!");
5                 if (n == 1 || n == 2) 
6                     return 1;
7                 else 
8                     return Fibonacci(n - 1) + Fibonacci(n - 2); 
9         }     
  非递归方式 
 2   public static int fx(int n) { 
 3                 //参数合法性验证 
 4                 if (n < 1) 
 5                     Console.WriteLine("参数必须大于1!"); 
 6                 //n为1或2时候直接返回值 
 7                 if (n == 1 || n == 2) return 1; 
 8                 //n>2时候循环求值 
 9                 int Nn = 0; 
10                 int N1 = 1; 
11                 int N2 = 1; 
12                 for (int i = 3; i <= n; i++) {
13                     Nn = N1 + N2;
14                     N1 = N2;
15                     N2 = Nn; 
16                 }
17                 return Nn; 
18         } 

    总结:递归的代码简单些,不过递归总体来说是以内存换时间,速度快,耗内存。

             非递归比较省内存,速度稍微慢些。
    出题:1,5,11,27,65,157,。。。,N。求第N项是多少?斐波那契变式。
 

 1 public static int Fibonacci(int n) { 
 2                 //参数合法性验证 
 3                 if (n < 1)
 4                     Console.WriteLine("参数必须大于1!");
 5                 if (n == 1)
 6                     return 1;
 7                 else if (n == 2)
 8                     return 5;
 9                 else 
10                     return Fibonacci(n - 1)*2 + Fibonacci(n - 2); 
11         }

  有空大家可以思考其他方式。

抱歉!评论已关闭.