首页 > 其他 > 详细

面试题14:剪绳子

时间:2018-12-22 23:05:43      阅读:259      评论:0      收藏:0      [点我收藏+]
<?php
header("content-type:text/html;charset=utf-8");
/*
 * 剪绳子 把一根绳子剪成多段,并且使得每段的长度乘积最大。 P96
 */

//动态规划
function integerBreak1($length){
    if($length < 2){
        return 0;
    }
    if($length == 2){
        return 1;
    }

    if($length == 3){
        return 2;
    }
    $products = array();
    $products[0] = 0;
    $products[1] = 1;
    $products[2] = 2;
    $products[3] = 3;
    for($i=4;$i<=$length;$i++){
        $max = 0;
        for($j = 1;$j<$i;$j++){
            $product = $products[$j] * $products[$i-$j];
            if($max < $product){
                $max = $product;
            }
            $products[$i] = $max;
        }
    }
    return $products[$length];
}

//贪心算法
function integerBreak2($length){
    if($length < 2){
        return 0;
    }
    if($length == 2){
        return 1;
    }

    if($length == 3){
        return 2;
    }
    $timesOf3 = floor($length / 3);
    if($length - $timesOf3 * 3 == 1){
        $timesOf3--;
        $timesOf2 = ($length - $timesOf3 * 3)/2;
    }
    return (pow(3,$timesOf3) * pow(2,$timesOf2));

}

echo integerBreak1(10);
echo integerBreak2(10);

 

面试题14:剪绳子

原文:https://www.cnblogs.com/xlzfdddd/p/10162784.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!