Проблема с лестницей: как распечатать комбинации? - PullRequest
Новая
       27

Проблема с лестницей: как распечатать комбинации?

0 голосов
/ 09 февраля 2019

Вопрос:

В этой задаче мы оцениваем следующий сценарий: Вы стоите у основания лестницы и идете наверх.Небольшой шаг поднимется на одну ступеньку, а большой шаг - на две.Вы хотите рассчитать количество способов подняться по всей лестнице на основе различных комбинаций больших и малых шагов.Например, по лестнице из трех ступеней можно подняться тремя различными способами: три маленьких шага, один маленький шаг, за которым следует один большой шаг, или один большой, а затем один маленький.

Вызов путей(3) должен выдать следующий вывод: 

1 1 1,
1 2,
2 1

Мой код: 

public static void waysToClimb(int n){
    if(n == 0) 
        System.out.print("");
    else if(n == 1)
        System.out.print("1");
    else {
        System.out.print("1 "); 
        waysToClimb(n - 1);
        System.out.print(",");
        System.out.print("2 ");
        waysToClimb(n - 2);
    }
}

Мой вывод: 

1 1 1,
2,
2 1

Моя рекурсия не запоминаетсяпуть, который потребовалось, чтобы понять, как это исправить?

Редактировать:

Спасибо, ребята, за ответы.Извините за поздний ответ

Я понял это 

public static void waysToClimb(int n){

String s ="[";
int p=0;
com(s,p,n);

}

public static void com (String s, int p, int n) {

if(n==0 && p==2)

System.out.print(s.substring(0,s.length()-2)+"]");

else if(n==0 && p !=0)

System.out.print(s+"");

else if(n==0 && p==0)

System.out.print("");

else if(n==1)

System.out.print(s+"1]");

else {

    com(s+"1, ",1,n-1);
    System.out.println();
    com(s+"2, ",2,n-2);

}

}

Ответы [ 2 ]

0 голосов
/ 09 февраля 2019

Ниже упомянутое решение будет работать аналогично поиску в глубину, оно будет исследовать один путь.Как только путь завершен, он будет отслеживать и исследовать другие пути: 

public class Demo {
    private static LinkedList<Integer> ll = new LinkedList<Integer>(){{ add(1);add(2);}};

    public static void main(String args[]) {
        waysToClimb(4, "");
    }

    public static void waysToClimb(int n, String res) {
        if (ll.peek() > n)
            System.out.println(res);
        else {
            for (Integer elem : ll) {
                if(n-elem >= 0)
                    waysToClimb(n - elem, res + String.valueOf(elem) + " ");
            }
        }
    }
}
0 голосов
/ 09 февраля 2019

Если вы явно хотите напечатать все пути (отличные от подсчета или нахождения определенного), вам нужно сохранить их до нуля. 

public static void waysToClimb(int n, List<Integer> path)
{
    if (n == 0)
    {
        //  print whole path
        for (Integer i: path)
        {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    else if (n == 1)
    {
        List<Integer> newPath = new ArrayList<Integer>(path);
        newPath.add(1);
        waysToClimb(n-1, newPath);
    }
    else if (n > 1)
    {
        List<Integer> newPath1 = new ArrayList<Integer>(path);
        newPath1.add(1);
        waysToClimb(n-1, newPath1);

        List<Integer> newPath2 = new ArrayList<Integer>(path);
        newPath2.add(2);
        waysToClimb(n-2, newPath2);
    }
}

начальный вызов: waysToClimb(5, new ArrayList<Integer>());

...