设为首页收藏本站
切换到宽版

PHPIN.NET

 找回密码
 立即注册
PHPIN.NET»论坛 › PHP综合 › PHP综合教程 › 袋鼠从起点开始跳，问到终点有多少种不同的跳跃方式 ...
返回列表 发新帖
查看: 5966|回复: 0

[高级进阶] 袋鼠从起点开始跳，问到终点有多少种不同的跳跃方式

[复制链接]
admin

469

主题

31

回帖

5569

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5569
发表于 2019-2-13 12:24:27 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？立即注册

x
袋鼠从起点开始跳，问到终点有多少种不同的跳跃方式

题目
有一只袋鼠，它跳跃一次的方式只有两种：①一次跳1米 ②一次跳3米，现在有一段10米长的路，袋鼠从起点开始跳，问到终点有多少种不同的跳跃方式？

方法1：生成二叉树生成
  • 每一步有两种选择：1米或者3米,所以解集是一棵二叉树,每一个节点代表一种选择。
  • 假设当前运动位置是S，则S = sum（根节点 + ... +当前节点）。（我不知道markdown如何打数学公式，google出来的都没成功，凑合着看吧）
  • 当前运动位置 > 10m，说明路走完了。结束当前路径搜索。

遍历二叉树，找到所有sum
  1. <?php
  2. const TOTAL_STEP = 10;
  3. const OPTION_STEP1 = 1;
  4. const OPTION_STEP3 = 3;

  6. $table = [];
  7. $count = 0;

  9. // 生成遍历二叉树
  10. function gene1($path, $dist){
  11.     global $table;
  12.     global $count;
  13.     $path1 = 0;
  14.     $path2 = 0;

  16.     $count += 1;
  17.     if($dist < TOTAL_STEP){
  18.         $path1 = $path . OPTION_STEP1;
  19.         $set1 = gene1($path1, $dist + OPTION_STEP1);        

  21.         $path2 = $path . OPTION_STEP3;
  22.         $set2 = gene1($path2, $dist + OPTION_STEP3);

  24.         return array_merge($set1, $set2);
  25.     }else{
  26.         return [$path];
  27.     }
  28. }

  30. $start = microtime(true);
  31. $paths = gene1("", 0);
  32. $end = microtime(true);
  33. echo "======================================\n";
  34. printf("运行时间： %.8fs\n", ($end - $start));
  35. echo "gene函数执行次数： " . $count . "\n";
  36. echo "numOfPath: " . count($paths) . "\n";
  37. foreach($paths as $path){
  38.     echo $path . "   ";
  39. }
复制代码
运行结果
  1. C:\Users\shyandsy\Desktop
  2. λ php alg.php
  3. ======================================
  4. 运行时间： 0.00028992s
  5. gene函数执行次数： 119
  6. numOfPath: 60
  7. 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
  8.    31133   313111   313113   31313   3133   331111   331113   33113   3313   3331   3333
复制代码

时间复杂度O(2^N),很慢

方法2：动态规划优化
添加一个hashtable T，用来记录计算过的结果，避免重复计算。对于任意节点K，有当前运动距离S。如果T[S]存在，则不需要再次遍历节点K的子节点，计算所有可能性，直接取出T[S]使用即可；否则，遍历T[S]所有子节点，得到所有可能性，并保存到T[S]。
  1. <?php
  2. const TOTAL_STEP = 10;
  3. const OPTION_STEP1 = 1;
  4. const OPTION_STEP3 = 3;

  6. $table = [];
  7. $count = 0;

  9. function gene2($path, $dist){
  10.     global $table;
  11.     global $count;
  12.     $path1 = 0;
  13.     $path2 = 0;

  15.     $count += 1;

  17.     if($dist < TOTAL_STEP){
  18.         if(array_key_exists($dist, $table)){
  19.             $final = $table[$dist];
  20.         }else{
  21.             $path1 = $path . OPTION_STEP1;
  22.             $set1 = gene2($path1, $dist + OPTION_STEP1);

  24.             $path2 = $path . OPTION_STEP3;
  25.             $set2 = gene2($path2, $dist + OPTION_STEP3);

  27.             $final = array_merge($set1, $set2);

  29.             $table[$dist] = $final;
  30.         }

  32.         return $final;

  34.     }else{
  35.         return [$path];
  36.     }

  38. }

  40. $start = microtime(true);
  41. $paths = gene2("", 0);
  42. $end = microtime(true);
  43. echo "======================================\n";
  44. printf("运行时间： %.8fs\n", ($end - $start));
  45. echo "gene函数执行次数： " . $count . "\n";
  46. echo "numOfPath: " . count($paths) . "\n";
  47. foreach($paths as $path){
  48.     echo $path . "   ";
  49. }
复制代码

执行结果
  1. C:\Users\shyandsy\Desktop
  2. λ Cphp alg.php
  3. ======================================
  4. 运行时间： 0.00009298s
  5. gene函数执行次数： 21
  6. numOfPath: 60
  7. 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
  8.    1111111113   111111113   11111113   1111111111   1111111113   1111111111   1111111113   111111113   1111111111   1111111113   111111113   11111113   1111111111   1111111113   111111113   11111113   1111111111   1111111113   1111111111
  9. 1111111113   111111113   1111111111   1111111113   111111113   11111113   1111111111   1111111113   111111113   11111113
  10.    1111111111   1111111113
复制代码

算法复杂度O(n)

分析
不使用动态规划gene函数调用119次，耗时0.00028992s，很明显这是一个O(2^n)的算法；
使用动态规划后，gene函数调用21次，耗时0.00009298s,算法复杂度O(n)。

重构代码方便测试
  • 只返回不同跳跃方式的数量，以节省内存，方便更长距离的测试
  • 分别测试TOTAL_STEP=10, 30, 50，看看会有多大差距。

  1. <?php
  2. const TOTAL_STEP = 10;
  3. const OPTION_STEP1 = 1;
  4. const OPTION_STEP3 = 3;

  6. $table = [];
  7. $count = 0;

  9. function gene1($path, $dist){
  10.     global $table;
  11.     global $count;
  12.     $path1 = 0;
  13.     $path2 = 0;

  15.     $count += 1;
  16.     if($dist < TOTAL_STEP){
  17.         $path1 = $path . OPTION_STEP1;
  18.         $num1 = gene1($path1, $dist + OPTION_STEP1);        

  20.         $path2 = $path . OPTION_STEP3;
  21.         $num2 = gene1($path2, $dist + OPTION_STEP3);

  23.         return $num1 + $num2;
  24.     }else{
  25.         return 1;
  26.     }
  27. }

  29. function gene2($path, $dist){
  30.     global $table;
  31.     global $count;
  32.     $path1 = 0;
  33.     $path2 = 0;

  35.     $count += 1;

  37.     if($dist < TOTAL_STEP){
  38.         if(array_key_exists($dist, $table)){
  39.             $final = $table[$dist];
  40.         }else{
  41.             $path1 = $path . OPTION_STEP1;
  42.             $num1 = gene2($path1, $dist + OPTION_STEP1);

  44.             $path2 = $path . OPTION_STEP3;
  45.             $num2 = gene2($path2, $dist + OPTION_STEP3);

  47.             $final = $num1 + $num2;

  49.             $table[$dist] = $final;
  50.         }

  52.         return $final;

  54.     }else{
  55.         return 1;
  56.     }

  58. }

  60. function test($func){   
  61.     global $count;
  62.     global $table;

  64.     $count = 0;
  65.     $table = [];

  67.     $start = microtime(true);
  68.     $quantity = $func("", 0);
  69.     $end = microtime(true);
  70.     echo "===============$func ()=======================\n";
  71.     printf("运行时间： %.8fs\n", ($end - $start));
  72.     echo "gene函数执行次数： " . $count . "\n";
  73.     echo "numOfPath: " . $quantity . "\n";
  74. }

  76. ini_set('xdebug.max_nesting_level', 20000);
  77. ini_set('memory_limit','2000M');

  79. printf("TEST for total distance = %d\n", TOTAL_STEP);

  81. test("gene1");
  82. test("gene2");
复制代码

测试const TOTAL_STEP = 10;结果
  1. C:\Users\shyandsy\Desktop
  2. λ php alg.php
  3. TEST for total distance = 10
  4. ===============gene1 ()=======================
  5. 运行时间： 0.00023198s
  6. gene函数执行次数： 119
  7. numOfPath: 60
  8. ===============gene2 ()=======================
  9. 运行时间： 0.00006604s
  10. gene函数执行次数： 21
  11. numOfPath: 60
复制代码

测试const TOTAL_STEP = 30;结果
  1. C:\Users\shyandsy\Desktop
  2. λ php alg.php
  3. TEST for total distance = 30
  4. ===============gene1 ()=======================
  5. 运行时间： 0.46277499s
  6. gene函数执行次数： 250981
  7. numOfPath: 125491
  8. ===============gene2 ()=======================
  9. 运行时间： 0.00018311s
  10. gene函数执行次数： 61
  11. numOfPath: 125491
复制代码

测试const TOTAL_STEP = 50;结果(gene1()已然慢的无法接受了)
  1. C:\Users\shyandsy\Desktop
  2. λ php alg.php
  3. TEST for total distance = 50
  4. ===============gene1 ()=======================
  5. 运行时间： 1028.82678294s
  6. gene函数执行次数： 524543135
  7. numOfPath: 262271568
  8. ===============gene2 ()=======================
  9. 运行时间： 0.00030088s
  10. gene函数执行次数： 101
  11. numOfPath: 262271568
复制代码


以上文章来自网友 楚天乐的小站 （需自备梯子）版权归作者所有，本站仅转发整理。
php, 算法, PHP算法

相关帖子
回复

举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|PHPIN.NET ( 冀ICP备12000898号-14 )|网站地图

GMT+8, 2024-10-31 06:36

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表