一个很多人都做不出来的面试题

Question

题目：一楼梯有n阶，一个人每次可以上一个台阶，也可以上2个台阶，求出这个人上楼梯的走法
要求：5分钟内写出代码！
提示：用递归法，或者不用递归法
望高手来show一下自己的算法～

Answer 1

f(n) = f(n-1) + f(n-2)
f(1) = 1
f(2) = 2如果用Haskell语言来实现，上面就是源代码了。

Answer 2

楼主别小瞧了中国人，
8过偶连调试用了10分钟
#include <stdio.h>
#include <string.h>void func(int rest, char* prev)
{
    if ( !rest )
    {
printf("%s\n", prev);
return;
}
 if ( rest - 1 >= 0)
     {
char output[100];
strcpy(output, prev);
 strcat(output, " 1");
         func(rest-1, output);
     }     if ( rest - 2 >= 0)
     {
 char output[100];
strcpy(output, prev);
 strcat(output, " 2");
         func(rest-2, output);
 }
}int main()
{
func(6, "");
}

Answer 3

public void count(int n){
   if(n<1) {
      throw new IllegalArgumentExcetion();
   }
   else if(n==1){
       return 1;
   }
   else if(n==2) {
       return 2;
   }
   else {
        return count(n-1)+count(n-2);
   }
}

Answer 4

楼上的两位都实现了：
f(n) = f(n-1) + f(n-2)
f(1) = 1
f(2) = 2一个是C,一个是Java。结果是2^（n-1). 并不是正确结果。
如：n = 3 时，结论是3而不是4

Answer 5

当n＝3的时候是三个台阶，怎么可能有4种走法呢。n＝3的时候是3没有错！
==================================================================所以:结果是2^（n-1). 并不是正确结果。

Answer 6

也就是说：
f(n) = f(n-1) + f(n-2)
f(1) = 1
f(2) = 2
是错误的。下面的两种实现也是不对题的！

Answer 7

package test;public class Step {
static int stepCount=0;
static int steps[] = new int[100];
public static void step(int n){
if(n==0) {
return;
}
if(n==1){
steps[stepCount++]=1;
printResult();

return;
}
if(n==2){
steps[stepCount++]=1;
steps[stepCount++]=1;

printResult();

stepCount-=2;
steps[stepCount++]=2;

printResult();

return;
}

int u=stepCount;
steps[stepCount++]=1;
step(n-1);

stepCount = u;
steps[stepCount++]=2;
step(n-2);
}
private static void printResult() {
int i=0;
while(i<stepCount)
System.out.print(steps[i++]);
System.out.println();
}
public static void main(String[] args){
step(6);
}
}

Answer 8

f(0)=f(1)=1;
f(2)=2;if(n>2)
f(n)=f(n-2)*2+f(n+3);
就可以实现的，没有问题的

Answer 9

f(n) = f(n-1) + f(n-2)
f(1) = 1
f(2) = 2
是没有问题的！

Answer 10

f(n) = f(n-1) + f(n-2)
f(1) = 1
f(2) = 2如果用Haskell语言来实现，上面就是源代码了。
---------------------------------------------完全赞同！！！

Answer 11

int s[20];
void stair(int height, int index)
{
   if (height>=2) { s[++index] = 2; height -= 2; stair(height,index);}
   else
   {  if (height ==1 ) { s[++index] = 1; height = 0; }
      for(int j = 1; j<=index; j++)
      printf(" %d",s[j]); printf("\n");
   }
   if (s[index] == 2)
   {  s[index] = 1; height++; stair(height,index); }}
main()
{
   
   stair(7,0);
}

Answer 12

f(n) = f(n-1) + f(n-2)
f(1) = 1
f(2) = 2
--------------------------------------
通项：
     
          1/2           1/2             1/2           1/2
     3 + 5         1 + 5     n     5 - 5         1 - 5      n
f(n)=-----------*(---------)  +   ----------* ( -----------) 
            1/2 
      5 + 5           2              10             2
          
用特征根法就可以求，化简后很简单，你不妨试试

Answer 13

//输出各种走法的递归算法
/*
public class Step
{
private int n,stepNums;
private int [] steps;

public Step(int i)
{
n=i;stepNums=0;
steps=new int[i]; System.out.println("Stairsteps:"+n);
process(0,0);
System.out.println("TotalNums:"+stepNums);
}
private void printAll(int j)//打印走法
{
System.out.print("Case "+stepNums+": ");
for (int i=0;i<j;i++) System.out.print(steps[i]+"   ");
System.out.println();
}
private void process(int i,int j)//递归
{
if (i>=n)
{
if (i==n)
{
stepNums++;
printAll(j);
}
return;
}
else
{
steps[j]=1;process(i+1,j+1);
steps[j]=2;process(i+2,j+1);
}
}

public static void main(String args[])
{
new Step(5);
}
}*///只输出总数递归算法
public class Step
{
private int n,stepNums;

public Step(int i)
{
n=i;stepNums=0; System.out.println("Stairsteps:"+n);
process(0);
System.out.println("TotalNums:"+stepNums);
}
private void process(int i)//递归
{
if (i>=n)
{
if (i==n) stepNums++;
return;
}
else
{
process(i+1);
process(i+2);
}
}

public static void main(String args[])
{
new Step(3);
}
}===================================================
这个题目其实很简单,递归的主要算法就是:
private void process(int i)//递归
{
if (i>=n)
{
if (i==n) stepNums++;
return;
}
else
{
process(i+1);
process(i+2);
}
}

Answer 14

huntsky(何) 的方法好！逻辑清晰，便于扩展！
学习。

Answer 15

下面是扩展成“一楼梯有n阶，一个人每次可以上一个台阶，也可以上2个台阶，还可以上3个台阶，求出这个人上楼梯的走法”的例子：
public class Steps {
private int StairsNum, stepNums;
private int walk[] = {1, 2, 3};

public Steps(int i)
{
StairsNum=i;
stepNums=0; System.out.println("Stairs Number: " + StairsNum);
process(0);
System.out.println("Walk methods Number: " + stepNums + "\r\n");
}
private void process(int n)
{
if (n >= StairsNum)
{
if (n == StairsNum) stepNums++;
return;
}
else
{
for(int i = 0; i < walk.length; i++){
process(n + walk[i]);
}
}
}

public static void main(String[] args){
new Steps(1);
new Steps(2);
new Steps(3);
new Steps(4);
new Steps(5);
new Steps(6);
new Steps(7);
new Steps(8);
}
}

Answer 16

用特征根法就可以求，化简后很简单。
－－－－－－－－－－－－－－－－－
对于“一楼梯有n阶，一个人每次可以上一个台阶，也可以上2个台阶，求出这个人上楼梯的走法”适用，
但对于“一楼梯有n阶，一个人每次可以上一个台阶，也可以上3个台阶，求出这个人上楼梯的走法”
就不那么简单了。在上面的扩展程序中只要修改成private int walks[] = {1, 3};即可。

Answer 17

TO: rower203(华仔) 仔细看看我的代码，偶的很正确啊。

Answer 18

#include <stdio.h>
#include <string.h>void func(int rest, char* prev)
{
    if ( !rest )
    {
printf("%s\n", prev);  //打印当前的组合
return;
    }
    
    if ( rest - 1 >= 0)    //走1层
    {
                   char output[100]; //换成封装过的String类型最佳，为防栈overflow
strcpy(output, prev);
 strcat(output, " 1");
         func(rest-1, output);  // 走1步时候的分之判断
     }     if ( rest - 2 >= 0)  //走两层
     {
 char output[100];  
strcpy(output, prev);
 strcat(output, " 2");
         func(rest-2, output);  // 走两步时候的分之判断
 }
}int main()
{
func(6, ""); //
}

Answer 19

import java.util.Random;
public class test1 {
    Random r = new Random();
    public void go(int n,int step)
    {
        int totle =n;
        if(totle>=2)
        {
            int s = r.nextInt(2);
            if(s==0)
                
                step =1;
            else
                step =2;
            
            totle = totle - step;
           
            
           System.out.println("步数="+(s+1));
            
           System.out.println("剩余楼梯="+totle);
            go(totle,step);
        }
        else if(totle>1)
        {
            go(1,1);
        }
        else if(totle==0)
            return;
    }
public static void main(String[] argv)
{
    
    test1 t =new test1();
    t.go(10,2);
}
}

Answer 20

int walk(int n){
  if(n =< 2)
   return n;
  if(n>2)
   return walk(n-1)+walk(n-2);}

Answer 21

int walk(int n){
  if(n =< 2)
   return n;
  if(n>2)
   return walk(n-1)+walk(n-2);}回复人： chen_2001(刀锋) 为正解