Algorithme

[Nadiaidan]

Bonjour tout le monde!
Je suis de nature assez curieuse en ce qui concerne les mathématiques, il y a quelques jours, j'ai découvert un exercice de "suite" permettant de trouver le nombre de façon différentes pour monter un escalier de n marche(s). J'ai trouvé cet exercice très interressant et amusant, mais n'est il pas possible de programmer un algorithme sous algobox par exemple, pour trouver les réponses beaucoup plus facilement et rapidement. Je ne suis pas très douée en algorithme, quelqu'un pourrait il m'aider pour le créer?
Merci beaucoup :)

[mathelot]

bonjour,

si on les monte "b" par "b",ie, (quatre par quatre , b=4)

n=bq+r

on ajoute 1, on regarde si on conserve la division euclidienne

[chan79]

[quote="Nadiaidan"]
Salut
Tu peux regarder ça; c'est pour le cas où on peut monter de 1, 2 ou 3 marches à chaque fois.
Par exemple, avec 6 marches: 24 façons.

[chan79]

Salut
Tu peux regarder ça; c'est pour le cas où on peut monter de 1, 2 ou 3 marches à chaque fois.
Par exemple, avec 6 marches: 24 façons.

[chan79]

Bonjour tout le monde!
Je suis de nature assez curieuse en ce qui concerne les mathématiques, il y a quelques jours, j'ai découvert un exercice de "suite" permettant de trouver le nombre de façon différentes pour monter un escalier de n marche(s). J'ai trouvé cet exercice très interressant et amusant, mais n'est il pas possible de programmer un algorithme sous algobox par exemple, pour trouver les réponses beaucoup plus facilement et rapidement. Je ne suis pas très douée en algorithme, quelqu'un pourrait il m'aider pour le créer?
Merci beaucoup

Salut
Tu peux regarder ça; c'est pour le cas où on peut monter de 1, 2 ou 3 marches à chaque fois.
Par exemple, avec 6 marches: 24 façons.

[Nadiaidan]

Bonjour chan79, merci beaucoup pour cette algorithme, cela va vraiment beaucoup plus vite que de passer par les calculs. ^^ C'est pour être un peu long pour créer l'algorithme lorsque l'on est pas très habituée, mais une fois fait cela va tout seul :)

[fatal_error]

hello,

une variante récursive

Code: Tout sélectionner

function howManyWay(n, steps){
  if(n==0){
    return 1;
  }
  if(n<0){
    return 0;
  }
  var r=0;
  steps.forEach(function(step){
    r += howManyWay(n-step, steps);
  });
  return r;
}
console.log('nb poss : '+howManyWay(6, [1,2,3])); //24

edit:
j'avais oublié, un peu de mémoization, ca fait pas de mal...

Code: Tout sélectionner

var memo={};
function howManyWay(n, steps){
  if(n==0){
    return 1;
  }
  if(n<0){
    return 0;
  }
  if(n in memo){
    return memo[n];
  }
  memo[n] = steps.map(function(step){
    return howManyWay(n - step, steps);
  }).reduce(function(a,b){return a+b});
  return memo[n];
}
console.log('nb poss : '+howManyWay(6, [1,2,3]));