华为面试题:1000阶台阶,如果每次只能走1步,2步或3步,问:有多少种走法?(理解递归算法) |
您所在的位置:网站首页 › 华为手机一共有多少种型号呢 › 华为面试题:1000阶台阶,如果每次只能走1步,2步或3步,问:有多少种走法?(理解递归算法) |
作者:非妃是公主 专栏:《笔记》《C++》 个性签:顺境不惰,逆境不馁,以心制境,万事可成。——曾国藩 转载请标明原文链接:https://blog.csdn.net/myf_666/article/details/114113541 前几天和家人聊天,无意间听到了这道题,据说是花厂的面试题,不知真假,不过今天倒是用C++实现了一下; 乍一看,一千阶台阶可能有些懵,但是,不要慌计算机就是重复简单动作的一个工具。 如果我现在将它改为1阶,还未上幼儿园的小朋友可能会毫不犹豫地说有1种走法; 如果我将它改为2阶,可能稍微上过几天幼儿园的同学就会说,有两种走法,我们可以一下走两阶,或者分两次走,每次走一阶; 如果我将它改为3阶,那么一年级的小学生可能需要稍加列举一下才能分析出到底有多少种走法,请看下面的代码片: 1 1 1 1 2 2 1 3细心的你会发现,只有4种是嘛? 是的,没错,正是四种; 那么,我们继续,如果我将题目改为4阶台阶呢?我们还需要一一例举吗? NO,那样的话我们就需要到一年级去回炉重造了; 4阶,相当于我们一次走一步的走法(1)种数(乘上)走3阶的走法种数,走两步的走法(1)种数(乘上)走2阶走法种数,走三步的走法(1)种数(乘上)走1阶的走法种数;(这里走两步不能包含走一步的走法,走三步的走法不能包含走两步的走法。) 现在我们的问题就清楚了,我们采用了递归的方法,不断地调用线程,来解决问题,这就是一个简单的所谓的算法; 算法,听起来很高深,其实就是将我们人类的多姿多彩的思维转化成为(抽象成)计算机可以执行的语言就好了,无非就是简单机械的判断和存储;当然这其中可能会用到一些数学的方法; 下面附上一个21行的简单的代码: #include using namespace std; int number(int n) { if (n == 1) { return 1; } else if (n == 2) { return 2; } else if (n == 3) { return 4; } else { return number(n - 1) + number(n - 2) + number(n - 3); } } int main() { int n = 1000; cin >> n;//输入任意的台阶数,当然要考虑到个人计算机的算力,好比1000,一般的轻薄本或商务本的算力肯定是需要很久时间的,可以睡前开始,早晨起来后看结果,嘿嘿 cout |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |