>  기사  >  백엔드 개발  >  그릇 A. 각 그릇에는 B개의 공이 들어갈 수 있습니다. 총 C개의 공이 있습니다. (공은 완전히 동일합니다.)

그릇 A. 각 그릇에는 B개의 공이 들어갈 수 있습니다. 총 C개의 공이 있습니다. (공은 완전히 동일합니다.)

WBOY
WBOY원래의
2016-07-25 08:48:221267검색
碗相同,球相同,转换一下思路。
A列B行的表格,每个钢珠可放入一个格子,共C个钢珠。
移动钢珠,使出现各种可能。为了避免重复和遗漏,我们依据一下规律移动钢珠。
从左到右放置钢珠,第一列放置满后,再放置第二列;依次类推。
移动钢珠的时候,总是保证左边的任何一列钢珠数不少于比右边的任何一列。
每移动一个钢珠,出现一种可能的情况,计数器加1.
  1. $boxNum = 20;
  2. $size = 10;
  3. $total = 33;
  4. //初始化
  5. $data = array();
  6. for($i=1;$i<=$boxNum;$i )
  7. {
  8. if($total>=$size)
  9. {
  10. $data[$i] = $size;
  11. $total -= $size;
  12. }
  13. else if($total>0)
  14. {
  15. $data[$i] = $total;
  16. $total = 0;
  17. }
  18. else
  19. {
  20. $data[$i] = 0;
  21. }
  22. }
  23. for($i=1;$i<=$boxNum;$i ) echo $data[$i]."t";
  24. echo "rn";
  25. $count = 1;
  26. while(true)
  27. {
  28. for($i=$boxNum;$i>=1;$i--)
  29. {
  30. //发现最后一个值
  31. if($data[$i]>0)
  32. {
  33. $last = $i;
  34. break;
  35. }
  36. }
  37. list($prev,$next) = getPrevNext($data,$last);
  38. if($prev===false)
  39. {
  40. if($last<$boxNum)
  41. {
  42. if($data[1]>1)
  43. {
  44. list($prev,$next) = getPrevNext($data,$last 1);//启用新列
  45. }
  46. else
  47. {
  48. break;//结束
  49. }
  50. }
  51. else
  52. {
  53. break;//结束
  54. }
  55. }
  56. $num = floor(($data[$prev] - $data[$next])/2);
  57. $data[$prev] -= $num;
  58. $data[$next] = $num;
  59. $count = $num;
  60. for($i=1;$i<=$boxNum;$i ) echo $data[$i]."t";
  61. echo "num:".$num."rn";
  62. }
  63. echo '共有'.$count.'种可能'."rn";
  64. function getPrevNext($data,$last)
  65. {
  66. $prev = $next = false;
  67. for($i=$last-1;$i>=1;$i--)
  68. {
  69. if($data[$i]-$data[$i 1]>1)//发现一阶滚落
  70. {
  71. $prev = $i;
  72. $next = $i 1;
  73. break;
  74. }
  75. else if($data[$i]-$data[$last]>1)//发现多阶滚落
  76. {
  77. $prev = $i;
  78. for($k=$i 1;$k<=$last;$k )
  79. {
  80. if($data[$i]-$data[$k]>1)//发现最短多阶滚落
  81. {
  82. $next = $k;
  83. break;
  84. }
  85. }
  86. break;
  87. }
  88. }
  89. return array($prev,$next);
  90. }
复制代码


성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.