腾讯面试题：走到50台阶的可能数(台阶可以一次走一阶或者二阶)，三种方式实现

Bertha 。 2022-08-07 11:51 153阅读 0赞

//腾讯面试题，有50个台阶，一次走一步或者两步，有多少种可能  
//走到50阶的可能是走到49阶的可能加上走上走到48的可能  
  
//分析  
/\*  
    台阶数   可能数  
    1            1            直接走一个台阶就ok  
    2            2            走1 1或者直接走2个台阶  
    3            3            111,21,12  
    4            5            1111,112,121,22,211          
    5            8            11111,1112,1121,1211,2111,122,221,212  
    ...            ...            ...  
    50        走到50阶可以是从48阶走到50阶，也可以是从49阶走到50阶，那么总数就是走到48阶的加上走到49阶的和  
\*/  
  
/\*  
    走到台阶4的可能数量是：从2台阶直接到4台阶，或者从3台阶到 4台阶 ，  
    由于到2台阶的可能数是2种，到3台阶的可能数是3 ，加起来就是5，即等于走到4台阶的可能数  
    那么走到50台阶的可能就等于走到48的可能加走到49的可能，（走到50阶，要么从48到50，要么从49到50）  
    任何循环都可以转换成递归，但是 递归不一定能转换成循环

\*/

#include<stdio.h>
    #include<stdlib.h>
     //递归实现 
    double tencent(int n)//要返回double类型，不然溢出 
    {
    	if(n==1)
    	{
    		return 1.0;//return 1 不能这样写，溢出 
    	}
    	else if(n==2)
    	{
    		return 2.0;//return 2 不能这样写，溢出 
    	}
    	else
    	{
    		return tencent(n-1)+tencent(n-2);
    	}
    } 
    //for循环实现
    int For(int n)
    {
    	int n1 = 1;
    	int n2 = 2;
    	int n3;
    	for(int i=0;i<n;i++)
    	{
    		n3 = n1+n2;
    		n1=n2;//向前移动,n1等于当前n2的值， 
    		n2=n3;//向前移动,n2等于当前n3的值，
    	}
    	return n3;
    } 
    //数组实现
    int Array(int n) 
    {
    	int a[50];
    	a[0] = 1;
    	a[1] = 2;
    	for(int i=2;i<n;i++)//从2开始循环 
    	{
    		a[i] = a[i-1]+a[i-2];
    	}
    	return a[n-1];
    }
    int main()
    {
    	int n;
    	scanf("%d",&n);//假设输入的数字是12 
    	printf("递归实现:走到%d阶的可能数是:%f\n",n,tencent(n));//如果是50则溢出大约10分钟才行
    	printf("For 实现:走到%d阶的可能数是:%d\n",n,For(n-2));//for的10等价于12,n1,n2都被忽略,num从3开始
    	printf("数组实现:走到%d阶的可能数是:%d\n",n,Array(n));
    	return 0;
    }

注：腾讯面试说的是传入50阶，但是要求出50阶的可能需要10分钟，你要现场做出  
               来写出算法就可以了。50的话绝对会溢出，那么就只能用double类型了 。

![Center][]

[Center]: /images/20220805/bdd11e2f52154759b6a8083985f7e5e1.png