Question:
Dans ce problème, le scénario que nous évaluons est le suivant: vous vous tenez au pied d'un escalier et vous vous dirigez vers le haut. Une petite foulée montera d'un escalier et une grande foulée en avancera de deux. Vous voulez compter le nombre de façons de monter l'escalier entier en fonction de différentes combinaisons de grandes et petites foulées. Par exemple, un escalier de trois marches peut être monté de trois manières différentes: trois petites enjambées, une petite foulée suivie d'une grande foulée ou une grande suivie d'une petite.
L'appel de wayToClimb (3) devrait produire le résultat suivant:
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);
}
}
Mon code:
1 1 1, 2, 2 1
Ma sortie:
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);
}
}
Ma récursivité ne semble pas se souvenir du chemin qu'il a fallu pour savoir comment y remédier?
Modifier:
Merci les gars pour les réponses. Désolé pour la réponse tardive
J'ai compris
1 1 1, 1 2, 2 1
4 Réponses :
Si vous souhaitez explicitement imprimer tous les chemins (autrement que de les compter ou d'en trouver un spécifique), vous devez les stocker jusqu'à 0.
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);
}
}
appel initial: waysToClimb (5, nouvelle ArrayList
La solution mentionnée ci-dessous fonctionnera de la même manière que la première recherche en profondeur, elle explorera un chemin. Une fois qu'un chemin est terminé, il effectuera un retour en arrière et explorera d'autres chemins:
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) + " ");
}
}
}
}
public class Test2 {
public int climbStairs(int n) {
// List of lists to store all the combinations
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// initially, sending in an empty list that will store the first combination
csHelper(n, new ArrayList<Integer>(), ans);
// a helper method to print list of lists
print2dList(ans);
return ans.size();
}
private void csHelper(int n, List<Integer> l, List<List<Integer>> ans) {
// if there are no more stairs to climb, add the current combination to ans list
if(n == 0) {
ans.add(new ArrayList<Integer>(l));
}
// a necessary check that prevent user at (n-1)th stair to climb using 2 stairs
if(n < 0) {
return;
}
int currStep = 0;
// i varies from 1 to 2 as we have 2 choices i.e. to either climb using 1 or 2 steps
for(int i = 1; i <= 2; i++) {
// climbing using step 1 when i = 1 and using 2 when i = 2
currStep += 1;
// adding current step to the arraylist(check parameter of this method)
l.add(currStep);
// make a recursive call with less number of stairs left to climb
csHelper(n - currStep, l, ans);
l.remove(l.size() - 1);
}
}
private void print2dList(List<List<Integer>> ans) {
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans.get(i).size(); j++) {
System.out.print(ans.get(i).get(j) + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
Test2 t = new Test2();
t.climbStairs(3);
}
}
Please note this solution will timeout for larger inputs as this isn't a memoized recursive solution and can throw MLE(as I create a new list when a combination is found).Hope this helps.
si quelqu'un cherche une solution python, pour ce problème.
def way_to_climb(n, path=None, val=None):
path = [] if path is None else path
val = [] if val is None else val
if n==0:
val.append(path)
elif n==1:
new_path = path.copy()
new_path.append(1)
way_to_climb(n-1, new_path, val)
elif n>1:
new_path1 = path.copy()
new_path1.append(1)
way_to_climb(n-1, new_path1, val)
new_path2 = path.copy()
new_path2.append(2)
way_to_climb(n-2, new_path2, val)
return val
Note: il est basé sur la solution @unlut, ici OP a utilisé une approche récursive top-down. Cette solution est pour toutes les personnes qui recherchent toutes les combinaisons de problèmes d'escalier en python, pas de question python pour cela, j'ai donc ajouté une solution python ici
si nous utilisons une approche ascendante et utilisons la mémorisation, alors nous pouvons résoudre le problème plus rapidement.
La question indique que vous devez compter le nombre de façons différentes, pas les imprimer. Lequel est le résultat attendu?
vous ne comptez pas (additionnez le nombre d'étapes) - chaque appel de wayToClimb ajoute 1 au nombre d'étapes possibles, à moins qu'il ne vous reste 0 pas. où vous mettez l'incrément est juste une décision que vous devez prendre (vous devez seulement faire attention à ne pas compter deux fois).
Attention, les réponses ci-dessous ne couvrent pas très bien le cœur du problème (soit la sémantique en boucle, soit il y a aussi une solution mathématique si vous êtes conscient)