題目
有個(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è)樣子:
再考慮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è)樣子:
有了階乘硫狞,排列也就有了:
回到問(wèn)題上來(lái)信轿,我們需要用到組合嗎?
首先残吩,總數(shù)量是確定的x+y虏两,而且第一次邁2步和后面無(wú)論第幾次邁2步都是相同的,所以這種排列組合其實(shí)可以轉(zhuǎn)化為“把雞蛋放入籃子”的問(wèn)題——將n個(gè)無(wú)差別的雞蛋放入m個(gè)籃子中共有幾種放法世剖。那么求組合數(shù)函數(shù)也是需要的:
接下來(lái)就是循環(huán)每一個(gè)可能解定罢,可以總是將x值作為雞蛋的數(shù)量,將xy之和作為籃子的數(shù)量旁瘫,也就是C(x+y,x)祖凫,舉個(gè)例子來(lái)說(shuō)就是,總共要邁26次腳酬凳,選擇其中2次只邁1步惠况,有多少種邁法。
思路step3:
有了前面那么多的思考宁仔,我們來(lái)寫代碼:
經(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)證一下自己的答案。
可以看到隘截,小編自己的思路和最終答案是相同的扎阶,只是過(guò)程相對(duì)復(fù)qing雜xi。
還是不太放心婶芭,測(cè)試了臺(tái)階總數(shù)從1~7的所有情況东臀,也都是符合答案的,甚至我沒有特殊考慮的只有1~2層的情況也能返回正確的答案雕擂。