当前位置：Gxlcms > PHP教程 > A个碗每碗可装B个球共有C个球问有多少种装法(球完全相同)

A个碗每碗可装B个球共有C个球问有多少种装法(球完全相同)

时间：2021-07-01 10:21:17 帮助过：2人阅读

碗相同，球相同，转换一下思路。
A列B行的表格，每个钢珠可放入一个格子，共C个钢珠。
移动钢珠，使出现各种可能。为了避免重复和遗漏，我们依据一下规律移动钢珠。
从左到右放置钢珠，第一列放置满后，再放置第二列；依次类推。
移动钢珠的时候，总是保证左边的任何一列钢珠数不少于比右边的任何一列。
每移动一个钢珠，出现一种可能的情况，计数器加1.

$boxNum = 20;
$size = 10;
$total = 33;
//初始化
$data = array();
for($i=1;$i<=$boxNum;$i++)
{
if($total>=$size)
{
$data[$i] = $size;
$total -= $size;
}
else if($total>0)
{
$data[$i] = $total;
$total = 0;
}
else
{
$data[$i] = 0;
}
}
for($i=1;$i<=$boxNum;$i++) echo $data[$i]."\t";
echo "\r\n";
$count = 1;
while(true)
{
for($i=$boxNum;$i>=1;$i--)
{
//发现最后一个值
if($data[$i]>0)
{
$last = $i;
break;
}
}
list($prev,$next) = getPrevNext($data,$last);
if($prev===false)
{
if($last<$boxNum)
{
if($data[1]>1)
{
list($prev,$next) = getPrevNext($data,$last+1);//启用新列
}
else
{
break;//结束
}
}
else
{
break;//结束
}
}
$num = floor(($data[$prev] - $data[$next])/2);
$data[$prev] -= $num;
$data[$next] += $num;
$count += $num;
for($i=1;$i<=$boxNum;$i++) echo $data[$i]."\t";
echo "num:".$num."\r\n";
}
echo '共有'.$count.'种可能'."\r\n";
function getPrevNext($data,$last)
{
$prev = $next = false;
for($i=$last-1;$i>=1;$i--)
{
if($data[$i]-$data[$i+1]>1)//发现一阶滚落
{
$prev = $i;
$next = $i+1;
break;
}
else if($data[$i]-$data[$last]>1)//发现多阶滚落
{
$prev = $i;
for($k=$i+1;$k<=$last;$k++)
{
if($data[$i]-$data[$k]>1)//发现最短多阶滚落
{
$next = $k;
break;
}
}
break;
}
}
return array($prev,$next);
}

A个碗每碗可装B个球共有C个球问有多少种装法(球完全相同)

人气教程排行