袋鼠从起点开始跳,问到终点有多少种不同的跳跃方式
题目
有一只袋鼠,它跳跃一次的方式只有两种:①一次跳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 +...