上楼梯有几种走法问题

假设一个楼梯有 N 阶台阶，人每次最多可以跨 M 阶。例如楼梯总共有3个台阶，人每次最多跨2个台阶，也就是说人每次可以走1个，也可以走2个，但最多不会超过2个，那么楼梯总共有这么几种走法：

    
①：1 1 1
②：1 2
③：2 1

现在要求用程序实现计算台阶的所有走法的总数。

其实就是个斐波那契数列。下面是用递归方法来解决：

';
}
?>

程序运行结果：

1
2
3
5
8
13
21
34
55

非递归方法：

function up($n)
{
	$a = array(1, 2);
	for($i = 3; $i <= $n; $i++){
		$a[$i] = $a[$i-1] + $a[$i-2];
	}
	print_r($a);
}
up(10);

如果说要展示出所有的情况的递归方法：

function up_out($n)
{
	if($n == 1)
		return array('1 ');
	else if($n == 2)
		return array('1 1 ', '2 ');
	return array_merge(lian(up_out($n-1),'1 '), lian(up_out($n-2), '2 '));
}
function lian($a1, $a2)
{
	foreach($a1 as &$a1_v) {
		$a1_v = $a1_v . $a2;
	}
	return $a1;
}
print_r(up_out(10));

展示所有情况的非递归方法：

function up_out($n)
{
	$re = array(array(0), array('1 '), array('1 1 ', '2 '));
	for($i = 3; $i <= $n; $i++) {
		$re[$i] = array_merge(lian($re[$i-1], '1 '), lian($re[$i-2], '2 '));
	}
	return $re;
}
function lian($a1, $a2) {
	foreach($a1 as &$a_v) {
		$a_v = $a_v . $a2;
	}
	return $a1;
}
print_r(up_out(10));

本文地址：http://www.nowamagic.net/librarys/veda/detail/995，欢迎访问原出处。