演算法設計與分析
一：改進演算法和提高計算機處理能力對演算法速度的影響
答：（1）首先從改進演算法看對演算法速度的影響
從上面例子看出改進演算法對演算法速度的影響是明顯的。
（2）從提高計算機處理能力對演算法速度的影響
從例子看出提高計算機處理能力對2的n次方或者n!的時間複雜性演算法速度影響有限。
1) 二： 證明證明是的上界
答：設g(n)=, f(n)= +2n+6，
當 n >= 6 +2n=6<=+2n+n=+3n<=+3=4()=o()
根據大o的定義當存在正的常數和自然數no ,當ｎ＞no ｆ（n)=o(g(n))時可以得出是+2n+6的上界。
三 答：設h(n)= max
max ≤ max = max=2o(h(n))=o(h(n)+h(n))
根據o的性質可得出max= o（max).
四：分析二分搜尋的時間複雜性，改寫二分搜尋演算法使得搜尋元素x不在陣列中時，返回小於x的最大元素位置i和大於x的最小元素位置j。如搜尋元素在陣列中，i和j相同，均為x在陣列中的位置。
演算法複雜度為o(logn)
五：拉斯維加斯( las vegas )演算法與蒙特卡羅(monte carlo)演算法比較
他們都是概率隨機演算法
拉斯維加斯演算法的乙個顯著特徵是它所作的隨機性決策有可能導致演算法找不到問題所需的解，即演算法執行一次或者得到乙個正確解，或者無解，無解的話繼續求解。
蒙特卡羅演算法則在一般情況下可以保證對問題的所有例項都以高概率給出正確解，但是通常無法判定乙個具體解是否正確
六 三個顧客需要的服務時間分別是t1,t2,t3 求解顧客的服務順序
七 tsp
選權值最小的
答：最短路徑根據權值最小的方法 1--3 是1 3-2 是2 2到4 是1 4到1 是1
所以可以得出最短路徑是1,3,2,4,1的迴路
八：0/1揹包和揹包
這兩類問題都具有最優子結構性質，揹包問題可以用貪心法求解，而0/1問題不能（分支界限法（要考吧）
九兄妹分財產問題以及其複雜度分析
回溯法求解全排列問題
求主元素的兩種方法，一種是線性規劃方法，一種是蒙特卡羅演算法
1.課本習題2-9 p38頁線性規劃方法
蒙特卡羅演算法
課本p263頁
randomnumber rnd
template
bool majority(type *t,int n)
回溯法與分支限界法比較，有什麼相同？有什麼不同？
相同點：分支限界法類似於回溯法，也是一種在問題的解空間樹t上搜尋問題的解法。
不同點：（1）兩者的求解目標不同。回溯法的求解目標是找出t中滿足約束條件的所有解，而分支限界法的求解目標就是找出滿足約束條件的乙個解，或是在滿足約束條件的解中找出使某一目標函式值達到極大或極小的解，即在某種意義下的最優解。
（2）兩者在解空間樹t上的搜尋方式不同。回溯法以深度優先的方式搜尋解空間樹t，而分支限界法則以廣度優先或者最小耗費優先的方式搜尋解空間數t。
圖的著色問題
見ppt
演算法經典程式
目錄第二講分治法 2 迴圈賽日程表問題 2 第三講動態規劃 6 矩陣連乘問題 6 最長公共子串行 7 0 1揹包問題 9 最大k乘積問題 11 第四講貪心法 13 揹包問題 13 活動安排問題 14 最優裝載 15 第五講回溯法 18 裝載問題 18 八皇后問題 20 圖的m著色問題 24 第六講分...
各大軟體公司經典演算法面試題
2011 04 03 微軟1.有乙個整數陣列，請求出兩兩之差絕對值最小的值，記住，只要得出最小值即可，不需要求出是哪兩個數。2.寫乙個函式，檢查字元是否是整數，如果是，返回其整數值。或者 怎樣只用4行 編寫出乙個從字串到長整形的函式？3.給出乙個函式來輸出乙個字串的所有排列。4.請編寫實現mallo...
C語言經典演算法詳解
分而治之方法與軟體設計的模組化方法非常相似。為了解決乙個大的問題，可以 1 把它分成兩個或多個更小的問題 2 分別解決每個小問題 3 把各小問題的解答組合起來，即可得到原問題的解答。小問題通常與原問題相似，可以遞迴地使用分而治之策略來解決。下列通過例項加以說明。例 利用分而治之演算法求乙個整數陣列中...