Compter le nombre de chemins possibles jusqu'à l'échelle

Je n'arrive pas à trouver un algorithme pour résoudre le problème suivant, j'ai essayé à l'aide d'une série de boucles, mais il est devenu trop compliqué:

Une échelle de a n étapes, on peut monter à l'échelle à l'aide de tout
combinaison d'étapes de 1 ou étapes de 2. De combien de façons possibles sont
il y pour un pour monter à l'échelle?

Ainsi, par exemple, si l'échelle a 3 étapesce serait les chemins possibles:

  • 1-1-1
  • 2-1
  • 1-2

Et pour 4 étapes

  • 1-1-1-1
  • 2-1-1
  • 1-2-1
  • 1-1-2
  • 2-2

Aucune indication sur la manière dont cela pourrait être fait serait grandement apprécié. Aussi, je travaille en Java.

Edit: j'étais en effet en cours à l'aide de petits n valeurs, mais il serait certainement intéressant de savoir comment gérer avec les plus grands.

source d'informationauteur

  1. 28

    Fait intéressant, il existe une solution simple à ce problème. Vous pouvez utiliser la récursivité:

    public static int countPossibilities(int n) {
    if (n == 1 || n == 2) return n;
    return countPossibilities(n - 1) + countPossibilities(n - 2);
}

    Chaque fois que vous êtes confronté à ce type de "tricky" problème, l'ours à l'esprit que la solution est souvent assez élégant, et de toujours vérifier pour voir si quelque chose peut être fait avec la récursivité.

    MODIFIER: je suis en supposant que vous avez de traiter avec relativement peu de n valeurs de ce problème, mais si vous faites affaire avec les grands alors la méthode ci-dessus va probablement prendre une bonne quantité de temps pour terminer. Une solution serait d'utiliser un Map que serait la carte n à countPossibilities(n) - de cette façon, il n'y aurait pas de perte de temps de faire un calcul que vous avez déjà fait. Quelque chose comme ceci:

    private static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
static {
    map.put(1, 1);
    map.put(2, 2);
}

public static int countPossibilities(int n) {
    if (map.containsKey(n))
        return map.get(n);

    int a, b;

    if (map.containsKey(n - 1))
        a = map.get(n - 1);
    else {
        a = countPossibilities(n - 1);
        map.put(n - 1, a);
    }

    if (map.containsKey(n - 2))
        b = map.get(n - 2);
    else {
        b = countPossibilities(n - 2);
        map.put(n - 2, b);
    }

    return a + b;
}

    Essayez-le avec les n = 1000. La deuxième méthode est littéralement ordres de grandeur plus rapide que le premier.

  2. 7

    C'est en fait étroitement liée à la La suite de Fibonaccicomme il a été mentionné que brièvement dans l'un des commentaires à ce jour: Chaque étape n peut être atteint de deux étapes ci-dessous (n-2) ou l'une des étapes ci-dessous (n-1), donc le nombre de possibilités pour atteindre cette étape est la somme des possibilités pour atteindre ces deux étapes. Enfin, il y a exactement une possibilité d'atteindre la première étape (et le zéro, c'est à dire en restant sur le terrain).

    Aussi, car le nombre de possibilités pour l'étape n dépend uniquement sur les résultats de l'étape n-1 et n-2il n'est pas nécessaire de stocker toutes ces valeurs intermédiaires dans une carte ou dans un tableau -- les deux derniers sont assez!

    public static long possForStep(int n) {
    //current and last value, initially for n = 0 and n = 1
    long cur = 1, last = 1;
    for (int i = 1; i < n; i++) {
        //for each step, add the last two values and update cur and last
        long tmp = cur;
        cur = cur + last;
        last = tmp;
    }
    return cur;
}

    Ce n'est pas seulement réduit la quantité de code par une bonne action, mais aussi donne une complexité de O(n) dans le temps et O(1) dans l'espace, par opposition à O(n) dans le temps et de l'espace lors du stockage de toutes les valeurs intermédiaires.

    Toutefois, étant donné que même les long type va rapidement débordement comme n se rapproche de 100, de toute façon, l'espace de la complexité de O(n) n'est pas vraiment un problème, vous pouvez tout aussi bien aller avec cette solution, qui est beaucoup plus facile à lire.

    public static long possForStep(int n) {
    long[] values = new long[n+1];
    for (int i = 0; i <= n; i++) {
        //1 for n==0 and n==1, else values[i-1] + values[i-2];
        values[i] = (i <= 1) ?  1 : values[i-1] + values[i-2];
    }
    return values[n];
}

    Mise à jour: Remarque que c'est très proche, mais pas tout à fait la même que la séquence de Fibonacci, qui commence 0, 1, 1, 2, 3,... alors que celui-ci va 1, 1, 2, 3, 5, ...c'est à dire possForStep(n) == fibonacci(n+1).

  3. 1

    Je voudrais utiliser la programmation dynamique et à chaque fois de résoudre un problème où l'échelle est de 1 échelon ou 2 échelons plus courte.

    def solveLadder(numOfRungs):
  if numOfRungs<=2:
    return numOfRungs
  return solveLadder(numOfRungs-1)+solveLadder(numOfRungs-2)
  4. 0

    C'est un arbre avec la récursivité. Vous pourriez avoir besoin de revenir en arrière pour les cas qui ne peuvent pas travailler (par exemple 2-2 pour une période de trois escalier échelle).

  5. 0

    C'est la suite de fibonacci. Vous pouvez le résoudre élégamment à l'aide de la queue récursive de la récursivité:

        let ladder n =
        let rec aux n1 n2 n =
            if n=0 then (n1 + n2)
            else aux n2 (n1+n2) (n-1)
        aux 1 1 (n-2)

    Plus facile à comprendre non-queue récursive code serait:

        let rec ladder n =
        if n<=2 then n
        else ladder (n-1) + ladder (n-2)

    Vous pouvez facilement traduire qu'à Java.

  6. -2
    1. Élément de la liste

    C'est simple suite de fibonacci si le pas de mesure que nous pouvons prendre est de 1 ou 2
    pour

    • Pas d'escalier, cas possible

      1------------------1

      2------------------2

      3------------------3

      4------------------5

      5------------------8

      6------------------13

    et ainsi de suite