`
128kj
  • 浏览: 601277 次
  • 来自: ...
社区版块
存档分类
最新评论

上楼梯(深搜+回溯)JAVA解答

阅读更多
N阶楼梯上楼问题:一次可以走两阶或一阶,请把所有行走方式打印出来。

import java.util.Scanner;
 public class Main{
   private int n;
   private int[] answer;//存入上楼梯的方法
   private int ways;//上楼梯方法总数
  
   public Main(int n){
      this.n=n;
      answer=new int[n+1];
   }

   public int getWays(){
     return ways;
   }

   //第level步上到了第step阶
   public void  GoUp(int level,int step){
    if(step>n) return;
    if(step == n)//已经走到尽头   
    {  
        ways++;  
        for(int i=0; i<level; i++) 
         System.out.printf("%d\t",answer[i]);  
        System.out.println();  
        return;  
    }  
    for(int i=1; i<=2; i++)//2种分枝   
    {  
       
     answer[level] = i;//记录解向量   
     //继续递归走下一步,注意递归自动隐含level和step的回溯过程!!   
     GoUp(level+1,step+i);  
     //answer[level]=0;//恢复现场,
      
    }  
   
  }  
  public static void main(String[] args){  
    Scanner in=new Scanner(System.in);
    System.out.println("请输入楼梯的阶数");
    int n =in.nextInt();  
    Main ma=new Main(n);
    ma.GoUp(0,0);  
    System.out.printf("Totally %d ways .\n",ma.getWays());  
  }
}  

程序运行:
C:\test>java Main
请输入楼梯的阶数
5
1       1       1       1       1
1       1       1       2
1       1       2       1
1       2       1       1
1       2       2
2       1       1       1
2       1       2
2       2       1
Totally 8 ways .

C:\test>java Main
请输入楼梯的阶数
6
1       1       1       1       1       1
1       1       1       1       2
1       1       1       2       1
1       1       2       1       1
1       1       2       2
1       2       1       1       1
1       2       1       2
1       2       2       1
2       1       1       1       1
2       1       1       2
2       1       2       1
2       2       1       1
2       2       2
Totally 13 ways .

C:\test>
分享到:
评论

相关推荐

    图的深搜+回溯练习题:POJ2197

    标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...

    图的深搜+树状数组练习 POJ 3321(JAVA)

    标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...

    动态规划算法+贪心算法+回溯法实验文档

    如果不符合,则回溯到上一步,尝试其他可能性。实验结果的截图将有助于直观地展示回溯法的搜索过程。 最后,贪心算法(Greedy Algorithm)是一种在每一步选择局部最优解,期望最终得到全局最优解的策略。在计算加油...

    《算法设计与分析》课程笔记(代码:动态规划+贪心算法+回溯算法) by 浅若清风cyf

    《算法设计与分析》课程笔记代码Part2(动态规划+贪心算法+回溯算法) 本文为博主基于课堂ppt以及自行编写的代码整理的研究生《算法设计与分析》课程笔记,涉及分治算法、动态规划算法、贪心算法、回溯算法、分支...

    POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】

    提供的代码文件"POJ3009-Curling 2.0【DFS+Vector+剪枝】.cpp"和"POJ3009-Curling 2.0【DFS+回溯+剪枝】.cpp"应该分别展示了如何在实际编程中应用这些技术,而"POJ3009-Curling 2.0.doc"则可能是解题报告,详细阐述...

    acm常用算法(分治+回溯+枚举)

    尽管这种方法看起来简单,但在某些问题上(尤其是问题规模较小或者有明显规律可循的场景)非常有效。例如,寻找素数、计算排列组合等。在ACM中,枚举法常与其他算法(如动态规划)结合使用,以提高解题效率。 在...

    邻接表实现图的广搜和深搜(java模板)

    DFS是一种从起点开始,尽可能深地搜索图的分支,直到达到叶子节点或回溯到无新节点可走为止。其主要步骤包括: 1. 访问当前节点,并将其标记为已访问。 2. 对于当前节点的每一个未访问过的邻居,递归地执行DFS。 3. ...

    批处理作业调度回溯法java实现

    批处理作业调度回溯法java实现 批处理作业调度回溯法是一种解决作业调度问题的算法,它通过回溯法来搜索所有可能的解决方案,以找到最佳的作业调度方式。在这个Java实现的批处理作业调度程序中,我们使用回溯法来...

    矩阵链乘和n皇后问题的程序和解题报告(随机法+回溯法)

    回溯法是一种试探性的搜索策略,它尝试逐步构造解决方案,如果在某一步发现当前选择无法导出合法解,就回溯到上一步,改变之前的选择,继续尝试。在n皇后问题中,回溯法会尝试在每行放置一个皇后,同时检查是否违反...

    动态规划+回溯算法+二叉树等算法做法文档整理

    动态规划、回溯算法以及二叉树是计算机科学中重要的算法概念,它们在解决各种问题时发挥着关键作用。这份压缩包文件包含了这些主题的详细讲解,为学习者提供了丰富的学习资源。 首先,动态规划是一种优化技术,常...

    回溯算法java实例

    八皇后问题则是经典的回溯算法应用例子,目标是在8x8的棋盘上放置8个皇后,使得任意两个皇后都不在同一行、同一列或同一斜线上。这个问题可以通过维护一个表示皇后位置的数组来解决,每行对应一个数组元素,值表示...

    解数独深度搜索+回溯法+解数独问题

    利用深度搜索和回溯法解数独,输入为9×9行字符,待填部分用0表示

    递归回溯深度优先搜索DFS练习题(含C++源码)

    深度优先搜索(Depth First Search,简称DFS)是一种用于遍历或搜索树或图的算法,它按照“尽可能深”的原则访问节点,直到达到叶节点或回溯到无新节点可访问时为止。在这个过程中,DFS通常与递归和回溯策略结合使用...

    n后问题回溯算法 java

    总结起来,n皇后问题通过回溯算法在Java中的实现,不仅锻炼了我们的逻辑思维能力,也让我们更好地理解了递归和回溯这两种重要的编程技巧。同时,这个问题也为我们提供了一个在有限搜索空间中寻找解的有效方法,这在...

    ZOJ1004回溯+深搜

    深度搜索 回溯 int main { string s1 s2; while cin &gt;&gt; s1 &gt;&gt; s2 { count 0; cout &lt;&lt; &quot;[&quot; &lt;&lt; endl; if s1 length s2 length BackTrake s1 s2 ; cout &lt;&lt; &quot;]...

    递归+回溯 cqbz2026/2024/3/2

    复习资料,是cqbz就来看吧

    0-1背包回溯法java实现

    在选择当前物品时,将当前物品的质量和价值加到当前的质量和价值上,然后继续搜索下一个物品。在不选择当前物品时,将当前物品的价值从remain中减去,然后继续搜索下一个物品。 在搜索过程中,如果当前的价值大于...

    jd-gui+jclasslib+jbe java反编译工具合集

    Java反编译是开发者在没有源代码的情况下理解或修改已编译的.class文件的重要手段。本合集包含三个工具:jd-gui、jclasslib和JBE,它们都是Java反编译领域的利器,能帮助我们深入洞察Java字节码。 1. **jd-gui**: ...

Global site tag (gtag.js) - Google Analytics