https://segmentfault.com/q/1010000000443863

本貼是對(duì)上述地址的問(wèn)題思考。

問(wèn)題：

李白街上走，提壺去買酒，遇店加一倍，見(jiàn)花喝一斗。途中遇5次店，見(jiàn)10次花，壺中原有2斗酒，最后剛好遇見(jiàn)花，剛好喝完酒，求可能的解。

分析：從兩個(gè)角度去分析，一個(gè)是人的角度，另一個(gè)是計(jì)算機(jī)角度。

人的角度：把問(wèn)題抽象成數(shù)學(xué)問(wèn)題求解，確定一些關(guān)系。

1.共見(jiàn)花10次=-10（斗酒），原有2斗酒=2，即增加的酒是-（-10+2）=8（斗酒）

問(wèn)題變成了在五次中增加8斗酒的可能解（遇店=加酒=1，見(jiàn)花=減酒=0，即對(duì)5個(gè)1和10個(gè)0進(jìn)行排列組合，最后一次是0。由于見(jiàn)花不存在順序的區(qū)別，所以只需要把遇店的可能情況排出來(lái)再填入見(jiàn)花即可，所以五次中增加8斗酒的可能解就是最終整個(gè)問(wèn)題的可能解數(shù)）

2.增加的酒數(shù)要滿足5次一共加8斗，注定了增加的酒數(shù)不能大于4（五次中每次都加1斗酒是最少的，還剩下3斗，全部加到其中一次就是4斗，即一次最大只能加4斗）。

綜合上述兩點(diǎn)，我們可以有：

11222/11132/11114這三種可能，

那么這三種可能是否有不成立的呢（下面說(shuō)的“基數(shù)”指翻倍前的酒數(shù)）？

對(duì)于11114：

要想增加4斗酒，就必須有基數(shù)4去翻倍?；鶖?shù)是4的可能情況有：

A.原先有2斗酒，遇店后變成4斗

此時(shí)必須有24，而11114中沒(méi)有2，所以不可能。

B.原先有n（n≥5）斗酒，遇花后變成4斗再遇店

原先有2斗，已經(jīng)增加了至少3斗酒（n-2≥3），還要增加4斗，則一共增加了3+4=7斗，也就是說(shuō)，要遇店4次加7斗酒（還有一次加1斗才滿足5次加8斗的條件），其中有一次是加4斗的，也就是遇店3次加3斗，而這是不可能的（相當(dāng)于1次加1斗，而1次加1斗意味著基數(shù)是1，那么又怎么能有n斗酒出現(xiàn)呢？n可是大于等于5的！）。綜上，11114的情況是不可能的。

（其實(shí)看到1111就知道不可能了，增加1斗酒，基數(shù)必須是1，四個(gè)基數(shù)都是1，后面不可能基數(shù)變成4出現(xiàn)增加1斗酒的情況。這是我后來(lái)才發(fā)現(xiàn)的....）

11222是可能的，保持基數(shù)是2和1是很容易的事情。

11132，要想增加3斗酒，就必須有基數(shù)3去翻倍，所以不可能是連續(xù)三個(gè)1在3前面，必須是23連著才行。

至此，我們知道了可能的情況是11222，32111.利用高中的排列組合，我們可以有：

11222的可能情況是C25，32111的可能情況是C14，加起來(lái)一共14種可能。

計(jì)算機(jī)角度：函數(shù)與條件

設(shè)J=酒，D=遇店剩余次數(shù)，H=見(jiàn)花剩余次數(shù)

初始條件可列：

J=2，D=5，H=10；最后一次是H；J=0，D=0，H=0

其它條件可列：

F（J，H，D）

F（0，H≠0，D≠0），false；F（J≠0，0，D≠0），false；（不能只有J=H=D=0才true，這樣就是暴力遞歸而非用剪枝條件優(yōu)化算法。什么是暴力遞歸和剪枝條件看開(kāi)頭的網(wǎng)址）

F（J，H（J>H），D），false；F（J，H(J·2^D＜H)，D），false

然后是函數(shù)關(guān)系：

H=H-1時(shí)，F(xiàn)=F（J-1，H，D）；D=D-1時(shí)，F(xiàn)=F（2J，H，D）

用if循環(huán)來(lái)遞歸就可以得出解了。詳細(xì)的代碼在開(kāi)頭的網(wǎng)址里有。（有空我會(huì)用C++實(shí)現(xiàn)，然后補(bǔ)充進(jìn)這個(gè)帖子）

回顧上面兩個(gè)角度，我發(fā)現(xiàn)所謂算法，和人的角度本質(zhì)上是一樣的：人在思考的時(shí)候往往一開(kāi)始也是用窮舉的方法去思考，只不過(guò)我們沒(méi)有那么死板，我們會(huì)用“剪枝”（開(kāi)頭的文章地址中提到的一個(gè)詞）去把一些不對(duì)的方法給刪去（比如上文我通過(guò)一系列的演算把11114這條去掉了）。而計(jì)算機(jī)的算法就是在繼續(xù)人“剪枝”后的窮舉。

以上所有，就是我在李白喝酒問(wèn)題中學(xué)到的思維與方法。

wuduojia

總結(jié)

以上是生活随笔為你收集整理的（1）李白喝酒的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。