A个碗 每碗可装B个球 共有C个球 问有多少种装法(球完全相同)
-
原创
-
2016-07-25 08:48:22
920浏览
碗相同，球相同，转换一下思路。
A列B行的表格，每个钢珠可放入一个格子，共C个钢珠。
移动钢珠，使出现各种可能。为了避免重复和遗漏，我们依据一下规律移动钢珠。
从左到右放置钢珠，第一列放置满后，再放置第二列；依次类推。
移动钢珠的时候，总是保证左边的任何一列钢珠数不少于比右边的任何一列。
每移动一个钢珠，出现一种可能的情况，计数器加1.
- $boxNum = 20;
- $size = 10;
- $total = 33;
- //初始化
- $data = array();
- for($i=1;$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;$iecho "\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 {
- 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 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 {
- if($data[$i]-$data[$k]>1)//发现最短多阶滚落
- {
- $next = $k;
- break;
- }
- }
- break;
- }
- }
-
- return array($prev,$next);
- }
|
声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn核实处理。
