首页 » php » PHP经典算法百钱买小鸡-论算法的重要性

PHP经典算法百钱买小鸡-论算法的重要性

 

遇到一道有趣的题,并计算2种方法的效率,发现如果穷举所有组合竟高达1000000次排列~所以简化到了600次。所以,你的一个条件,或者一个运算,可能会提高几千倍的效率!

<?php 
header("Content-Type:text/html;charset=utf-8");
//百钱买小鸡
/*
公鸡5文钱1只,母鸡三文钱一只,小鸡一文钱三只。
现在用100文钱共买了100只鸡,
问这100只鸡中,公鸡,母鸡,小鸡各是多少只?
*/

$start = microtime(true);
//写法一 穷举所有排列:计算1000000次。
for($g = 1; $g <= 100; $g++){
    for($m = 1; $m <= 100; $m++){
        for($x = 1; $x <= 100; $x++){
            if($g+$m+$x == 100 && $g*5+$m*3+$x/3==100){
                echo "公,母,雏,分别为:".$g."&nbsp;".$m."&nbsp;".$x."<br />";
            }
            //计算排列组合次数
            if($g == 100 && $m == 100 && $x == 100){
                echo "排列次数为:".$g*$m*$x;   
            }
        }
    }
}
echo "<br />";
$end = microtime(true);
echo "函数执行时间为:".($end - $start);//计算函数运行时间。
echo "<br />";

//写法二:简化组合.
$start = microtime(true);
for($g = 1; $g < 20; $g++){
    for($m = 1; $m <= 33; $m++){
        $x = 100 - $g - $m;
        if($g+$m+$x == 100 && $g*5+$m*3+$x/3==100){
            echo "公,母,雏,分别为:".$g."&nbsp;".$m."&nbsp;".$x."<br />";
        }
        //计算排列组合次数
        if($g == 19 && $m == 33){
            echo "排列次数为:".$g*$m;  
        }
    }
}
echo "<br />";
$end = microtime(true);
echo "函数执行时间为:".($end - $start);//计算函数运行时间。
echo "<br />";
?>
输出结果1: 
公,母,雏,分别为:4 18 78 
公,母,雏,分别为:8 11 81 
公,母,雏,分别为:12 4 84 
排列次数为:1000000 
函数执行时间为:0.10584402084351

再来看一下第二套算法~整整差了一千倍~虽说是毫秒。

输出结果2: 
公,母,雏,分别为:4 18 78 
公,母,雏,分别为:8 11 81 
公,母,雏,分别为:12 4 84 
排列次数为:627 
函数执行时间为:0.00016307830810547

 

原文链接:PHP经典算法百钱买小鸡-论算法的重要性,转载请注明来源!

0