Home  >  Article  >  Backend Development  >  Bowl A. Each bowl can hold B balls. There are C balls in total. How many ways are there (the balls are exactly the same)?

Bowl A. Each bowl can hold B balls. There are C balls in total. How many ways are there (the balls are exactly the same)?

WBOY
WBOYOriginal
2016-07-25 08:48:221236browse
The bowl is the same, the ball is the same, change your thinking.
For the table in column A and row B, each steel ball can be placed in a grid, for a total of C steel balls.
Move the steel ball to create various possibilities. In order to avoid duplication and omission, we move the steel balls according to the following rules.
Place steel balls from left to right. After the first column is full, place the second column; and so on.
When moving the steel balls, always ensure that the number of steel balls in any column on the left is no less than that in any column on the right.
Every time a steel ball is moved, a possible situation occurs, and the counter increases by 1.
  1. $boxNum = 20;
  2. $size = 10;
  3. $total = 33;
  4. //Initialization
  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. //Find the last value
  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);//Enable new column
  45. }
  46. else
  47. {
  48. break;//End
  49. }
  50. }
  51. else
  52. {
  53. break;//End
  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 'There are'.$count.' possibilities'."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)//First-order rolling found
  70. {
  71. $prev = $i;
  72. $next = $i+1;
  73. break;
  74. }
  75. else if($data[$i]-$data[$last] >1)//Multiple-order rolling is found
  76. {
  77. $prev = $i;
  78. for($k=$i+1;$k<=$last;$k++)
  79. {
  80. if($data[$ i]-$data[$k]>1)//Find the shortest multi-step roll-off
  81. {
  82. $next = $k;
  83. break;
  84. }
  85. }
  86. break;
  87. }
  88. }
  89. return array($ prev,$next);
  90. }
Copy code


Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn