c語言經典演算法100例

Ⅰ c語言經典題目

1.正確的演算法:
如果n=3, 過河時間為A+B+C
如果n<=2, 好算, 不費口舌了

如果n>=4, 這個是重點:
每次優先考慮把最慢兩人送過河
把n人中最快兩人記為A,B, 最慢兩人記為C,D(過河時間A<B<C<D), n人問題實質上轉換為4人過河問題, 參考到4人過河時的優化,
記AB過河, A回, CD過河, B回, 為方法X, 實質是利用最快兩人進行優化, 耗時A+2B+D
記AD過河, A回, AC過河, A回, 為方法y, 實質是利用最快一人來過河, 耗時2A+C+D
每次比較這兩個方法, 如果x快, 使用x方法, 如果y快, 則用y, 並且, 一旦某次使用y方法後, 以後都不用比較了, 全部使用y方法過河

2.演算法正確性證明:
為什麼每次先讓最慢兩人過河? 因為他們遲早要過河...早過晚過一樣, 而晚過的話, 有可能時間不能被優化, 所以選擇最先過
為什麼是兩人, 不是三人? 因為這船一次只能兩人, 三人問題和兩人問題的優化一樣, 所以一次考慮三人毫無意義, 同理, 三人以上不加考慮

為什麼某次用y過河後不用再比較xy了?
先看這個例子:

1 99 100 101
用x方法是99+1+101+99= 300
y方法是 101+1+100+1 = 203

y比x快的原因是2A+C+D < A+2B+D, 即 A+C<2B
容易想到, 從此以後A+C都會小於2B了(因為C越來越小)

3.補充:
演算法分析就到這里了, 至於具體的程序...樓主既然是ACMer, 這個應該不困難
當然, 如果樓主需要的話, 也可以給出程序

Ⅱ c語言常用演算法有哪些

0） 窮舉法
窮舉法簡單粗暴，沒有什麼問題是搞不定的，只要你肯花時間。同時對於小數據量，窮舉法就是最優秀的演算法。就像太祖長拳，簡單，人人都能會，能解決問題，但是與真正的高手過招，就頹了。
1） 貪婪演算法
貪婪演算法可以獲取到問題的局部最優解，不一定能獲取到全局最優解，同時獲取最優解的好壞要看貪婪策略的選擇。特點就是簡單，能獲取到局部最優解。就像打狗棍法，同一套棍法，洪七公和魯有腳的水平就差太多了，因此同樣是貪婪演算法，不同的貪婪策略會導致得到差異非常大的結果。
2） 動態規劃演算法
當最優化問題具有重復子問題和最優子結構的時候，就是動態規劃出場的時候了。動態規劃演算法的核心就是提供了一個memory來緩存重復子問題的結果，避免了遞歸的過程中的大量的重復計算。動態規劃演算法的難點在於怎麼將問題轉化為能夠利用動態規劃演算法來解決。當重復子問題的數目比較小時，動態規劃的效果也會很差。如果問題存在大量的重復子問題的話，那麼動態規劃對於效率的提高是非常恐怖的。就像斗轉星移武功，對手強它也會比較強，對手若，他也會比較弱。
3）分治演算法
分治演算法的邏輯更簡單了，就是一個詞，分而治之。分治演算法就是把一個大的問題分為若干個子問題，然後在子問題繼續向下分，一直到base cases，通過base cases的解決，一步步向上，最終解決最初的大問題。分治演算法是遞歸的典型應用。
4） 回溯演算法
回溯演算法是深度優先策略的典型應用，回溯演算法就是沿著一條路向下走，如果此路不同了，則回溯到上一個
分岔路，在選一條路走，一直這樣遞歸下去，直到遍歷萬所有的路徑。八皇後問題是回溯演算法的一個經典問題，還有一個經典的應用場景就是迷宮問題。
5） 分支限界演算法
回溯演算法是深度優先，那麼分支限界法就是廣度優先的一個經典的例子。回溯法一般來說是遍歷整個解空間，獲取問題的所有解，而分支限界法則是獲取一個解（一般來說要獲取最優解）。

Ⅲ 水仙花數的c語言編程。

所謂的「水仙花數」是指一個三位數其各位數字的立方和等於該數本身，例如153是「水仙花數」，因為：153 = 1^3 + 5^3+ 3^3。

下面是完整的C語言編程代碼：

運行結果：
result is：153 370 371 407

(3)c語言經典演算法100例擴展閱讀

常見水仙花數

水仙花數又稱阿姆斯特朗數。

1、三位的水仙花數共有4個：153，370，371，407；

2、四位的四葉玫瑰數共有3個：1634，8208，9474；

3、五位的五角星數共有3個：54748，92727，93084；

4、六位的六合數只有1個：548834；

5、七位的北斗七星數共有4個：1741725，4210818，9800817，9926315；

6、八位的八仙數共有3個：24678050，24678051，88593477