public class ClimbStairs { public static final int N = 10;//有N级楼梯 public static final int ONE = 1;//一步可以迈1级 public static final int TWO = 2;//一步可以迈2级 public static final int THREE = 3;//一步可以迈3级 public static void main(String[] args) {
int max_ONE = N/ONE;//如果只迈ONE,最多需要max_ONE int max_TWO = N/TWO;//如果只迈TWO,最多需要max_TWO int max_Three = N/THREE;//如果只迈THREE,最多需要max_THREE
呵呵,工作后很少做这种题,早上起来做个也挺有意思的.这种题主要是要实际情景抽象成编程问题,考察建模能力下面是我的代码,就是递归,如果有朋友用while循环做,我也参考参考 /* * To change this template, choose Tools | Templates and open the template in * the editor. */ package com.csdn.question;import java.util.ArrayList; import java.util.List;/** * Description: 一个人爬楼梯,一步可以迈一级,二级,三级台阶,如果楼梯有N级,编写程序,输出所有走法。java实现。 * Thinking: 先试探性的走出第一步,在第一步的基础上递归处理剩下的台阶数,直到最后走出一棵树,然后遍历树,打印出路径 * @author karl */ public class ClimbStairs_ThunderSubject {
public static final int step_1 = 1; //一步一级 public static final int step_2 = 2; //一步二级 public static final int step_3 = 3; //一步三级
/** * Description: 开始走楼梯,即创建基于根节点root的树 * @param root 根节点 * @param n 楼梯级数 */ public static void climbStaris_CreateTree( Node root ,int n){ if( n == 1 ){ //若台阶数为1,则只能走一步一级 Node step = new Node(step_1); root.children.add(step); }else if( n == 2 ){ //若台阶数为2,第一步可以走一级,也可以走两阶,用for循环处理 for( int i=1; i<=2; i++ ){ Node step = new Node(i); root.children.add(step);
//走完第一步,剩下的台阶数递归处理 int left = n - i; climbStaris_CreateTree(step,left); } }else if( n >= 3 ){ //做台阶数大于等于3,则第一步有三种走法,一级,二级,或三级,for循环处理 for( int i=1; i<=3; i++){ Node step = new Node(i); root.children.add(step);
//走完第一步,剩下的台阶数递归处理 int left = n - i; climbStaris_CreateTree(step,left); } }
public static void main(String[] args){ Node root = new Node(); climbStaris_CreateTree(root,4); printPath_ergodicTree(root,"start"); }
} /** * Description: 定义树的节点 * @author karl */class Node{
int val; List<Node> children = new ArrayList<Node>();
Node(){} Node( int val ){ this.val = val; }
}
public static void main(){ int one , two three ,N; N = 10; for( one = 1 ; one < N ; one++ ){ for( two = 1 ; two < N/2 ; two++) { for( three = 1 ; three < N/3 ; three++) if( one+(two*2)+(three*3) == N ){ System.out.println(one,two three); } } } }感觉大概是这样的吧,但是我觉得这个题的本意不是说要你输出每次上楼时,统计跨了一节台阶的次数,跨了两个节台阶的次数,跨了三个节台阶的次数,这样这个题目不是很难。题的本意应该是输出上楼时每步的情况,如对于one=1,two=2,three=3这种统计结果,其实又包含好几种方式,如第three可以先跨,也可以后跨。如果要把着样的可能性全输出就比较难了,代码怎么写,还没想出来。
long long GetResult(unsigned int n) { int result[3] = {1,2 ,4}; if(n < 4) return result[n]; else return GetResult(n - 1) + GetResult(n - 2)-GetResult(n-3); }
#62的,java社区,你搞个c出来干什么?
java: // 每一步能走的台阶数 private static final int s1 = 1; private static final int s2 = 2; private static final int s3 = 3; //存储台阶走法List private static List<int[]> methodList = new ArrayList<int[]>(); //主方法,参数(台阶数)大于等于 3 即可 private static void step(int n) { for (int i = 1; i <= 3; i++) { int[] intArray = new int[n]; intArray[0] = i; methodList.add(intArray); } int arrayCount = 3; int completeCount = 0; int currentListSize = 0; while (completeCount != methodList.size()) { currentListSize = methodList.size(); for (int i = 0; i < methodList.size(); i++) { if (i == currentListSize) { break; } int[] intTemp = methodList.get(i); if (sum(intTemp) + s3 <= n) { int[] itt1 = new int[n]; System.arraycopy(intTemp, 0, itt1, 0, n); itt1[site(itt1)] = s3; methodList.add(arrayCount, itt1); arrayCount++; int[] itt2 = new int[n]; System.arraycopy(intTemp, 0, itt2, 0, n); itt2[site(itt2)] = s2; methodList.add(arrayCount, itt2); arrayCount++; intTemp[site(intTemp)] = s1; } else if (sum(intTemp) + s2 <= n) { int[] itt3 = new int[n]; System.arraycopy(intTemp, 0, itt3, 0, n); itt3[site(itt3)] = s2; methodList.add(arrayCount, itt3); arrayCount++; intTemp[site(intTemp)] = s1; } else if (sum(intTemp) + s1 <= n) { intTemp[site(intTemp)] = s1; } } completeCount = 0; for (int i = 0; i < methodList.size(); i++) { int[] intTemp = methodList.get(i); if (sum(intTemp) == n) { completeCount++; } } } } //目前走了多少台阶 private static int sum(int[] intParam) { int intTotal = 0; for (int j = 0; j < intParam.length; j++) { if (intParam[j] > 0) { intTotal += intParam[j]; } } return intTotal; } //目前走到第几步 private static int site(int[] intParam) { int site = 0; for (int j = 0; j < intParam.length; j++) { if (intParam[j] == 0) { site = j; break; } } return site; }
对57楼的代码进行了补充 打印出来详细的步骤import java.util.*; public class ClimbStairs { public static ArrayList<String> stepList = new ArrayList<String>(); public static void main(String[] args) { int n = 10; System.out.println(go(n,"")); showListStep();
} public static int go(int n,String left) { if(n == 1) { stepList.add(left+"-1"); return 1; } if(n == 2) {
import java.util.*;public class Main { int MAX = 10000000, n, method; int[] step = new int[MAX]; public static void main(String args[]) { new Main().run(); } void run() { Scanner in = new Scanner(System.in); while(in.hasNext()) { n = in.nextInt(); method = 0; goUp(0,0); System.out.println("Total case:"+method); } } void goUp(int curFloor,int curStep) { if(curFloor == n) { method++; System.out.println("Case "+method+":"); for(int i=0; i<curStep; i++) { System.out.print(step[i]+" "); } System.out.print("\n"); return; } if(curFloor+1 <= n) { //尝试向上走1步 step[curStep] = 1; goUp(curFloor+1,curStep+1); } if(curFloor+2 <= n) { //尝试向上走2步 step[curStep] = 2; goUp(curFloor+2,curStep+1); } if(curFloor+3 <= n) { //尝试向上走3步 step[curStep] = 3; goUp(curFloor+3,curStep+1); } } }
类斐波那契 1,递归实现(C++): int calcSteps(int n) { assert(n > 0); if (n==1) return 1; if (n==2) return 3; if (n==3) return 4; return calcSteps(n-1) + calcSteps(n-2) + calcSteps(n-3); }2,迭代实现(C++): int calcSteps(int n) { assert(n > 0); int n1 = 1; int n2 = 3; int n3 = 4; if (n==1) return n1; if (n==2) return n2; if (n==3) return n3; int ret; for (int i = 4; i <= n; i++) { ret = n1 + n2 + n3; n1 = n2; n2 = n3; n3 = ret; } return ret; }
public class StairsTest { /** * @param args */ public static void main(String[] args) { int x ; int y ; int z ; int n =9 ; for(x=0;x<n;x++){ for(y=0;y<n/2;y++){ for(z=0;z<n/3;z++){ if(x+2*y+3*z==n){ System.out.println("第一步-->"+x+"第二步-->"+y+"第三部-->"+z); } } } } }} 这种应该是最没文化的了。
忘了java怎么写了,简单写个C++的,这个在于算法怎么写,用啥语言都差不多吧
package sercli;public class Cal { /** * @测试一下 */ public static void main(String[] args) { Cal cc=new Cal(); int answer1=cc.getNum(1); int answer2=cc.getNum(2); int answer3=cc.getNum(3); int answer4=cc.getNum(4); int answer5=cc.getNum(5); int answer6=cc.getNum(6); int answer7=cc.getNum(7);
改一下:package sercli;public class Cal { /** * @测试一下 */ public static void main(String[] args) { Cal cc=new Cal(); int answer1=cc.getNum(1); int answer2=cc.getNum(2); int answer3=cc.getNum(3); int answer4=cc.getNum(4); int answer5=cc.getNum(5); int answer6=cc.getNum(6); int answer7=cc.getNum(7);
public class ClimbStairs {
public static final int N = 10;//有N级楼梯
public static final int ONE = 1;//一步可以迈1级
public static final int TWO = 2;//一步可以迈2级
public static final int THREE = 3;//一步可以迈3级
public static void main(String[] args) {
int max_ONE = N/ONE;//如果只迈ONE,最多需要max_ONE
int max_TWO = N/TWO;//如果只迈TWO,最多需要max_TWO
int max_Three = N/THREE;//如果只迈THREE,最多需要max_THREE
for(int i=0; i<=max_ONE; i++){
int temp_ONE = i;//一步1级已迈出的级数
for(int j=0; j<=max_TWO - temp_ONE/2; j++){
int temp_TWO = j*2;//一步2级已迈出的级数
for(int k=0; k<=max_Three - temp_ONE/3 - temp_TWO/3; k++){
int temp_THREE = k*3;//一步3级已迈出的级数
if(temp_ONE+temp_TWO+temp_THREE == N) System.out.println(i + " " + j + " "+ k);
}
}
}
}
}
/*
0 2 2
0 5 0
1 0 3
1 3 1
2 1 2
2 4 0
3 2 1
4 0 2
4 3 0
5 1 1
6 2 0
7 0 1
8 1 0
10 0 0
*/
在temp__THREEE=N/3+1;
关于你的if语句判断if(10<=temp_ONE+temp_TWO+temp_THREE <=12),你再试下,应该可以的
/*
* To change this template, choose Tools | Templates and open the template in
* the editor.
*/
package com.csdn.question;import java.util.ArrayList;
import java.util.List;/**
* Description: 一个人爬楼梯,一步可以迈一级,二级,三级台阶,如果楼梯有N级,编写程序,输出所有走法。java实现。
* Thinking: 先试探性的走出第一步,在第一步的基础上递归处理剩下的台阶数,直到最后走出一棵树,然后遍历树,打印出路径
* @author karl
*/
public class ClimbStairs_ThunderSubject {
public static final int step_1 = 1; //一步一级
public static final int step_2 = 2; //一步二级
public static final int step_3 = 3; //一步三级
/**
* Description: 开始走楼梯,即创建基于根节点root的树
* @param root 根节点
* @param n 楼梯级数
*/
public static void climbStaris_CreateTree( Node root ,int n){
if( n == 1 ){ //若台阶数为1,则只能走一步一级
Node step = new Node(step_1);
root.children.add(step);
}else if( n == 2 ){ //若台阶数为2,第一步可以走一级,也可以走两阶,用for循环处理
for( int i=1; i<=2; i++ ){
Node step = new Node(i);
root.children.add(step);
//走完第一步,剩下的台阶数递归处理
int left = n - i;
climbStaris_CreateTree(step,left);
}
}else if( n >= 3 ){ //做台阶数大于等于3,则第一步有三种走法,一级,二级,或三级,for循环处理
for( int i=1; i<=3; i++){
Node step = new Node(i);
root.children.add(step);
//走完第一步,剩下的台阶数递归处理
int left = n - i;
climbStaris_CreateTree(step,left);
}
}
}
/**
* Description: 打印楼梯的走法,即遍历整个树
* @param root 需要遍历的父节点
* @param rootPath 需要遍历的父节点相对于树根节点的路径
*/
public static void printPath_ergodicTree( Node root, String rootPath){
//若传入的父节点即为叶子几点,则直接打印其路径,完毕后回,遍历下一个节点
if( root.children.size() == 0 ){
System.out.println(rootPath);
return;
}
// 做传入的父节点有子节点,则递归遍历其子节点
for( int i=0; i<root.children.size(); i++ ){
Node child = root.children.get(i);
String childPath = rootPath+"-"+String.valueOf(child.val);
//递归处理其子节点
printPath_ergodicTree(child,childPath);
}
}
public static void main(String[] args){
Node root = new Node();
climbStaris_CreateTree(root,4);
printPath_ergodicTree(root,"start");
}
}
/**
* Description: 定义树的节点
* @author karl
*/class Node{
int val;
List<Node> children = new ArrayList<Node>();
Node(){}
Node( int val ){
this.val = val;
}
}
int one , two three ,N;
N = 10;
for( one = 1 ; one < N ; one++ ){
for( two = 1 ; two < N/2 ; two++) {
for( three = 1 ; three < N/3 ; three++)
if( one+(two*2)+(three*3) == N ){
System.out.println(one,two three);
}
}
}
}感觉大概是这样的吧,但是我觉得这个题的本意不是说要你输出每次上楼时,统计跨了一节台阶的次数,跨了两个节台阶的次数,跨了三个节台阶的次数,这样这个题目不是很难。题的本意应该是输出上楼时每步的情况,如对于one=1,two=2,three=3这种统计结果,其实又包含好几种方式,如第three可以先跨,也可以后跨。如果要把着样的可能性全输出就比较难了,代码怎么写,还没想出来。
= 2 (n = 2);
= 4 (n = 3);
= f(n-3) + f(n-2) + f(n-1) (n>3);
//startUp()传入楼梯数,因为测试,我输入了个5
System.out.println(startUp(5));
} public static int startUp(int n){
if(n ==3)
return 4;
if(n <3)
return n;
return startUp(n-1) + startUp(n-2) + startUp(n-3);
}
}
goUp(5);
}
public static void goUp(int n) {
ArrayList<String> al = new ArrayList<String>();
p(n,al);
}
private static void p(int n,List<String> al) {
if(n==0) {
for(String str:al)
System.out.print(str+" ");
System.out.println();
}
else if(n<0) {
return;
}
else {
int num = al.size();
al.add("1");
p(n-1,al);
al = al.subList(0, num);
al.add("2");
p(n-2,al);
al = al.subList(0, num);
al.add("3");
p(n-3,al);
al =al.subList(0, num);
}
}结果:1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
{public static final int N =10;public static void main(String[] args)
{int t_one;
int t_two;
int t_three;for(int i=0;i<=N;i++)
{t_one=i;
for(int j=0;j<=(N-t_one)/2;j++)
{t_two=j*2;
for(int k=0;k<=(N-t_one-t_two)/2;k++)
{t_three=k*3;
if((t_one+t_two+t_three)==N)
{System.out.println("一级步数:"+t_one+" 二级步数:"+t_two/2+" 三级步数"+t_three/3);
}
}
}
}
}
}
for(int j=0;j<=n/2;j++){
for(int k=0;j<=n/3;k++){
if(i+j*2+k*3==n){System.out.println(x+','+y+','+z)}
}
}
}
a=1;
b=2
c=4;
d = a + b + c;
a=b;
b=c;
c=d;
n--;
}
while(n>3){
a=1;
b=2
c=4;
d = a + b + c;
a=b;
b=c;
c=d;
n--;
}
{
public JavaTree left;
public JavaTree center;
public JavaTree right;
public boolean isLeaf = false;
public JavaTree father;
public Integer value;
public static ArrayList<JavaTree> leaves = new ArrayList<JavaTree>();
public JavaTree getLeft()
{
return left;
} public void setLeft(JavaTree left)
{
this.left = left;
} public JavaTree getCenter()
{
return center;
} public void setCenter(JavaTree center)
{
this.center = center;
} public JavaTree getRight()
{
return right;
} public void setRight(JavaTree right)
{
this.right = right;
} public Integer getValue()
{
return value;
} public void setValue(Integer value)
{
this.value = value;
}
public boolean isLeaf()
{
return isLeaf;
} public void setLeaf(boolean isLeaf)
{
this.isLeaf = isLeaf;
} public JavaTree getFather()
{
return father;
} public void setFather(JavaTree father)
{
this.father = father;
} public void addTree(int n, JavaTree fa)
{
if(n==0)
{
setLeaf(true);
leaves.add(fa);
return;
}
setValue(n);
if(fa!=null)
{
setFather(fa);
}
if(n>=3)
{
left = new JavaTree();
center = new JavaTree();
right = new JavaTree();
left.setValue(n-1);
left.addTree(n-1, this);
center.setValue(n-2);
center.addTree(n-2, this);
right.setValue(n-3);
right.addTree(n-3, this);
}else if(1<n&&n<=2)
{
left = new JavaTree();
center = new JavaTree();
left.setValue(n-1);
left.addTree(n-1, this);
center.setValue(n-2);
center.addTree(n-2, this);
}else if(n==1)
{
left = new JavaTree(); left.setValue(n-1);
left.addTree(n-1, this);
}
}
public void display()
{
System.out.print(getValue()+" ");
}
public void display(JavaTree leaf)
{
leaf.display();
if(leaf.getFather()!=null)
{
display(leaf.getFather());
}
}
}
package arithmetic;public class JavaTreeMain
{
public static void main(String[] args)
{
JavaTree root = new JavaTree();
root.addTree(10, null);
int count = 0;
for(JavaTree temp:JavaTree.leaves)
{
temp.display(temp);
System.out.println();
count++;
}
System.out.println("*****************"+count);
// JavaTree temp = JavaTree.leaves.get(0);
// temp.display(temp);
}
}
switch(level){
case 1:
return 1;
case 2:
return 2;
case 3:
return 4;
}
int count = 0;
for (int i = 0; i < level; i++) {
count += getCount(i);
}
return count;
}
{
int n=N;
int one=n;
int two=n/2;
int three=n/3;
System.out.println("一步\t二步\t三步");
for(int i=0;i<=one;i++)
for(int j=0;j<=two;j++)
for(int k=0;k<=three;k++)
{
if(i+j*2+k*3==n)
{
System.out.println(i+"\t"+j+"\t"+k);
}
if(j!=0 && i+j*2+k*3==n+1)
{
System.out.println(i+"\t"+j+"\t"+k);
}
if(k!=0 && i+j*2+k*3==n+2)
{
System.out.println(i+"\t"+j+"\t"+k);
}
}
}
public static void main(String[] args)
{
MyClass.floor(10);
}}
减掉的应该是这一步走得台阶数,但是走了一步,要加1
for(int i = 0 ;i<= 5;i++){
int j = 0;
for(;j<=5/2;j++){
int k = 0;
for(; k<=5/3 ;k++){
if(i+j*2+k*3==5){
System.out.println("i="+i+";j="+j+";k="+k);
}
}
}
}
}
/// 打印n步楼梯步数走法
/// </summary>
/// <param name="n"></param>
public void PrintZouFa(int n)
{
for (int i = 0; i <= n / 1; i++)//迈一步
{
for (int j = 0; j <= (n - i) / 2; j++)//迈两步
{
for (int k = 0; k <= (n-i-2*j)/3; k++)//迈三步
{
int total=i+2*j+3*k;
if (total == n)
{
System.out.println(i + " " + j + " "+ k);
}
}
}
}
}
难道我错了,不就是个递归吗?
public class ClimbStairs {
public static void main(String[] args) {
int n;
System.out.println(go(n));
}
public static int go(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
if(n == 3) return 4;
return go(n-1)+go(n-2)+go(n-3);
}
}
这句的意思是:
如果第一步走了一步还有n-1步要走,有go(n-1)种方法
如果第一步走了两步还有n-2步要走,有go(n-2)种方法
如果第一步走了三步还有n-3步要走,有go(n-3)种方法
{
if (n < 0)
{
return;
}
if (n == 0)
{
cout << step << endl;
}
step[i] = '1';
step[i + 1] = '\0';
stepN(n - 1, step, i + 1);
if (n > 1)
{
step[i] = '2';
step[i + 1] = '\0';
stepN(n - 2, step, i + 1);
}
if (n > 2)
{
step[i] = '3';
step[i + 1] = '\0';
stepN(n - 3, step, i + 1);
}
}int main()
{
char buf[11];
stepN(10, buf);
getchar();
}
答案:
1111111111
111111112
111111121
11111113
111111211
11111122
11111131
111112111
11111212
11111221
1111123
11111311
1111132
111121111
11112112
11112121
1111213
11112211
1111222
1111231
11113111
1111312
1111321
111133
111211111
11121112
11121121
1112113
11121211
1112122
1112131
11122111
1112212
1112221
111223
1112311
111232
11131111
1113112
1113121
111313
1113211
111322
111331
112111111
11211112
11211121
1121113
11211211
1121122
1121131
11212111
1121212
1121221
112123
1121311
112132
11221111
1122112
1122121
112213
1122211
112222
112231
1123111
112312
112321
11233
11311111
1131112
1131121
113113
1131211
113122
113131
1132111
113212
113221
11323
113311
11332
121111111
12111112
12111121
1211113
12111211
1211122
1211131
12112111
1211212
1211221
121123
1211311
121132
12121111
1212112
1212121
121213
1212211
121222
121231
1213111
121312
121321
12133
12211111
1221112
1221121
122113
1221211
122122
122131
1222111
122212
122221
12223
122311
12232
1231111
123112
123121
12313
123211
12322
12331
13111111
1311112
1311121
131113
1311211
131122
131131
1312111
131212
131221
13123
131311
13132
1321111
132112
132121
13213
132211
13222
13231
133111
13312
13321
1333
211111111
21111112
21111121
2111113
21111211
2111122
2111131
21112111
2111212
2111221
211123
2111311
211132
21121111
2112112
2112121
211213
2112211
211222
211231
2113111
211312
211321
21133
21211111
2121112
2121121
212113
2121211
212122
212131
2122111
212212
212221
21223
212311
21232
2131111
213112
213121
21313
213211
21322
21331
22111111
2211112
2211121
221113
2211211
221122
221131
2212111
221212
221221
22123
221311
22132
2221111
222112
222121
22213
222211
22222
22231
223111
22312
22321
2233
2311111
231112
231121
23113
231211
23122
23131
232111
23212
23221
2323
23311
2332
31111111
3111112
3111121
311113
3111211
311122
311131
3112111
311212
311221
31123
311311
31132
3121111
312112
312121
31213
312211
31222
31231
313111
31312
31321
3133
3211111
321112
321121
32113
321211
32122
32131
322111
32212
32221
3223
32311
3232
331111
33112
33121
3313
33211
3322
3331
{
int result[3] = {1,2 ,4};
if(n < 4)
return result[n];
else
return GetResult(n - 1) + GetResult(n - 2)-GetResult(n-3);
}
// 每一步能走的台阶数
private static final int s1 = 1;
private static final int s2 = 2;
private static final int s3 = 3;
//存储台阶走法List
private static List<int[]> methodList = new ArrayList<int[]>();
//主方法,参数(台阶数)大于等于 3 即可
private static void step(int n) { for (int i = 1; i <= 3; i++) {
int[] intArray = new int[n];
intArray[0] = i;
methodList.add(intArray);
} int arrayCount = 3;
int completeCount = 0;
int currentListSize = 0; while (completeCount != methodList.size()) {
currentListSize = methodList.size();
for (int i = 0; i < methodList.size(); i++) {
if (i == currentListSize) {
break;
}
int[] intTemp = methodList.get(i); if (sum(intTemp) + s3 <= n) { int[] itt1 = new int[n];
System.arraycopy(intTemp, 0, itt1, 0, n);
itt1[site(itt1)] = s3;
methodList.add(arrayCount, itt1);
arrayCount++;
int[] itt2 = new int[n];
System.arraycopy(intTemp, 0, itt2, 0, n);
itt2[site(itt2)] = s2;
methodList.add(arrayCount, itt2);
arrayCount++;
intTemp[site(intTemp)] = s1;
} else if (sum(intTemp) + s2 <= n) {
int[] itt3 = new int[n];
System.arraycopy(intTemp, 0, itt3, 0, n);
itt3[site(itt3)] = s2;
methodList.add(arrayCount, itt3);
arrayCount++;
intTemp[site(intTemp)] = s1;
} else if (sum(intTemp) + s1 <= n) {
intTemp[site(intTemp)] = s1;
} }
completeCount = 0;
for (int i = 0; i < methodList.size(); i++) {
int[] intTemp = methodList.get(i);
if (sum(intTemp) == n) {
completeCount++;
}
}
}
}
//目前走了多少台阶
private static int sum(int[] intParam) {
int intTotal = 0;
for (int j = 0; j < intParam.length; j++) {
if (intParam[j] > 0) {
intTotal += intParam[j];
}
}
return intTotal;
}
//目前走到第几步
private static int site(int[] intParam) {
int site = 0;
for (int j = 0; j < intParam.length; j++) {
if (intParam[j] == 0) {
site = j;
break;
}
}
return site;
}
public class ClimbStairs {
public static ArrayList<String> stepList = new ArrayList<String>();
public static void main(String[] args) {
int n = 10;
System.out.println(go(n,""));
showListStep();
}
public static int go(int n,String left) {
if(n == 1)
{
stepList.add(left+"-1");
return 1;
}
if(n == 2)
{
stepList.add(left+"-1-1");
stepList.add(left+"-2");
return 2;
}
if(n == 3)
{
stepList.add(left+"-1-1-1");
stepList.add(left+"-2-1");
stepList.add(left+"-1-2");
stepList.add(left+"-3");
return 4;
}
return go(n-1,left+"-1")+go(n-2,left+"-2")+go(n-3,left+"-3");
}
public static void showListStep()
{
for(int i=0; i<stepList.size();i++)
{
System.out.println(stepList.get(i));
}
}
}
import java.util.*;public class Main {
int MAX = 10000000, n, method;
int[] step = new int[MAX];
public static void main(String args[]) {
new Main().run();
}
void run() {
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
n = in.nextInt();
method = 0;
goUp(0,0);
System.out.println("Total case:"+method);
}
}
void goUp(int curFloor,int curStep)
{
if(curFloor == n) {
method++;
System.out.println("Case "+method+":");
for(int i=0; i<curStep; i++) {
System.out.print(step[i]+" ");
}
System.out.print("\n");
return;
}
if(curFloor+1 <= n) { //尝试向上走1步
step[curStep] = 1;
goUp(curFloor+1,curStep+1);
}
if(curFloor+2 <= n) { //尝试向上走2步
step[curStep] = 2;
goUp(curFloor+2,curStep+1);
}
if(curFloor+3 <= n) { //尝试向上走3步
step[curStep] = 3;
goUp(curFloor+3,curStep+1);
}
}
}
1,递归实现(C++):
int calcSteps(int n)
{
assert(n > 0);
if (n==1) return 1;
if (n==2) return 3;
if (n==3) return 4; return calcSteps(n-1) + calcSteps(n-2) + calcSteps(n-3);
}2,迭代实现(C++):
int calcSteps(int n)
{
assert(n > 0);
int n1 = 1;
int n2 = 3;
int n3 = 4;
if (n==1) return n1;
if (n==2) return n2;
if (n==3) return n3; int ret;
for (int i = 4; i <= n; i++)
{
ret = n1 + n2 + n3;
n1 = n2;
n2 = n3;
n3 = ret;
} return ret;
}
* @param args
*/
public static void main(String[] args) {
int x ;
int y ;
int z ;
int n =9 ;
for(x=0;x<n;x++){
for(y=0;y<n/2;y++){
for(z=0;z<n/3;z++){
if(x+2*y+3*z==n){
System.out.println("第一步-->"+x+"第二步-->"+y+"第三部-->"+z);
}
}
}
} }} 这种应该是最没文化的了。
package sercli;public class Cal { /**
* @测试一下
*/
public static void main(String[] args) {
Cal cc=new Cal();
int answer1=cc.getNum(1);
int answer2=cc.getNum(2);
int answer3=cc.getNum(3);
int answer4=cc.getNum(4);
int answer5=cc.getNum(5);
int answer6=cc.getNum(6);
int answer7=cc.getNum(7);
System.out.println("answer1---"+answer1);
System.out.println("answer2---"+answer2);
System.out.println("answer3---"+answer3);
System.out.println("answer4---"+answer4);
System.out.println("answer5---"+answer5);
System.out.println("answer6---"+answer6);
System.out.println("answer7---"+answer7);
}
public int getNum(int stairs){
if((stairs==0)||(stairs<0)){
return 0;
}else if(stairs==1){
return 1;
}else if(stairs==2){
return 2;
}else if(stairs==3){
return 5;
}else{
return getNum(stairs-1)+getNum(stairs-2)+getNum(stairs-3);
}
}}输出:
answer1---1
answer2---2
answer3---5
answer4---8
answer5---15
answer6---28
answer7---51
* @测试一下
*/
public static void main(String[] args) {
Cal cc=new Cal();
int answer1=cc.getNum(1);
int answer2=cc.getNum(2);
int answer3=cc.getNum(3);
int answer4=cc.getNum(4);
int answer5=cc.getNum(5);
int answer6=cc.getNum(6);
int answer7=cc.getNum(7);
System.out.println("answer1---"+answer1);
System.out.println("answer2---"+answer2);
System.out.println("answer3---"+answer3);
System.out.println("answer4---"+answer4);
System.out.println("answer5---"+answer5);
System.out.println("answer6---"+answer6);
System.out.println("answer7---"+answer7);
}
public int getNum(int stairs){
if((stairs==0)||(stairs<0)){
return 0;
}else if(stairs==1){
return 1;
}else if(stairs==2){
return 2;
}else if(stairs==3){
return 4;
}else{
return getNum(stairs-1)+getNum(stairs-2)+getNum(stairs-3);
}
}}输出:answer1---1
answer2---2
answer3---4
answer4---7
answer5---13
answer6---24
answer7---44
即 for(int x=0;x<n;x++)
```{
for(int y=0;y<n/2;y++)
{
for(int z=0;z<n/3;z++)
{
if(x+y+z==n)
{
cout<<x<<y<<z
}
}
}
}
所有的递归问题都能用while循环解决,所以最优算法就是用while循环做,这样所有的问题都能在一个方法栈中进行,不过思考过程很复杂...唉..偷懒了..
那么,
如果第一次走一步,有f(n-1)种走法
如果第一次走两步,有f(n-2)种走法
如果第一次走散步,有f(n-3)种走法
总共就是f(n-1)+f(n-2)+f(n-3)
13楼,高人啊,代码清晰,构建合理,出题人的原意大概要的就是这个答案吧!
佩服!
public class A {
private static final int allstep = 4; //阶梯总数
public static void main(String[] args) {
int step[] = new int[allstep]; //路径数组,step[i]表示第i+1步走了几级楼梯,
//如step[0]=2表示第1步走了2级。
for (int i = 0; i < allstep; i++)
step[i] = 0;
foo(step, 0, 1, -1); //第一步走1级台阶
foo(step, 0, 2, -1); //第一步走2级台阶
foo(step, 0, 3, -1); //第一步走3级台阶
}
/** 此函数表示每走一步的动作过程。a[]存储走过的路径,steped表示已经走过的台阶总数,
* go表示这一步将要走几级台阶,index表示已经走了几步
*/
private static void foo(int a[], int steped, int go, int index) {
if (steped+go < allstep) { //如果已经走过的台阶数和这一步将要走的台阶数之和小于
//总台阶数
index += 1; //步数增1
a[index] = go; //将此步走过的台阶数存入路径中
//递归走下一步
foo(a, steped+go, 1, index);
foo(a, steped+go, 2, index);
foo(a, steped+go, 3, index);
} else if (steped+go == allstep) { //如果已经走过的台阶数和这一步将要走的台阶数之
//和等于总台阶数,表示走完,输出路径
index += 1;
a[index] = go;
//输出路径
StringBuffer out = new StringBuffer("路径:");
for (int i = 0; i <= index; i++)
out.append(a[i]+" ");
System.out.println(out);
} else {
}
}
}//台阶总数为4时的输出结果:
路径:1 1 2
路径:1 2 1
路径:1 3
路径:2 1 1
路径:2 2
路径:3 1
第一次发帖,请各路大神指正
import java.util.List;public class ClimbStairs { /**
* @param args
*/
public static void main(String[] args) {
List<Integer> Steps = new ArrayList<Integer>();
Climb(Steps, 6); } public static void Climb(List<Integer> Steps,int length){
if(length==1){
Steps.add(1);
System.out.println(Steps.toString());
}else if(length==2){
List<Integer> temp = new ArrayList<Integer>();
temp.addAll(Steps);
Steps.add(1);
Steps.add(1);
System.out.println(Steps.toString());
temp.add(2);
System.out.println(temp.toString());
}else if(length==3){
List<Integer> temp1 = new ArrayList<Integer>();
temp1.addAll(Steps);
List<Integer> temp2 = new ArrayList<Integer>();
temp2.addAll(Steps);
List<Integer> temp3 = new ArrayList<Integer>();
temp3.addAll(Steps);
Steps.add(1);
Steps.add(1);
Steps.add(1);
System.out.println(Steps.toString());
temp1.add(2);
temp1.add(1);
System.out.println(temp1.toString());
temp2.add(1);
temp2.add(2);
System.out.println(temp2.toString());
temp3.add(3);
System.out.println(temp3.toString());
}else{
List<Integer> temp1 = new ArrayList<Integer>();
temp1.addAll(Steps);
List<Integer> temp2 = new ArrayList<Integer>();
temp2.addAll(Steps);
List<Integer> temp3 = new ArrayList<Integer>();
temp3.addAll(Steps);
temp1.add(1);
Climb(temp1,length-1);
temp2.add(2);
Climb(temp2,length-2);
temp3.add(3);
Climb(temp3,length-3);
}
}
}
static int maxStepLen = 3;// 最大步长
static int count = 0; static void printNode(List<Integer> path, int from) { for (int length = 1; length <= maxStepLen; length++) {// 步长都可以是1,2,3 List<Integer> copyPath = new ArrayList<Integer>(path);// 将之前的路径复制 copyPath.add(length);// 步长加入path
int nowFrom = from + length;// 现在的位置 if (nowFrom == 10) {
count++;
System.out.println(path.toString());
break;
}
printNode(copyPath, nowFrom);
}
}
public static void main(String[] args) {
printNode(new ArrayList<Integer>(), 0);
System.out.println(count);
}