简明现代魔法 -> 计算机算法 -> 楼梯问题的一些解决方法

楼梯问题的一些解决方法

2011-02-18

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

    
①:1 1 1
②:1 2
③:2 1

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

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

<?php

function up($n)
{
	if($n == 2)
		return 2;
	elseif($n == 1)
	return 1;

	return up($n-1)+up($n-2);
}

for($i = 1; $i < 10; $i++)
{
	echo up($i).'<br />';
}

?>

程序运行结果:

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));
随机文章推荐
网站分类


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

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


 

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

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