简明现代魔法 -> 计算机算法 -> 不使用递归求解裴波那契数列

不使用递归求解裴波那契数列

2010-09-15

裴波那契数列 1,1,2,3,5,8,13,21…………,一般来说使用递归会使问题简单很多。但是有些时候会要求我们不用递归解决这类问题,比如Lisp这种不支持递归的语言,或者对程序的执行效率要求很高,或者面试等等场合。本文给出一种不使用递归求解裴波那契数列的方案。

下面是递归的解法:

public int sum(int n)
{
  if(n<3)
    return 1;
  else
    return sum(n-1) + sum(n-2);
}

不使用递归的话可以用下面的函数实现:

public int sum(int n)
{
  if(n<3)
    return 1;
  else
  {
    int base1 = 1;
    int base2 = 1; int temp;
    for(int i=3; i<=n; i++)
    {
      temp = base2;
      base2 += base1;
      base1 = temp;
    }
    return base2;
  }
}

PHP程序测试如下:

    
<?php
$origin = 6;
$result = sum($origin);
echo $result;
function sum($n)
{
	if($n < 3)
	{
		return 1;
	}
	else
	{
		$base1 = 1;
		$base2 = 1; 
		$temp;
		for($i=3; $i <= $n; $i++)
		{
			$temp = $base2;
			$base2 += $base1;
			$base1 = $temp;
		}
		return $base2;
	}
}
?>
随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们