复盘PHP经典问题解决过程:上台阶问题

简介: 题目有个人想上一个50级的台阶,每次只能迈1级或者迈2级台阶,问:这个人有多少种方法可以把台阶走完?例如:总共3级台阶,可以先迈1级再迈2级,或者先迈2级再迈1级,或者迈3次1级总共3中方式。

题目

有个人想上一个50级的台阶,每次只能迈1级或者迈2级台阶,问:这个人有多少种方法可以把台阶走完?例如:总共3级台阶,可以先迈1级再迈2级,或者先迈2级再迈1级,或者迈3次1级总共3中方式。

心路历程

这个题目我刚看到的时候觉得很有意思,值得思考一下,也和同学讨论过思路,并没有直接去网上找答案,觉得那样的话就浪费了,所以自己先尝试着解了。

说这么多是希望大家也不要直接去看解答,因为看完之后一个星期也就忘了。可以先收藏一手,自己去试试然后再回来看,我会把我自己解的思路和正解都放在这篇文章里。

思路step1:

从初中生的思路来看,第一个能想到的方法肯定是一个二元方程,也就是x+2y=50,其中x代表迈1步,y代表迈2步,无论怎么迈总共50级台阶。

接下来的问题就是求这个方程解的数量(不是某一个解),x+2y-50=0这个方程的所有解应该是一条直线,所以我很单纯的去把图给画了,就像下面这个样子:

img_ab37e8b87a97d72c897bbf9b61581587.jpe
PHP经典面试题:上台阶问题

再考虑x和y都必须是整数才能符合题意,y取值在025之间,可以看出只要y是整数解那么x一定为整数解,0也可以作为一种特殊情况,综上y可能的取值是:025共26个。那么相对应的x取值也就可以算出来了。

这里还有一种情况,如果总台阶数不是50,那么y的取值范围有可能是0~24.5,那么我认为y只能取值到24,也就是向下取整。

思路step2:

如果仅从数量上来看,xy总共有26种组合的方式,但这肯定不是最后答案,例如,迈2次1步再迈24次2步和先迈24次2步再迈2次1步是两种不同的方式,那么接下来就是排列组合的问题。

所以,我们要求的是所有xy同为整数的解的排列之和,是不是感觉有点复杂了,但是没关系,前面说的内容都是用PHP可以实现的,排列组合也是可以用PHP实现的。然后,排列组合算法的第一个问题就是如何实现阶乘?

在PHP中range函数可以建立一个包含指定范围单元的数组,允许传入三个参数起始值、终止值和步长值,例如rang(1,3)会返回包含1、2、3这三个数的一个数组。

另外PHP中的array_product函数可以计算数组中所有值的乘积

有了这两个函数我们就可以自己写出阶乘的函数了,虽然我不知道效率怎么样,但起码我们不用往递归的方面去想了,另外还需要考虑一下0和1阶乘的情况,就是下面这个样子:

img_52240f6e2bff322129202b89d961695c.jpe
PHP经典面试题:上台阶问题

有了阶乘,排列也就有了:

img_43774adfb6f33ddc006e22014e2b7a87.jpe
PHP经典面试题:上台阶问题

回到问题上来,我们需要用到组合吗?

首先,总数量是确定的x+y,而且第一次迈2步和后面无论第几次迈2步都是相同的,所以这种排列组合其实可以转化为“把鸡蛋放入篮子”的问题——将n个无差别的鸡蛋放入m个篮子中共有几种放法。那么求组合数函数也是需要的:

img_23eb5b776365a0a4ba0f00dade55abda.jpe
PHP经典面试题:上台阶问题

接下来就是循环每一个可能解,可以总是将x值作为鸡蛋的数量,将xy之和作为篮子的数量,也就是C(x+y,x),举个例子来说就是,总共要迈26次脚,选择其中2次只迈1步,有多少种迈法。

思路step3:

有了前面那么多的思考,我们来写代码:

img_df00ef9823b0a92c0b137899cfddd1da.jpe
PHP经典面试题:上台阶问题

经过测试,最终50级台阶的走法有20365011074种,二百零三亿六千五百零一万一千零七十四种(醉了)。

那么到这里我就开始去网络上找正确答案了,让我震惊了,发现我的思路果然是初中生的,且是从来不参加任何数学竞赛的那种,下面我分析一下网络上答案的思路。

答tu案cao

网上的解只有一种,那就是把这个问题归结为斐波那契数列的问题,完全看不出来好吗!

答案穷举了总台阶数从1级到5级的情况,得出结论1级共1种走法,2级2种走法,3级3中走法,4级5种走法,5级有八种走法,然后就开始研究斐波那契数列去了!

那你出个题目出个那么悬乎干嘛!直接让我们用PHP写个斐波那契函数不就好了吗!要考察思维能力也得给点提示啊!比如说设置两个问题:第一问,当台阶总数为5时有几种走法?第二问,当台阶总数为n时有几种走法?

总之呢就是在面试的时候,如果你见过这题那么恭喜你,如果没见过那么就可以去下一题了。

当然也有大神给出了比较让人信服的逻辑:

当我们走到第50层的时候,最后有两种选择,从49开始迈1级或者从48开始迈2级。那么到达50层的走法等于到达49层的走法+到达48层的走法,以此类推,可以得到总的走法符合斐波那契数列,我们的代码就好写了。

恩............膜拜奥数大神的思维。

PHP写斐波那契应该是比较简单的问题,那最后让我们用答案中的斐波那契函数来验证一下自己的答案。

img_5f416301ee25f53defc6264fd782bce0.jpe
PHP经典面试题:上台阶问题

可以看到,小编自己的思路和最终答案是相同的,只是过程相对复qing杂xi。

还是不太放心,测试了台阶总数从1~7的所有情况,也都是符合答案的,甚至我没有特殊考虑的只有1~2层的情况也能返回正确的答案。

目录
相关文章
|
PHP
复盘微信支付金额不正确问题解决过程——PHP浮点型计算
问题 2017年9月份,商城项目在运行过程中,购买某商品时如果在下单时没有完成付款,而是稍后再从“个人中心-我的订单”发起付款,则无法调起微信支付界面 思路 其他商品正常,说明导致问题的原因大概率是商品本身 只有从会员中心发起的付款存在此问题,说明大...
1379 0
|
算法 PHP
复盘PHP经典问题解决过程:穷举问题
问题 对于5个数字的集合[1,2,3,4,5],从中取出3个,不分先后,共有多少种取法? 这是一个很简单的组合问题,在之前的文章中就解决过:PHP经典面试题:上台阶问题。
1284 0
|
2月前
|
安全 关系型数据库 MySQL
PHP与MySQL交互:从入门到实践
【9月更文挑战第20天】在数字时代的浪潮中,掌握PHP与MySQL的互动成为了开发动态网站和应用程序的关键。本文将通过简明的语言和实例,引导你理解PHP如何与MySQL数据库进行对话,开启你的编程之旅。我们将从连接数据库开始,逐步深入到执行查询、处理结果,以及应对常见的挑战。无论你是初学者还是希望提升技能的开发者,这篇文章都将为你提供实用的知识和技巧。让我们一起探索PHP与MySQL交互的世界,解锁数据的力量!
|
2月前
|
NoSQL 关系型数据库 MySQL
不是 PHP 不行了,而是 MySQL 数据库扛不住啊
【9月更文挑战第8天】这段内容讨论了MySQL在某些场景下面临的挑战及其原因,并指出这些问题不能完全归咎于MySQL本身。高并发读写压力、数据量增长以及复杂查询和事务处理都可能导致性能瓶颈。然而,应用程序设计不合理、系统架构不佳以及其他数据库选择和优化策略不足也是重要因素。综合考虑这些方面才能有效解决性能问题,而MySQL通过不断改进和优化,仍然是许多应用场景中的可靠选择。
124 9
|
3月前
|
存储 SQL 关系型数据库
PHP与MySQL交互的奥秘
【8月更文挑战第29天】在编程的世界里,PHP和MySQL就像是一对默契的舞伴,共同演绎着数据的交响曲。本文将带你探索它们之间的互动,从连接数据库到执行查询,再到处理结果,每一步都充满了节奏与和谐。我们将一起走进这段代码的旅程,感受数据流动的魅力。
|
4天前
|
存储 关系型数据库 MySQL
PHP与MySQL动态网站开发深度解析####
本文作为技术性文章,深入探讨了PHP与MySQL结合在动态网站开发中的应用实践,从环境搭建到具体案例实现,旨在为开发者提供一套详尽的实战指南。不同于常规摘要仅概述内容,本文将以“手把手”的教学方式,引导读者逐步构建一个功能完备的动态网站,涵盖前端用户界面设计、后端逻辑处理及数据库高效管理等关键环节,确保读者能够全面掌握PHP与MySQL在动态网站开发中的精髓。 ####
|
5天前
|
关系型数据库 MySQL PHP
PHP与MySQL动态网站开发实战指南####
本文深入探讨了PHP与MySQL在动态网站开发中的应用实践,通过具体案例解析如何高效结合这两大技术构建数据驱动的Web应用。文章将涵盖环境搭建、基础语法回顾、数据库设计与操作、用户注册与登录系统实现等关键步骤,旨在为开发者提供一个从零到一的项目实战路径,展示PHP与MySQL协同工作的强大能力。 ####
|
24天前
|
SQL 关系型数据库 MySQL
PHP与MySQL协同工作的艺术:开发高效动态网站
在这个后端技术迅速迭代的时代,PHP和MySQL的组合仍然是创建动态网站和应用的主流选择之一。本文将带领读者深入理解PHP后端逻辑与MySQL数据库之间的协同工作方式,包括数据的检索、插入、更新和删除操作。文章将通过一系列实用的示例和最佳实践,揭示如何充分利用这两种技术的优势,构建高效、安全且易于维护的动态网站。
|
3月前
|
SQL 关系型数据库 MySQL
PHP与MySQL交互之基础教程
【8月更文挑战第31天】 在数字世界中,数据是推动一切的核心力量。本文将引导你探索PHP与MySQL的协同工作,通过实际代码示例,展示如何建立连接、执行查询以及处理结果集。无论你是初学者还是希望巩固知识的开发者,这篇文章都将为你提供宝贵的实践知识。
|
4月前
|
数据库
基于PHP+MYSQL开发制作的趣味测试网站源码
基于PHP+MYSQL开发制作的趣味测试网站源码。可在后台提前设置好缘分, 自己手动在数据库里修改数据,数据库里有就会优先查询数据库的信息, 没设置的话第一次查询缘分都是非常好的 95-99,第二次查就比较差 , 所以如果要你女朋友查询你的名字觉得很好 那就得是她第一反应是查和你的缘分, 如果查的是别人,那不好意思,第二个可能是你。
66 3