编程题分享：有⼀堆糖果，其数量为n,现将糖果分成不同数量的堆数

泥豆芽儿 MT

发布于 2023-10-16 19:18:17

2200

发布于 2023-10-16 19:18:17

背景近期面试遇到一家公司的编程题，觉得挺有参考价值此处使用 PHP语言，进行编码测试，编码之前要进行思路分析，避免无头苍蝇，走一步看一步最后，希望后期面试顺利！欢迎指摘 .

题目：

	编程题：
	有⼀堆糖果，其数量为n，
	现将糖果分成不同数量的堆数（每堆数量均为整数，最少为1），
	请算出糖果堆对应数量的最⼤乘积是多少，并给出对应的分配⽅案；
	举例：糖果数量为8，可以得到的乘积最⼤为18，对应的分配⽅案为【2，3，3】；

思路分析：

初始测试数据比较小，可以在草稿纸上穷举分配方案，寻找规律，发现：

当数量小于5时，最大的乘积就是本身，无需分配
其次注意到分配后的数目如果是1则毫无意义，
同时穷举发现，越靠近数字3，乘积越大，得到的分配方案最符合要求
所以算法重点处理数量大于5的情况首先获取除3的整数部分 count, 和取模数字 mod 根据变量 count ,判断乘积，for 循环处理,并得到每个分配数字分析 mod 变量的影响，使得分配数尽可能靠近数字 3 最后，简单测试数量 n，验证分配方案是否符合实际要求 .

编码如下：

**
 * 有⼀堆糖果，其数量为n，现将糖果分成不同数量的堆数
 * @param int $z_number 糖果数量
 * @return string 检测结果
 */
public function zingFunc($z_number = 0){
    //检验数据规范性
    $res_msg = '分配数字为：'.$z_number;
    //最大乘积
    $max_result = 1;
    //方案分配
    $option_msg = '';
    if (is_int($z_number)&& $z_number > 0){
        if ($z_number < 5){
            $max_result = $z_number;
            $option_msg = $z_number;
        }else{
            //整数大于5，详细分析
            //取商的整数
            $count = intval($z_number/3);
            //除3取模
            $mod = $z_number%3;
            $arr_option = [];

            if ($mod == 0){
                //此时正好是统一分配
                for ($i=0;$i<$count;$i++){
                    $max_result*=3;
                    $arr_option[] = 3;
                }
            }elseif ($mod == 1){
                //对其中的一个分配数加1
                for ($i=0;$i<$count-1;$i++){
                    $max_result*=3;
                    $arr_option[] = 3;
                }
                $max_result *=4;
                $arr_option[] = 4;
            }else{
                //余数为2的时候，可以对前面取两堆，分别加1
                for ($i=0;$i<$count-2;$i++){
                    $max_result*=3;
                    $arr_option[] = 3;
                }
                $max_result *=4;
                $max_result *=4;
                $arr_option[] = 4;
                $arr_option[] = 4;
            }
            $option_msg = implode(',',$arr_option);
        }
        $res_msg .= ',最大乘积为：'.$max_result.',方案分配为：【'.$option_msg.'】';
    }else{
        $res_msg .= ',数据输入不是正整数';
    }
    //echo('<br>'.$res_msg);
    return $res_msg;
}