Guest User

Untitled

a guest
Aug 14th, 2018
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.03 KB | None | 0 0
  1. combinations of
  2. int f(int n,int a,int x)
  3. {
  4. if(a==1)
  5. {
  6. if(n>=0 && n<=x) //HERE WAS ERROR,sorry
  7. return 1;
  8. else
  9. return 0;
  10. }
  11.  
  12. int ans=0;
  13.  
  14. for(int i=0;i<=x;i++)
  15. ans += f(n-i,a-1,x);
  16.  
  17. return ans;
  18. }
  19.  
  20. int f(int n,int a,int x)
  21. {
  22. int q[1000][50]; // to simplify and not use dynamic allocation assume that a < 50 and n < 1000
  23.  
  24. q[0][0] = 1;
  25. for (int i = 1; i < 1000; ++i)
  26. q[i][0] = 0;
  27.  
  28. for (int i = 1; i <= a; ++i)
  29. {
  30. for (int j = 0; j <= n; j++)
  31. {
  32. int t = 0;
  33. for (int l = 0; l <= j && l <= x; ++l)
  34. t += q[j - l][i-1];
  35. q[j][i] = t;
  36. }
  37. }
  38.  
  39. return q[n][a];
  40. }
  41.  
  42. int f(int n,int a,int x)
  43. {
  44. int q[1000][2]; // to simplify and not use dynamic allocation assume n < 1000
  45.  
  46. q[0][0] = 1;
  47. for (int i = 1; i < 1000; ++i)
  48. q[i][0] = 0;
  49.  
  50. int current = 1;
  51. for (int i = 1; i <= a; ++i)
  52. {
  53. int t = 0;
  54. for (int j = 0; j <= n; j++)
  55. {
  56. t += q[j][1 - current];
  57. if (j > x)
  58. t -= q[j - x - 1][1 - current];
  59.  
  60. q[j][current] = t;
  61. }
  62. current = 1 - current;
  63. }
  64.  
  65. return q[n][1 - current];
  66. }
  67.  
  68. int f(int n, int a, int x){ // should all be unsigned, actually
  69. if (n == 0){
  70. return 1;
  71. }
  72. int p = a*x;
  73. if (p < n){
  74. return 0;
  75. }
  76. if (p == n){
  77. return 1;
  78. }
  79. if (x == 1){
  80. return binom(a,n); // ways to choose n boxes from a boxes
  81. }
  82. // now the interesting cases
  83. int ways = 0; // should perhaps be unsigned long long, that number grows fast
  84. int xCount, tempRes, min, max;
  85. min = a+n-p;
  86. if (min < 0) min = 0;
  87. max = n/x;
  88. for(xCount = min; xCount <= max; ++xCount){
  89. tempRes = f(n - x*xCount,a - xCount, x-1); // ways to distribute the remaining balls
  90. ways += binom(a,xCount)*tempRes; // multiply by the number of ways to choose xCount boxes
  91. }
  92. return ways;
  93. }
Add Comment
Please, Sign In to add comment