先对杨辉三角有个印象
求 第 h 行 第 r 列的数值
返回的结果:
使用递归1:第 100 行第 4 列值是: 156849 ,共计算 387 次,耗时 0.001 s
不用递归2:第 100 行第 4 列值是: 156849 ,共计算 292 次,耗时 0.001 s
不用递归3:第 100 行第 4 列值是: 156849 ,共计算 389 次,耗时 0.003 s
使用递归1:第 1000 行第 4 列值是: 165668499 ,共计算 3987 次,耗时 0.025 s
不用递归2:第 1000 行第 4 列值是: 165668499 ,共计算 2992 次,耗时 0.004 s
不用递归3:第 1000 行第 4 列值是: 165668499 ,共计算 3989 次,耗时 0.022 s
使用递归1:第 5000 行第 100 列值是: 624014247245299026906445998123558217870956092980555531377768115986897461531075814054704987026416324300946857745465985368470695552826369735898524891324219910107723427537989045846838371991032479953737061920407552 ,共计算 490099 次,耗时 0.522 s
不用递归2:第 5000 行第 100 列值是: 624014247245299026906445998123558217870956092980555531377768115986897461531075814054704987026416324300946857745465985368470695552826369735898524891324219910107723427537989045846838371991032479953737061920407552 ,共计算 485296 次,耗时 0.240 s
不用递归3:第 5000 行第 100 列值是: 624014247245299026906445998123558217870956092980555531377768115986897461531075814054704987026416324300946857745465985368470695552826369735898524891324219910107723427537989045846838371991032479953737061920407552 ,共计算 490197 次,耗时 0.420 s
注:递归的方式之所以要维护一个数组,是因为避免重复执行递归操作;
可以得出结论,第二种方法和第一、三种虽然循环次数并没有少一个数量,但使用内存更少(只使用一个一维数组),所以计算所花费的时间少很多。
function getMillisecond() {
list($s1, $s2) = explode(' ', microtime());
return (float)sprintf('%.03f', (floatval($s1) + floatval($s2)));
}
function yanghui($h,$r){
$rr = $r;
if($r > $h){
die("\$r = $r 不能大于 \$h = $h");
}
if($r > ceil($h/2)){
$rr = $h+1-$r;
}
echo "使用递归1:";
compute($h,$r,'yanghui1');
echo "不用递归2:";
compute($h,$r,'yanghui2');
echo "不用递归3:";
compute($h,$r,'yanghui3');
}
function compute($h,$r,$fun){
$count = 0;
$time = getMillisecond();
if($fun == 'yanghui1'){
$arr = [];
$v = $fun($h,$r,$count,$arr);
}else{
$v = $fun($h,$r,$count);
}
$v = number_format($v,0,'.','');
$time = sprintf('%.03f',getMillisecond() - $time);
echo "第 $h 行第 $r 列值是: $v ,共计算 $count 次,耗时 $time s\r\n";
}
function yanghui1($h,$r,&$count,&$arr){
if(!isset($arr[$h])){
$arr[$h] = [];
}
if(!isset($arr[$h][$r])){
$count ++;
if($r == 1 || $r == $h){
$arr[$h][$r] = 1;
}else{
$arr[$h][$r] = yanghui1($h-1,$r,$count,$arr)+yanghui1($h-1,$r-1,$count,$arr);
}
}
return $arr[$h][$r];
}
function yanghui2($h,$r,&$count){
$a = [];
$a[2] = $a[1] = 1;
$border = ($h+1-$r);
for($i=3;$i<=$h;$i++){
$pre = $a;
if($i <= $border){
for($j = 2; $j <= min([$i,$r]); $j++){
$a[$j] = $pre[$j-1]+$pre[$j];
$count ++ ;
}
}else{
for($j=max([($i-$border),2]);$j <= $r; $j++){
$a[$j] = $pre[$j-1]+$pre[$j];
$count ++;
}
}
}
return $a[$r];
}
function yanghui3($h,$r,&$count){
$border = ($h+1-$r);
$arr = [];
$arr[1][1] = 1;
if($h >= 2){
for($i=2;$i<=$h;$i++){
if($i <= $border){
for($j = 1; $j <= min([$i,$r]); $j++){
$arr[$i][$j] = $arr[$i-1][$j-1]+$arr[$i-1][$j];
$count ++ ;
}
}else{
for($j=max([($i-$border),2]);$j <= $r; $j++){
$arr[$i][$j] = $arr[$i-1][$j-1]+$arr[$i-1][$j];
$count ++;
}
}
}
}
return $arr[$h][$r];
}
$h = $_GET['h']?$_GET['h']:6;
$r = $_GET['r']?$_GET['r']:3;
yanghui($h,$r);
嗨,这是一条评论。
要开始审核、编辑及删除评论,请访问仪表盘的“评论”页面。
评论者头像来自Gravatar。