迅雷笔试题目 java爬楼梯

welldoneAAA 2011-10-14 10:47:15

一个人爬楼梯，一步可以迈一级，二级，三级台阶，如果楼梯有N级，编写程序，输出所有走法。java实现。

...全文

4607 97 打赏收藏转发到动态举报

写回复

用AI写文章

97 条回复

切换为时间正序

请发表友善的回复…

发表回复

wang_hao_long 2012-10-22

打赏
举报





static int to = 10;// 台阶数

	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);

	}

liu1989fei2008 2012-10-14

打赏
举报

自己试了下，没用什么特殊的算法，也不复杂，就是个递归，感觉好搓的样子



package everydaydo;



import java.util.ArrayList;

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);

		}

	}

}

guan0005 2012-10-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

第一次发帖，请各路大神指正

crazyyujie 2011-10-25

打赏
举报

13L，代码风格不错啊，看的舒服多了
57L，可以在补充下

lzo_ozl 2011-10-21

打赏
举报

mark mark

huhualinghuhualing 2011-10-21

打赏
举报

很多大虾啊，学习，学习。

渔丶 2011-10-20

打赏
举报

假设有方法f(),该方法用来计算N阶台阶共有多少种走法
那么，
如果第一次走一步，有f(n-1)种走法
如果第一次走两步，有f(n-2)种走法
如果第一次走散步，有f(n-3)种走法
总共就是f(n-1)+f(n-2)+f(n-3)

13楼，高人啊，代码清晰，构建合理，出题人的原意大概要的就是这个答案吧！
佩服！

karl1235 2011-10-20

打赏
举报

[Quote=引用 88 楼 mason520 的回复:]
13楼的算法不错，但是数字大些就会内存溢出，所以应该不是最优算法。有没有更好的？
[/Quote]

所有的递归问题都能用while循环解决,所以最优算法就是用while循环做,这样所有的问题都能在一个方法栈中进行,不过思考过程很复杂...唉..偷懒了..

zha_zi 2011-10-20

打赏
举报

1x+2y+3z=n 的所有解
即 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
}
}
}
}

mason520 2011-10-20

打赏
举报

13楼的算法不错，但是数字大些就会内存溢出，所以应该不是最优算法。有没有更好的？
[Quote=引用 13 楼 qiaoyupeng 的回复:]
呵呵,工作后很少做这种题,早上起来做个也挺有意思的.这种题主要是要实际情景抽象成编程问题,考察建模能力

下面是我的代码,就是递归,如果有朋友用while循环做,我也参考参考

Java code

/*
* To change this template, choose Tools | Templates and open the template in
* ……
[/Quote]

索隆 2011-10-19

打赏
举报

改一下：



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 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

索隆 2011-10-19

打赏
举报



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

yzw124 2011-10-19

打赏
举报

#62楼正解想法完全一致

买房动力十足 2011-10-19

打赏
举报

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);

					 }

				 }

			 }

		 }



	}



}

这种应该是最没文化的了。。。。

xftmf_2008 2011-10-19

打赏
举报

学习了

PigiRoNs 2011-10-19

打赏
举报

忘了java怎么写了，简单写个C++的，这个在于算法怎么写，用啥语言都差不多吧
[Quote=引用 67 楼 martin_jay 的回复:]

#62的，java社区，你搞个c出来干什么？
[/Quote]

zzy3696 2011-10-19

打赏
举报

学习学习

涛涛_2009 2011-10-18

打赏
举报

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)种方法

Martin_Jay 2011-10-18

打赏
举报

#62的，java社区，你搞个c出来干什么？

涛涛_2009 2011-10-18

打赏
举报

啊，不用这么麻烦啊
难道我错了，不就是个递归吗？

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);

	}

}