1000个苹果分成10堆

矫情吗；* 2022-07-11 01:54 128阅读 0赞

问题：1000个苹果分成10堆，可以组合任意1-1000个数的苹果  
此问题是否有解？如何求解？  
1.首先我们必须写一个验证的程序

/** * 验证数组 * @author syh * @param array $arr * @return bool */
        function check($arr) { 
            rsort($arr);//逆序
            $listNum=range(1,array_sum($arr));
            $fun=function ($num) use ($arr){ 
    
                foreach ($arr as $key => $val)
                {
                    if($num===$val) return true;
                    //减去数组中比自己小的最大值 
                    if($num>$val) $num=$num-$val;
                }
    
                return false;  
            };
            return !in_array(false,array_map($fun,$listNum));
    
        }
    $arr=[1,2,4,8,16,32,64,128,256,489];//此数组为正解的一种，可以通过验证
    $data=check($arr);
    var_dump($data);//true

2.遍历所有可能的组合或随机取值

2.0非递归遍历（最原始的实现）

/** * $m个苹果分为4堆 * @author syh * @param int $m苹果总数 * @return array 验证通过后的数组 */
        function test($m) { 
            $listAll=[];
            $list=[];
            $len=4;//苹果堆数
            $max=function($list) use ($m,$len){ 
               return  $m-array_sum($list)-($len-count($list))+1;
    
            };
    
            for ($k1=1,$max1=$max($list);$k1 <=$max1; $k1++)
            { 
                $list[1]=$k1;
                for ($k2=1,$max2=$max($list);$k2 <=$max2 ;$k2++)
                { 
                    $list[2]=$k2;
                    for ($k3=1,$max3=$max($list);$k3 <=$max3; $k3++)
                    {
                        $list[3]=$k3;
                        $list[4]=$m-array_sum($list);
                        if(check($list)) 
                        {
                            $listAll[]=$list;
                        }
                        unset($list[3]);
                        unset($list[4]);
                    }
                    unset($list[2]);
                } 
                unset($list[1]); 
    
            }
            return $listAll;
    
        }

2.1第一种遍历所有可能，

/** * 递归实现1 * @author int $m 苹果的个数 * @param int $n 苹果堆数 * @return array */
    function crateArr($m,$n) { 
        static $list=[];//保存当前的组合
        static $listAll=[];//保存所有可能的组合
        static $count=0,$len;
        if(($count++)===0)  $len=$n;//保存数组长度
        $max=$m-array_sum($list)-($len-count($list))+1;
    
        for ($i=1;$i<=$max;$i++)
        { 
    
            $list[$n]=$i;//第$n堆苹果 
            if ($n===2)
            {
                //此处为最后一次循环
                $list[$n-1]=$m-array_sum($list);//最后一堆苹果的个数
                if (check($list))
                {
                    $listAll[]=$list;  //验证通过后合并 
                }
                unset($list[$n-1]);
                unset($list[$n]);
            }
            elseif($n>2)
            {
                crateArr($m,$n-1);//递归进行 相当于for循环嵌套
                unset($list[$n]);
            }
    
        }
    
        return $listAll;//返回所有符合要求的组合
     }

2.2第一种遍历的次数太多，进一步优化

/** *递归实现2 * @author syh * @param string $m 苹果总数 * @param string $n 苹果堆数 * @param string $p 第一堆苹果起始值 * @return array */
    function createArr($m,$n,$p=1) { 
        static $list=[],$listAll=[];
        static $count=0,$len;
        if(($count++)===0)  $len=$n;//保存数组长度
        $d=$len-($len-$n)-1;//第$n项到$len-1项的元素个数
        // 假设第$n堆苹果到$len-1堆苹果数位公差为1的等差数列
        //最后一堆苹果个数=苹果总和-当前堆前面的总和-当前堆到第$len-1堆等差数列的和
        //第$len-1堆苹果的个数为a1+(n-1)*d 等差数列第n项公式
        //当前堆到$len-1的总和为a1*n+n*(n-1)*d/2等差数列前n项和
        // 数组为从小到大排序，当最后一项与倒数第二项相等时为每堆苹果的最大值，即临界点
        $max=($m-array_sum($list)-$d*($d-1)/2-$len+1)/($d+1)+1;
    
        for ($i=$p;$i<=ceil($max);$i++)
        {  
            $list[$n]=$i;     
            if ($n===2)
            {
                $list[$n-1]=$m-array_sum($list);
                if(check($list))
                {
                    // 验证通过后存入数组
                    $listAll[]=$list;          
                } 
                unset($list[$n-1]);
                unset($list[$n]);
            }
            elseif($n>2)
            {    
                $function=__FUNCTION__; 
                //堆数递减，后面堆苹果最小个数=前面堆苹果个数+1
                $function($m,$n-1,$i+1);
                unset($list[$n]);
            }
    
        }   
        return $listAll;
     }

2.3随机取值

总结：经过自己不懈的努力，程序终于实现了；但1000个苹果分成10堆计算量太大，自己的电脑最多能计算300个苹果分成10堆。  
1,2,4,8,16,32,64,128,256,489  
通过观察得出，符合此规律的等比数列，能组合的最大数为2的（数列长度）次方-1。通过程序验证63（2^6-1）个苹果分成6堆苹果只有一个解，小于63就会存在多解；同理，1000个苹果分成10堆，能组合的最大数为2^10-1（1023）;所以此问题存在多解，上面的数列只是其中一种解。  
2.4 进一步研究，求全部解

/**
    * 遍历后2位
    * 此解并不是最终解
    * @author   syh
    * @return   array
    */
    function checkAll()
    { 
        $arr=[1,2,4,8,16,32,64,128,256,489];
        $list=[];
        for ($i=256; $i >128 ; $i--)
        {  
            array_pop($arr);
            array_pop($arr);
            array_push($arr, $i,745-$i);
            if (check($arr))
            { 
                $list[]=implode('--',$arr);
            }
        }
        return $list;
    }
    $data=checkAll($arr);
     print_r($data);
     Array
    (
        [0] => 1--2--4--8--16--32--64--128--256--489
        [1] => 1--2--4--8--16--32--64--128--255--490
        [2] => 1--2--4--8--16--32--64--128--254--491
        [3] => 1--2--4--8--16--32--64--128--253--492
        [4] => 1--2--4--8--16--32--64--128--252--493
        [5] => 1--2--4--8--16--32--64--128--251--494
        [6] => 1--2--4--8--16--32--64--128--250--495
        [7] => 1--2--4--8--16--32--64--128--249--496
        [8] => 1--2--4--8--16--32--64--128--248--497
        [9] => 1--2--4--8--16--32--64--128--247--498
        [10] => 1--2--4--8--16--32--64--128--246--499
        [11] => 1--2--4--8--16--32--64--128--245--500
    )