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

楚天乐 392 0 条

题目

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

方法1:生成二叉树生成

  1. 每一步有两种选择:1米或者3米,所以解集是一棵二叉树,每一个节点代表一种选择。
  2. 假设当前运动位置是S,则S = sum(根节点 + ... +当前节点)。(我不知道markdown如何打数学公式,google出来的都没成功,凑合着看吧)
  3. 当前运动位置 > 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[S]存在,则不需要再次遍历节点K的子节点,计算所有可能性,直接取出T[S]使用即可;否则,遍历T[S]所有子节点,得到所有可能性,并保存到T[S]。

<?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


发表我的评论
昵称 (必填)
邮箱 (必填)
网址