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”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...
标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...
如果不符合,则回溯到上一步,尝试其他可能性。实验结果的截图将有助于直观地展示回溯法的搜索过程。 最后,贪心算法(Greedy Algorithm)是一种在每一步选择局部最优解,期望最终得到全局最优解的策略。在计算加油...
《算法设计与分析》课程笔记代码Part2(动态规划+贪心算法+回溯算法) 本文为博主基于课堂ppt以及自行编写的代码整理的研究生《算法设计与分析》课程笔记,涉及分治算法、动态规划算法、贪心算法、回溯算法、分支...
提供的代码文件"POJ3009-Curling 2.0【DFS+Vector+剪枝】.cpp"和"POJ3009-Curling 2.0【DFS+回溯+剪枝】.cpp"应该分别展示了如何在实际编程中应用这些技术,而"POJ3009-Curling 2.0.doc"则可能是解题报告,详细阐述...
尽管这种方法看起来简单,但在某些问题上(尤其是问题规模较小或者有明显规律可循的场景)非常有效。例如,寻找素数、计算排列组合等。在ACM中,枚举法常与其他算法(如动态规划)结合使用,以提高解题效率。 在...
DFS是一种从起点开始,尽可能深地搜索图的分支,直到达到叶子节点或回溯到无新节点可走为止。其主要步骤包括: 1. 访问当前节点,并将其标记为已访问。 2. 对于当前节点的每一个未访问过的邻居,递归地执行DFS。 3. ...
批处理作业调度回溯法java实现 批处理作业调度回溯法是一种解决作业调度问题的算法,它通过回溯法来搜索所有可能的解决方案,以找到最佳的作业调度方式。在这个Java实现的批处理作业调度程序中,我们使用回溯法来...
回溯法是一种试探性的搜索策略,它尝试逐步构造解决方案,如果在某一步发现当前选择无法导出合法解,就回溯到上一步,改变之前的选择,继续尝试。在n皇后问题中,回溯法会尝试在每行放置一个皇后,同时检查是否违反...
动态规划、回溯算法以及二叉树是计算机科学中重要的算法概念,它们在解决各种问题时发挥着关键作用。这份压缩包文件包含了这些主题的详细讲解,为学习者提供了丰富的学习资源。 首先,动态规划是一种优化技术,常...
八皇后问题则是经典的回溯算法应用例子,目标是在8x8的棋盘上放置8个皇后,使得任意两个皇后都不在同一行、同一列或同一斜线上。这个问题可以通过维护一个表示皇后位置的数组来解决,每行对应一个数组元素,值表示...
利用深度搜索和回溯法解数独,输入为9×9行字符,待填部分用0表示
深度优先搜索(Depth First Search,简称DFS)是一种用于遍历或搜索树或图的算法,它按照“尽可能深”的原则访问节点,直到达到叶节点或回溯到无新节点可访问时为止。在这个过程中,DFS通常与递归和回溯策略结合使用...
总结起来,n皇后问题通过回溯算法在Java中的实现,不仅锻炼了我们的逻辑思维能力,也让我们更好地理解了递归和回溯这两种重要的编程技巧。同时,这个问题也为我们提供了一个在有限搜索空间中寻找解的有效方法,这在...
深度搜索 回溯 int main { string s1 s2; while cin >> s1 >> s2 { count 0; cout << "[" << endl; if s1 length s2 length BackTrake s1 s2 ; cout << "]...
复习资料,是cqbz就来看吧
在选择当前物品时,将当前物品的质量和价值加到当前的质量和价值上,然后继续搜索下一个物品。在不选择当前物品时,将当前物品的价值从remain中减去,然后继续搜索下一个物品。 在搜索过程中,如果当前的价值大于...
Java反编译是开发者在没有源代码的情况下理解或修改已编译的.class文件的重要手段。本合集包含三个工具:jd-gui、jclasslib和JBE,它们都是Java反编译领域的利器,能帮助我们深入洞察Java字节码。 1. **jd-gui**: ...