復(fù)盤PHP經(jīng)典問(wèn)題解決過(guò)程:上臺(tái)階問(wèn)題

題目

有個(gè)人想上一個(gè)50級(jí)的臺(tái)階巾兆,每次只能邁1級(jí)或者邁2級(jí)臺(tái)階如捅,問(wèn):這個(gè)人有多少種方法可以把臺(tái)階走完?例如:總共3級(jí)臺(tái)階样傍,可以先邁1級(jí)再邁2級(jí)横缔,或者先邁2級(jí)再邁1級(jí),或者邁3次1級(jí)總共3中方式衫哥。

心路歷程

這個(gè)題目我剛看到的時(shí)候覺得很有意思茎刚,值得思考一下,也和同學(xué)討論過(guò)思路撤逢,并沒有直接去網(wǎng)上找答案膛锭,覺得那樣的話就浪費(fèi)了捌斧,所以自己先嘗試著解了。

說(shuō)這么多是希望大家也不要直接去看解答泉沾,因?yàn)榭赐曛笠粋€(gè)星期也就忘了捞蚂。可以先收藏一手跷究,自己去試試然后再回來(lái)看姓迅,我會(huì)把我自己解的思路和正解都放在這篇文章里。

思路step1:

從初中生的思路來(lái)看俊马,第一個(gè)能想到的方法肯定是一個(gè)二元方程丁存,也就是x+2y=50,其中x代表邁1步柴我,y代表邁2步解寝,無(wú)論怎么邁總共50級(jí)臺(tái)階。

接下來(lái)的問(wèn)題就是求這個(gè)方程解的數(shù)量(不是某一個(gè)解)艘儒,x+2y-50=0這個(gè)方程的所有解應(yīng)該是一條直線聋伦,所以我很單純的去把圖給畫了,就像下面這個(gè)樣子:

PHP經(jīng)典面試題:上臺(tái)階問(wèn)題

再考慮x和y都必須是整數(shù)才能符合題意界睁,y取值在025之間觉增,可以看出只要y是整數(shù)解那么x一定為整數(shù)解,0也可以作為一種特殊情況翻斟,綜上y可能的取值是:025共26個(gè)逾礁。那么相對(duì)應(yīng)的x取值也就可以算出來(lái)了。

這里還有一種情況访惜,如果總臺(tái)階數(shù)不是50嘹履,那么y的取值范圍有可能是0~24.5,那么我認(rèn)為y只能取值到24债热,也就是向下取整砾嫉。

思路step2:

如果僅從數(shù)量上來(lái)看,xy總共有26種組合的方式阳柔,但這肯定不是最后答案焰枢,例如蚓峦,邁2次1步再邁24次2步和先邁24次2步再邁2次1步是兩種不同的方式舌剂,那么接下來(lái)就是排列組合的問(wèn)題。

所以暑椰,我們要求的是所有xy同為整數(shù)的解的排列之和霍转,是不是感覺有點(diǎn)復(fù)雜了,但是沒關(guān)系一汽,前面說(shuō)的內(nèi)容都是用PHP可以實(shí)現(xiàn)的避消,排列組合也是可以用PHP實(shí)現(xiàn)的低滩。然后,排列組合算法的第一個(gè)問(wèn)題就是如何實(shí)現(xiàn)階乘岩喷?

在PHP中range函數(shù)可以建立一個(gè)包含指定范圍單元的數(shù)組恕沫,允許傳入三個(gè)參數(shù)起始值、終止值和步長(zhǎng)值纱意,例如rang(1,3)會(huì)返回包含1婶溯、2、3這三個(gè)數(shù)的一個(gè)數(shù)組偷霉。

另外PHP中的array_product函數(shù)可以計(jì)算數(shù)組中所有值的乘積迄委。

有了這兩個(gè)函數(shù)我們就可以自己寫出階乘的函數(shù)了,雖然我不知道效率怎么樣类少,但起碼我們不用往遞歸的方面去想了叙身,另外還需要考慮一下0和1階乘的情況,就是下面這個(gè)樣子:

PHP經(jīng)典面試題:上臺(tái)階問(wèn)題

有了階乘硫狞,排列也就有了:

PHP經(jīng)典面試題:上臺(tái)階問(wèn)題

回到問(wèn)題上來(lái)信轿,我們需要用到組合嗎?

首先残吩,總數(shù)量是確定的x+y虏两,而且第一次邁2步和后面無(wú)論第幾次邁2步都是相同的,所以這種排列組合其實(shí)可以轉(zhuǎn)化為“把雞蛋放入籃子”的問(wèn)題——將n個(gè)無(wú)差別的雞蛋放入m個(gè)籃子中共有幾種放法世剖。那么求組合數(shù)函數(shù)也是需要的:

PHP經(jīng)典面試題:上臺(tái)階問(wèn)題

接下來(lái)就是循環(huán)每一個(gè)可能解定罢,可以總是將x值作為雞蛋的數(shù)量,將xy之和作為籃子的數(shù)量旁瘫,也就是C(x+y,x)祖凫,舉個(gè)例子來(lái)說(shuō)就是,總共要邁26次腳酬凳,選擇其中2次只邁1步惠况,有多少種邁法。

思路step3:

有了前面那么多的思考宁仔,我們來(lái)寫代碼:

PHP經(jīng)典面試題:上臺(tái)階問(wèn)題

經(jīng)過(guò)測(cè)試稠屠,最終50級(jí)臺(tái)階的走法有20365011074種,二百零三億六千五百零一萬(wàn)一千零七十四種(醉了)翎苫。

那么到這里我就開始去網(wǎng)絡(luò)上找正確答案了权埠,讓我震驚了,發(fā)現(xiàn)我的思路果然是初中生的煎谍,且是從來(lái)不參加任何數(shù)學(xué)競(jìng)賽的那種攘蔽,下面我分析一下網(wǎng)絡(luò)上答案的思路。

答tu案cao

網(wǎng)上的解只有一種呐粘,那就是把這個(gè)問(wèn)題歸結(jié)為斐波那契數(shù)列的問(wèn)題满俗,完全看不出來(lái)好嗎转捕!

答案窮舉了總臺(tái)階數(shù)從1級(jí)到5級(jí)的情況,得出結(jié)論1級(jí)共1種走法唆垃,2級(jí)2種走法五芝,3級(jí)3中走法,4級(jí)5種走法辕万,5級(jí)有八種走法与柑,然后就開始研究斐波那契數(shù)列去了!

那你出個(gè)題目出個(gè)那么懸乎干嘛蓄坏!直接讓我們用PHP寫個(gè)斐波那契函數(shù)不就好了嗎价捧!要考察思維能力也得給點(diǎn)提示啊涡戳!比如說(shuō)設(shè)置兩個(gè)問(wèn)題:第一問(wèn)结蟋,當(dāng)臺(tái)階總數(shù)為5時(shí)有幾種走法?第二問(wèn)渔彰,當(dāng)臺(tái)階總數(shù)為n時(shí)有幾種走法嵌屎?

總之呢就是在面試的時(shí)候,如果你見過(guò)這題那么恭喜你恍涂,如果沒見過(guò)那么就可以去下一題了宝惰。

當(dāng)然也有大神給出了比較讓人信服的邏輯:

當(dāng)我們走到第50層的時(shí)候,最后有兩種選擇再沧,從49開始邁1級(jí)或者從48開始邁2級(jí)尼夺。那么到達(dá)50層的走法等于到達(dá)49層的走法+到達(dá)48層的走法,以此類推炒瘸,可以得到總的走法符合斐波那契數(shù)列淤堵,我們的代碼就好寫了。

恩............膜拜奧數(shù)大神的思維顷扩。

PHP寫斐波那契應(yīng)該是比較簡(jiǎn)單的問(wèn)題拐邪,那最后讓我們用答案中的斐波那契函數(shù)來(lái)驗(yàn)證一下自己的答案。

PHP經(jīng)典面試題:上臺(tái)階問(wèn)題

可以看到隘截,小編自己的思路和最終答案是相同的扎阶,只是過(guò)程相對(duì)復(fù)qing雜xi。

還是不太放心婶芭,測(cè)試了臺(tái)階總數(shù)從1~7的所有情況东臀,也都是符合答案的,甚至我沒有特殊考慮的只有1~2層的情況也能返回正確的答案雕擂。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末啡邑,一起剝皮案震驚了整個(gè)濱河市贱勃,隨后出現(xiàn)的幾起案子井赌,更是在濱河造成了極大的恐慌谤逼,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件仇穗,死亡現(xiàn)場(chǎng)離奇詭異流部,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)纹坐,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門枝冀,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人耘子,你說(shuō)我怎么就攤上這事果漾。” “怎么了谷誓?”我有些...
    開封第一講書人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵绒障,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我捍歪,道長(zhǎng)户辱,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任糙臼,我火速辦了婚禮庐镐,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘变逃。我一直安慰自己必逆,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開白布揽乱。 她就那樣靜靜地躺著末患,像睡著了一般。 火紅的嫁衣襯著肌膚如雪锤窑。 梳的紋絲不亂的頭發(fā)上璧针,一...
    開封第一講書人閱讀 52,736評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音渊啰,去河邊找鬼探橱。 笑死,一個(gè)胖子當(dāng)著我的面吹牛绘证,可吹牛的內(nèi)容都是我干的隧膏。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼嚷那,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼胞枕!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起魏宽,我...
    開封第一講書人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤腐泻,失蹤者是張志新(化名)和其女友劉穎决乎,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體派桩,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡构诚,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了铆惑。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片范嘱。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖员魏,靈堂內(nèi)的尸體忽然破棺而出丑蛤,到底是詐尸還是另有隱情,我是刑警寧澤撕阎,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布盏阶,位于F島的核電站,受9級(jí)特大地震影響闻书,放射性物質(zhì)發(fā)生泄漏名斟。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一魄眉、第九天 我趴在偏房一處隱蔽的房頂上張望砰盐。 院中可真熱鬧,春花似錦坑律、人聲如沸岩梳。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)冀值。三九已至,卻和暖如春宫屠,著一層夾襖步出監(jiān)牢的瞬間列疗,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工浪蹂, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留抵栈,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓坤次,卻偏偏與公主長(zhǎng)得像古劲,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子缰猴,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容