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>
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1772172
动态规划算法-多边形游戏。回溯法-符号三角形问题。贪心算法-计算加油次数。包括流程图+代码+实验结果截屏+实验总结。
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
《算法设计与分析》课程笔记代码Part2(动态规划+贪心算法+回溯算法) 本文为博主基于课堂ppt以及自行编写的代码整理的研究生《算法设计与分析》课程笔记,涉及分治算法、动态规划算法、贪心算法、回溯算法、分支...
利用深度搜索和回溯法解数独,输入为9×9行字符,待填部分用0表示
矩阵链乘和n皇后问题的程序和解题报告 其中n皇后问题采用两种方法求解:1、回溯法;2、随机算法与回溯法结合。
搜集到一些学校关于acm培训的资料,这里共享下。哈哈,希望大家能够多多交流
133
深度搜索 回溯 int main { string s1 s2; while cin >> s1 >> s2 { count 0; cout << "[" << endl; if s1 length s2 length BackTrake s1 s2 ; cout << "]...
复习资料,是cqbz就来看吧
本例是java实现的批处理作业调度程序,采用的是回溯法,排列集合的方式,参考书籍为:算法设计与分析
用回溯法解决01背包问题,用c语言编写的源代码
用java写了一个回溯法求解迷宫的程序,还有一个八皇后的问题,因为水平一般,不敢说一定正确,但是希望对你有一些提示。
回溯法实现n皇后问题,并输出每种放法的皇后位置
本例采用java实现的0-1背包问题,采用的是回溯法,参考算法设计与分析(第二版)
0-1背包 Java 回溯法 0-1背包 Java 回溯法 0-1背包 Java 回溯法
计算机学科作业,回溯法实现01背包问题JAVA版.txt
栈与递归--含分治与回溯.zip
本程序是用Java开发的,使用回溯法解决01背包问题。程序比较易懂。输入分三行,第一行是物品数量N和背包容量C,第二行是物品重量数组,第三行是价值重量数组。然后输出最优解。