經典小雞演算法

小雞問題是經典的基礎演算法問題，今天我們使用php解釋並優化小雞演算法問題。

1、問題描述

公雞5文錢一隻，母雞3文錢一隻，小雞3隻一文錢，用100文錢買一百隻雞，其中公雞，母雞，小雞都必須要有，問公雞，母雞，小雞要買多少只剛好湊足100文錢。

2、演算法分析

這是這個問題最常規的解法，看下程序的運行結果。

這個演算法是可以得到問題的答案，但是演算法的時間複雜度為O(N3)，我們可以嘗試優化該演算法使其時間複雜度降到O(N)。

3、演算法優化

首先根據問題分析了母雞、公雞的取值範圍，再通過代數式運算得到小雞的取值範圍，這樣通過人為分析縮小參數範圍，直接就減少了很多不必要的運算從而提高了演算法效率。

運行速度提高了將近1000倍。

再來看第二個優化。

設母雞有x，公雞有y，小雞有z，則 5x+3y+z/3=100 和 x+y+z=100；

消元得到 15x+9y+z=300 => 14x+8y=200 => y = 25-(7/4)x

令x=4k 則 y=25-7k， 4k+25-7k+z=100 => 25-3k+z=100 => z=75+3k

由以上可知 k取值區間為 [1,2,3]

這個優化也是首先通過數學方程消元來得到各個變數的一元一次方程，再結合已知條件確定參數的範圍，這個優化後的演算法時間複雜度降為O(N)。

程序運行結果為：

相對上一步優化速度提升了20多倍。

感受到數學的魅力了吧，所以說數學才是演算法的基礎呢。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！