袋鼠从起点开始跳，问到终点有多少种不同的跳跃方式
袋鼠从起点开始跳，问到终点有多少种不同的跳跃方式题目
有一只袋鼠，它跳跃一次的方式只有两种：①一次跳1米 ②一次跳3米，现在有一段10米长的路，袋鼠从起点开始跳，问到终点有多少种不同的跳跃方式？
方法1：生成二叉树生成
[*]每一步有两种选择：1米或者3米,所以解集是一棵二叉树,每一个节点代表一种选择。
[*]假设当前运动位置是S，则S = sum（根节点 + ... +当前节点）。（我不知道markdown如何打数学公式，google出来的都没成功，凑合着看吧）
[*]当前运动位置 > 10m，说明路走完了。结束当前路径搜索。
遍历二叉树，找到所有sum<?php
const TOTAL_STEP = 10;
const OPTION_STEP1 = 1;
const OPTION_STEP3 = 3;
$table = [];
$count = 0;
// 生成遍历二叉树
function gene1($path, $dist){
global $table;
global $count;
$path1 = 0;
$path2 = 0;
$count += 1;
if($dist < TOTAL_STEP){
$path1 = $path . OPTION_STEP1;
$set1 = gene1($path1, $dist + OPTION_STEP1);
$path2 = $path . OPTION_STEP3;
$set2 = gene1($path2, $dist + OPTION_STEP3);
return array_merge($set1, $set2);
}else{
return [$path];
}
}
$start = microtime(true);
$paths = gene1("", 0);
$end = microtime(true);
echo "======================================\n";
printf("运行时间： %.8fs\n", ($end - $start));
echo "gene函数执行次数： " . $count . "\n";
echo "numOfPath: " . count($paths) . "\n";
foreach($paths as $path){
echo $path . " ";
}运行结果C:\Users\shyandsy\Desktop
λ php alg.php
======================================
运行时间： 0.00028992s
gene函数执行次数： 119
numOfPath: 60
1111111111 1111111113 111111113 11111113 11111131 11111133 11111311 11111313 1111133 11113111 11113113 1111313 111133 11131111 11131113 1113113 111313 111331 111333 11311111 11311113 1131113 113113 113131 113133 113311 113313 11333 13111111 13111113 1311113 131113 131131 131133 131311 131313 13133 133111 133113 13313 1333 31111111 31111113 3111113 311113 311131 311133 311311 311313
31133 313111 313113 31313 3133 331111 331113 33113 3313 3331 3333
时间复杂度O(2^N),很慢
方法2：动态规划优化
添加一个hashtable T，用来记录计算过的结果，避免重复计算。对于任意节点K，有当前运动距离S。如果T存在，则不需要再次遍历节点K的子节点，计算所有可能性，直接取出T使用即可；否则，遍历T所有子节点，得到所有可能性，并保存到T。<?php
const TOTAL_STEP = 10;
const OPTION_STEP1 = 1;
const OPTION_STEP3 = 3;
$table = [];
$count = 0;
function gene2($path, $dist){
global $table;
global $count;
$path1 = 0;
$path2 = 0;
$count += 1;
if($dist < TOTAL_STEP){
if(array_key_exists($dist, $table)){
$final = $table[$dist];
}else{
$path1 = $path . OPTION_STEP1;
$set1 = gene2($path1, $dist + OPTION_STEP1);
$path2 = $path . OPTION_STEP3;
$set2 = gene2($path2, $dist + OPTION_STEP3);
$final = array_merge($set1, $set2);
$table[$dist] = $final;
}
return $final;
}else{
return [$path];
}
}
$start = microtime(true);
$paths = gene2("", 0);
$end = microtime(true);
echo "======================================\n";
printf("运行时间： %.8fs\n", ($end - $start));
echo "gene函数执行次数： " . $count . "\n";
echo "numOfPath: " . count($paths) . "\n";
foreach($paths as $path){
echo $path . " ";
}
执行结果C:\Users\shyandsy\Desktop
λ Cphp alg.php
======================================
运行时间： 0.00009298s
gene函数执行次数： 21
numOfPath: 60
1111111111 1111111113 111111113 11111113 1111111111 1111111113 1111111111 1111111113 111111113 1111111111 1111111113 111111113 11111113 1111111111 1111111113 111111113 11111113 1111111111 1111111113 1111111111 1111111113 111111113 11111113 1111111111 1111111113 1111111111 1111111113 111111113 1111111111
1111111113 111111113 11111113 1111111111 1111111113 1111111111 1111111113 111111113 1111111111 1111111113 111111113 11111113 1111111111 1111111113 111111113 11111113 1111111111 1111111113 1111111111
1111111113 111111113 1111111111 1111111113 111111113 11111113 1111111111 1111111113 111111113 11111113
1111111111 1111111113
算法复杂度O(n)
分析
不使用动态规划gene函数调用119次，耗时0.00028992s，很明显这是一个O(2^n)的算法；
使用动态规划后，gene函数调用21次，耗时0.00009298s,算法复杂度O(n)。
重构代码方便测试
[*]只返回不同跳跃方式的数量，以节省内存，方便更长距离的测试
[*]分别测试TOTAL_STEP=10, 30, 50，看看会有多大差距。
<?php
const TOTAL_STEP = 10;
const OPTION_STEP1 = 1;
const OPTION_STEP3 = 3;
$table = [];
$count = 0;
function gene1($path, $dist){
global $table;
global $count;
$path1 = 0;
$path2 = 0;
$count += 1;
if($dist < TOTAL_STEP){
$path1 = $path . OPTION_STEP1;
$num1 = gene1($path1, $dist + OPTION_STEP1);
$path2 = $path . OPTION_STEP3;
$num2 = gene1($path2, $dist + OPTION_STEP3);
return $num1 + $num2;
}else{
return 1;
}
}
function gene2($path, $dist){
global $table;
global $count;
$path1 = 0;
$path2 = 0;
$count += 1;
if($dist < TOTAL_STEP){
if(array_key_exists($dist, $table)){
$final = $table[$dist];
}else{
$path1 = $path . OPTION_STEP1;
$num1 = gene2($path1, $dist + OPTION_STEP1);
$path2 = $path . OPTION_STEP3;
$num2 = gene2($path2, $dist + OPTION_STEP3);
$final = $num1 + $num2;
$table[$dist] = $final;
}
return $final;
}else{
return 1;
}
}
function test($func){
global $count;
global $table;
$count = 0;
$table = [];
$start = microtime(true);
$quantity = $func("", 0);
$end = microtime(true);
echo "===============$func ()=======================\n";
printf("运行时间： %.8fs\n", ($end - $start));
echo "gene函数执行次数： " . $count . "\n";
echo "numOfPath: " . $quantity . "\n";
}
ini_set('xdebug.max_nesting_level', 20000);
ini_set('memory_limit','2000M');
printf("TEST for total distance = %d\n", TOTAL_STEP);
test("gene1");
test("gene2");
测试const TOTAL_STEP = 10;结果C:\Users\shyandsy\Desktop
λ php alg.php
TEST for total distance = 10
===============gene1 ()=======================
运行时间： 0.00023198s
gene函数执行次数： 119
numOfPath: 60
===============gene2 ()=======================
运行时间： 0.00006604s
gene函数执行次数： 21
numOfPath: 60
测试const TOTAL_STEP = 30;结果C:\Users\shyandsy\Desktop
λ php alg.php
TEST for total distance = 30
===============gene1 ()=======================
运行时间： 0.46277499s
gene函数执行次数： 250981
numOfPath: 125491
===============gene2 ()=======================
运行时间： 0.00018311s
gene函数执行次数： 61
numOfPath: 125491
测试const TOTAL_STEP = 50;结果(gene1()已然慢的无法接受了)C:\Users\shyandsy\Desktop
λ php alg.php
TEST for total distance = 50
===============gene1 ()=======================
运行时间： 1028.82678294s
gene函数执行次数： 524543135
numOfPath: 262271568
===============gene2 ()=======================
运行时间： 0.00030088s
gene函数执行次数： 101
numOfPath: 262271568
以上文章来自网友 楚天乐的小站 （需自备梯子）版权归作者所有，本站仅转发整理。
页:
[1]