爬楼梯问题

小鱼儿 2022-08-05 01:17 190阅读 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;  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，190人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java解决爬楼梯问题

Java解决爬楼梯问题 01 题目假设你正在爬楼梯。需要 `n` 阶你才能到达楼顶。每次你可以爬 `1` 或 `2` 个台阶。你有多少种不同的方法可以爬到楼顶

曾经终败给现在/ 2024年02月05日 20:49/ 0 赞/ 53 阅读

相关爬楼梯

爬楼梯 1、参考资料 https://leetcode-cn.com/problems/climbing-stairs/ https://segmentfault

╰+哭是因爲堅強的太久メ/ 2022年12月04日 07:36/ 0 赞/ 138 阅读

相关 70. 爬楼梯

> 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 > > 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ > > 注意：给定 n 是一个正整数。

梦里梦外;/ 2022年10月08日 15:20/ 0 赞/ 196 阅读

相关 70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入

超、凢脫俗/ 2022年10月07日 07:49/ 0 赞/ 198 阅读

相关爬楼梯问题

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

小鱼儿/ 2022年08月05日 01:17/ 0 赞/ 191 阅读

相关回溯解决爬楼梯问题

1.问题描述每次爬楼梯有每次可跨1,2,3步，爬上一个N阶楼梯有多少种方式，打印出每种方式。 2.源代码 // ConsoleApplication6.

灰太狼/ 2022年08月04日 10:52/ 0 赞/ 161 阅读

相关爬楼梯

如果每次可以上一级台阶或者两级台阶，那么上 n 级台阶一共有多少种方案？ \include<stdio.h> int main() \{ int n; int

冷不防/ 2022年07月14日 09:09/ 0 赞/ 409 阅读

相关爬楼梯

爬楼梯 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Problem Desc

墨蓝/ 2022年07月12日 12:36/ 0 赞/ 223 阅读

相关爬楼梯

1.知识点：递推 2.题意：如果每次可以上一级台阶或者两级台阶，那么上 n 级台阶一共有多少种方案 3.递推关系方程：a\[i\] = a\[i-1\] + a\[i-

傷城~/ 2022年05月30日 08:47/ 0 赞/ 215 阅读

相关爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：

小鱼儿/ 2022年02月27日 15:44/ 0 赞/ 255 阅读