写点什么

分苹果

用户头像
书旅
关注
发布于: 2020 年 08 月 14 日
分苹果

>题目:有1000个苹果,分别装在10个箱子里。任意给出1到1000之间的一个整数,都可以用某几个箱子中的苹果数量相加获得此数。请列出这10个箱子中分别有多少个苹果

方法一:

<?php
/**
* @params Integer $total
*
* 这个题特别容易陷进去,觉得这简直就是一个多元函数的数学题,但是仔细算几个数出来,就会发现规律
* 解题思路:
* 最小单位是1,所以要有1,有1就要有2,我们假设随机数是2,没有2的话,无法得到。所以我们现在前两个箱子分别装1、2。
* 假设现在抽到3,那没问题(1+2=3)。如果我们抽到4,现有的不能满足,所以必须有4(那么此时第三个箱子为4)。如果我们抽到5(1+4),没问题。
* 假设抽到6,没问题(2+4)。抽到7,没问题(1+2+4)。假设抽到8,那就无法满足了,所以必须有8(那么此时第四个箱子为8)
* 现在我们看一下前四个箱子的苹果数:1、2、4、8。相信我们已经看出规律了。
* 找出规律:1+2+4+8+16+32+64+128+256+512 =1023, 只有1000,所以最后一个箱子放{512-(1023-1000)}=489个
*/
function shareApples1($total)
{
$sum = $num = 1;
$result[] = $num;
while ($sum < $total) {
$num *= 2;
$result[] = $num;
$sum += $num;
}
array_pop($result);
$result[] = $num - ($sum - $total);
return $result;
}
?>

方法二:

<?php
/**
*@params Integer $total
*
* 解题思路:
* 通过方法一的解题过程,我们也会看出来,我们可以很轻易的推出来,前两个箱子肯定放1和2
* 既然是10个箱子里边任意几个箱子的苹果数相加都能得到1~1000之间的任意数。那么,我们发现
* 有了1和2,3可以通过1+2得到、4无法通过1和2得到,所以必须有4、那么5可以通过1+4得到、6可以通过2+4得到...
* 由此,我们也可以看出来下一个箱子里的苹果数,就是前面所有箱子里的苹果数之和再加一。
* 找规律:4=(2+1)+1、8=(1+2+4)+1、16=(8+4+2+1)+1
*/
function shareApples2($total)
{
$num1 = 1;
$num2 = 2;
$sum = $num1+$num2;
$result[0] = $num1;
$result[1] = $num2;
while($sum<$total){
$num = $sum+1;
$result[] = $num;
$sum += $num;
}
array_pop($result);
$result[] = $num-($sum-$total);
return $result;
}
?>



发布于: 2020 年 08 月 14 日阅读数: 53
用户头像

书旅

关注

公众号:IT猿圈 2019.04.11 加入

还未添加个人简介

评论

发布
暂无评论
分苹果