• 欢迎访问我爱CSharp学习网,这里有最新最全的C#书籍,C#视频。
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏我爱C#学习网吧
  • 推荐使用最新版Chrome浏览器和火狐浏览器访问本网站

C#完美实现斐波那契数列

C#杂烩 52csharp 841次浏览 0个评论 扫描二维码

斐波那契数列(1,1,2,3,5,8,…),用函数表示为f(n)=f(n-1)+f(n-2) (n>2,f(1)=1,f(2)=1)。


首先一般想到递归算法: 


/// <summary>
/// Use recursive method to implement Fibonacci
/// </summary>
/// <param name=”n”></param>
/// <returns></returns>
static int Fn(int n)
{
 if (n <= 0)
 {
  throw new ArgumentOutOfRangeException();
 }
 if (n == 1||n==2)
 {
  return 1;
 }

 // when n>46 memory will  overflow

 return checked(Fn(n – 1) + Fn(n – 2));
}


递归算法时间复杂度是O(n2),空间复杂度也很高的。


当然不是最优的。


自然我们想到了非递归算法了。


一般的实现如下:


/// <summary>
/// Use three variables to implement Fibonacci
/// </summary>
/// <param name=”n”></param>
/// <returns></returns>
static int Fn1(int n)
{
 if (n <= 0)
 {
  throw new ArgumentOutOfRangeException();
 }
 int a = 1;
 int b = 1;
 int c = 1;
 for (int i = 3; i <= n; i++)
 {

  // when n>46 memory will overflow

  c = checked(a + b);
  a = b;
  b = c;
 }
 return c;
}

 

这里算法复杂度为之前的1/n了,比较不错哦。


但是还有可以改进的地方,我们可以用两个局部变量来完成,看下吧:

 

/// <summary>

/// Use less variables to implement Fibonacci
/// </summary>
/// <param name=”n”></param>
/// <returns></returns>
static int Fn2(int n)
{
 if (n <= 0)
 {
  throw new ArgumentOutOfRangeException();
 }
 int a = 1;
 int b = 1;
 for (int i = 3; i <= n; i++)
 {

  // when n>46 memory will overflow

  b = checked(a + b);
  a = b – a;
 }
 return b;
}

 

好了,这里应该是最优的方法了。


值得注意的是,我们要考虑内存泄漏问题,因为我们用int类型来保存Fibonacci的结果,所以n不能大于46(32位操作系统)。


我爱CSharp学习网 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明C#完美实现斐波那契数列
喜欢 (1)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址