爬楼梯问题

小鱼儿 2022-08-05 01:17 160阅读 0赞

还记得当年找实习单位的时候，小米还有百度面试官问了这样同样的问题，只不过问的方式不一样，说到底就是这个递归问题，也可以说就一斐波那契数列：

问题描述：有n个台阶，每次只能走一阶或两阶，总共有多少种走法？

查了一下资料，可以归结为三种方法，递归，迭代，穷举。

方法1：递归

走到第n个台阶的时候只能是从前面的台阶走上来的，如果前一次他走了1步，则第n的时候他的走法为n-1步时的走法，如果前一次他走了两步，则第n的时候他的走法为n-2步的走法，总的走法就是n-1和n-2步中的总和。

#include<stdio.h>
    long int fun(int n)
    {
    if(n==1)   return 1;
    if(n==2)	return 2;
    if(n==3)	return 4;
    else return fun(n-1)+fun(n-2)+fun(n-3);
    }
    void main()
    {
    printf("%d",fun(100));
    }

方法2：迭代

由于递归方法可能迭代深度过大，时间太长，导致没有结果，所以用迭代来解决

#include<stdio.h>
    
    double fun(int n) {
    	if (n == 1)
    		return 1;
    	if (n == 2)
    		return 2;
    	if (n == 3)
    		return 4;
    	else
    		return fun(n - 1) + fun(n - 2) + fun(n - 3);
    }
    int main() {
    
    	double a[100];
    
    	a[0] = 1;
    	a[1] = 2;
    	a[2] = 4;
    
    	for (int x = 3; x < 100; x++) {
    		a[x] = a[x - 1] + a[x - 2] + a[x - 3];
    	}
    
    	for (int i = 0; i < 100; i++) {
    		printf("Level Amount--->%d\t", (i + 1));
    		printf("Sol:1--->%e\t", fun(i + 1));
    		printf("Sol:2--->%e\n", a[i]);
    
    	}
    
    	return 0;
    }

方法3.穷举法

\#include <iostream>  
using namespace std;  
  
  
int CountMethod(int n)  
\{  
int i, j, k;  
int count = 0;  
for (i = 0; i <= n/3; i++)  
for (j = 0; j <= n/2; j++)  
for (k = 0; k <= n; k++)  
if (3\*i + 2\*j + k == n)  
count++;//这里不是++；应该是(100!)/(j!)\*((100-j)!)/(k!);  
  
return count;  
  
\}  
  
  
int main()  
\{  
int count = CountMethod(100);  
cout << count << endl;  
return 0;  
\}