Différentes façons d'obtenir des balles d'une boîte

Question

Vous avez une boîte avec des balles, nous tirons toutes les balles de la boîte.
Mais nous pouvons en tirer un à la fois ou trois à la fois.
Et l'ordre d'extraction importe.
La question est de savoir combien de façons différentes il y a d'extraire les boules.
Donc si le :
La boîte contient 1 balle, il n'y a qu'un seul chemin.
La boîte contient 2 balles, il n'y a qu'un seul moyen.
La boîte contient 3 balles, il y a 2 façons de tirer (1 par 1 ou 3 en même temps).
La boîte contient 4 balles, il y a 3 façons de les utiliser :
1111
13
31

Et le résultat était que pour 7 boules, il y avait 9 façons différentes d'extraire les boules de la boîte.

La question est donc de savoir combien de balles il y a dans la boîte,

La solution que j'ai trouvée était récursive :

Int calculate(int balls){
   If(balls=0) return 0;
   If(balls=1) return 1;
   If(balls=2) return 1;
   If(balls=3) return 2;
    If(balls=4) return 3;

 return calculate(balls-1) + calculate(balls-3);
}

Est-ce correct ?
Existe-t-il un moyen de le faire sans utiliser la récursion ?

Merci.

Answer 1

Votre solution est correcte. Cependant, il existe des moyens d'améliorer les performances de l'algorithme en utilisant une technique appelée programmation dynamique. Dans ce cas, vous pouvez mémoriser les résultats, c'est-à-dire stocker tous les résultats intermédiaires dans une table de consultation après avoir calculé chacun d'eux une fois par récurrence. Cela permet de réaliser en temps linéaire une solution qui nécessite normalement un temps exponentiel. Voici un exemple d'implémentation de cette méthode en JavaScript :

function calculate (balls, map = []) {
  if (balls in map) {
    return map[balls]
  }

  switch (balls) {
  case 0:
    return 0
  case 1:
    return 1
  case 2:
    return 1
  case 3:
    return 2
  default:
    return map[balls] = calculate(balls - 1, map) + calculate(balls - 3, map)
  }
}

console.time('dynamic')
console.log(calculate(50))
console.timeEnd('dynamic')

Comparez cela à l'algorithme naïf :

function calculate (balls) {
  switch (balls) {
  case 0:
    return 0
  case 1:
    return 1
  case 2:
    return 1
  case 3:
    return 2
  default:
    return calculate(balls - 1) + calculate(balls - 3)
  }
}

console.time('naive')
console.log(calculate(50))
console.timeEnd('naive')

Answer 2

Vous n'avez pas besoin de mémorisation (du moins pas pour toutes les valeurs) ou de résoudre la récursion pour écrire un programme non récursif pour ce cas - ou des cas similaires.

Quelque chose comme ce qui suit fera l'affaire :

function calculate (balls) {
   if (balls=0) return 0; /* Or remove this line */
   if (balls<3) return 1;
   resMinus3=1;  /* The result for i-3 */
   resMinus2=1;  /* For i-2 */
   resMinus1=1;  /* And for i-1 */
   for(i=3;;++i) {
      newRes=resMinus1+resMinus3; /* The recursion formula */
      if (i>=balls) return newRes;
      resMinus3=resMinus2; /* Shifting results */
      resMinus2=resMinus1;
      resMinus1=newRes;
   }
}

La raison en est que pour calculer la valeur des boules, vous n'avez besoin que des valeurs des boules 1 et 3, de sorte que vous n'avez besoin que de garder la trace de trois résultats précédents pour mettre à jour le nouveau. Vous pourriez également écrire ceci comme une mise à jour de la matrice :

[resMinus1;resMinus2;resMinus3] <-[0,1,0;0,0,1;1,0,1]*[resMinus1;resMinus2;resMinus3]

Answer 3

D'un lien dans les commentaires on peut trouver cette équation :

a(n) = Somme_{i=0..floor(n/3)} binomiale(n-2*i, i)

function binom(n, k) {
  var coeff = 1;
  for (var i = n-k+1; i <= n; i++) coeff *= i;
  for (var i = 1;     i <= k; i++) coeff /= i;
  return coeff;
}
function calculate (balls) {
  sum = 0;
  for (i = 0; i <= Math.floor(balls/3); i++){
      sum += binom(balls - 2*i, i);
  }
  return sum;

}
console.time('someMathGenius')
console.log(calculate(50))
console.timeEnd('someMathGenius')

Answer 4

Pour N boules, vous pouvez tirer entre 0 et floor(n/3) triples.

Pour N boules où vous tirez k triples, vous tirez aussi N-3k simples.

Maintenant, le problème se réduit à compter les façons distinctes dont on peut ordonner k choses d'un type, et N-3k choses d'un autre type. C'est choisir(k + N-3k, k) = choisir(N-2k,k).

La réponse finale est la somme de k=0 à floor(N/3) de choose(N-2k,k).

N=0: choose(0,0) = 1 so there is 1 way of choosing nothing.
N=1: choose(1,0) = 1
N=2: choose(2,0) = 1
N=3: choose(3,0) + choose(1,1) = 1+1 = 2
N=4: choose(4,0) + choose(2,1) = 1+2 = 3
...
N=7: choose(7,0) + choose(5,1) + choose(3,2) = 1 + 5 + 3 = 9