演算法題目基本思想

1. 動態規劃演算法的基本思想是什麼

動態規劃演算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。動態規劃演算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規劃演算法多種多樣，但它們具有相同的填表格式。

2. 基本演算法思想之窮舉法

窮舉演算法是最基本的演算法思想，我們通過一個簡單的例子來看看窮舉演算法的應用。雞兔同籠問題：

通過分析我們可以知道雞的數量應該為0~35之間的數。這樣，我們可以使用窮舉法來逐個判斷是否符合，從而搜索答案。

3. 舍伍德演算法的基本思想

設A是一個確定性演算法，當它的輸入實例為x時所需的計算時間記為tA(x)。設Xn是演算法A的輸入規模為n的實例的全體，則當問題的輸入規模為n時，演算法A所需的平均時間為這顯然不能排除存在x∈Xn使得 tA(x)>>tA(n)的可能性。
希望獲得一個概率演算法B，使得對問題的輸入規模為n的每一個實例均有
這就是舍伍德演算法設計的基本思想。當s(n)與tA(n)相比可忽略時，舍伍德演算法可獲得很好的平均性能。
舍伍德演算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性演算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時，可以在這個確定演算法中引入隨機性將它改造成一個舍伍德演算法，消除或減少問題的好壞實例間的這種差別。舍伍德演算法精髓不是避免演算法的最壞情況行為，而是設法消除這種最壞行為與特定實例之間的關聯性。

4. kmp演算法的基本思想

主串：a
b
a
c
a
a
b
a
c
a
b
a
c
a
b
a
a
b
b，下文中我們稱作T
模式串：a
b
a
c
a
b，下文中我們稱作W
在暴力字元串匹配過程中，我們會從T[0]
跟
W[0]
匹配，如果相等則匹配下一個字元，直到出現不相等的情況，此時我們會簡單的丟棄前面的匹配信息，然後從T[1]
跟
W[0]匹配，循環進行，直到主串結束，或者出現匹配的情況。這種簡單的丟棄前面的匹配信息，造成了極大的浪費和低下的匹配效率。
然而，在KMP演算法中，對於每一個模式串我們會事先計算出模式串的內部匹配信息，在匹配失敗時最大的移動模式串，以減少匹配次數。
比如，在簡單的一次匹配失敗後，我們會想將模式串盡量的右移和主串進行匹配。右移的距離在KMP演算法中是如此計算的：在已經匹配的模式串子串中，找出最長的相同的前綴和後綴，然後移動使它們重疊。
在第一次匹配過程中
T:
a
b
a
c
a
a
b
a
c
a
b
a
c
a
b
a
a
b
b
W:
a
b
a
c
ab
在T[5]與W[5]出現了不匹配，而T[0]~T[4]是匹配的，現在T[0]~T[4]就是上文中說的已經匹配的模式串子串，現在移動找出最長的相同的前綴和後綴並使他們重疊：
T:
a
b
a
c
aab
a
c
a
b
a
c
a
b
a
a
b
b
W:
a
b
a
c
ab
然後在從上次匹配失敗的地方進行匹配，這樣就減少了匹配次數，增加了效率。
然而，有些同學可能會問了，每次都要計算最長的相同的前綴會不會反而浪費了時間，對於模式串來說，我們會提前計算出每個匹配失敗的位置應該移動的距離，花費的時間是常數時間。比如：
j012345W[j]abacabF(j)001012當W[j]與T[i]不匹配的時候，設置j
=
F(j-1)
文獻中，朱洪對KMP演算法作了修改，他修改了KMP演算法中的next函數，即求next函數時不但要求W[1,next(j)-1]=W[j-(next(j)-1)，j-1]，而且要求W[next(j)]<>W[j]，他記修改後的next函數為newnext。顯然在模式串字元重復高的情況下，朱洪的KMP演算法比KMP演算法更加有效。
以下給出朱洪的改進KMP演算法和next函數和newnext函數的計算演算法。

5. 動態規劃演算法的基本思想

動態規劃演算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題。

拓展資料：

動態規劃的實質是分治思想和解決冗餘，因此動態規劃是一種將問題實例分析為更小的、相似的子問題，並存儲子問題的解而避免計算重復的子問題，以解決最優化問題的演算法策略
動態規劃所針對的問題有一個顯著的特徵，即它對應的子問題樹中的子問題呈現大量的重復。動態規劃的關鍵在於，對於重復的子問題，只在第一次遇到時求解，並把答案保存起來，讓以後再遇到時直接引用，不必要重新求解。

6. 常見演算法思想6：回溯法

回溯法也叫試探法，試探的處事方式比較委婉，它先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一進行枚舉和檢驗。當發現當前候選解不可能是正確的解時，就選擇下一個候選解。如果當前候選解除了不滿足問題規模要求外能夠滿足所有其他要求時，則繼續擴大當前候選解的規模，並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在試探演算法中，放棄當前候選解，並繼續尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。

（1）針對所給問題，定義問題的解空間。
（2）確定易於搜索的解空間結構。
（3）以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索。

回溯法為了求得問題的正確解，會先委婉地試探某一種可能的情況。在進行試探的過程中，一旦發現原來選擇的假設情況是不正確的，馬上會自覺地退回一步重新選擇，然後繼續向前試探，如此這般反復進行，直至得到解或證明無解時才死心。

下面是回溯的3個要素。
（1）解空間：表示要解決問題的范圍，不知道範圍的搜索是不可能找到結果的。
（2）約束條件：包括隱性的和顯性的，題目中的要求以及題目描述隱含的約束條件，是搜索有解的保證。
（3）狀態樹：是構造深搜過程的依據，整個搜索以此樹展開。

下面是影響演算法效率的因素：

回溯法搜索解空間時，通常採用兩種策略避免無效搜索，提高回溯的搜索效率:

為縮小規模，我們用顯示的國際象棋8*8的八皇後來分析。按照國際象棋的規則，皇後的攻擊方式是橫，豎和斜向。
皇後可以攻擊到同一列所有其它棋子，因此可推導出每1列只能存在1個皇後，即每個皇後分別占據一列。棋盤一共8列，剛好放置8個皇後。

為了擺放出滿足條件的8個皇後的布局，可以按如下方式逐步操作：

把規模放大到N行N列也一樣，下面用回溯法解決N皇後問題：

執行：

7. 什麼是演算法構造演算法的基本思想是什麼

1順序結構
按從上到下的順序進行
2選擇結構
根據條件作判斷,再決定執行哪一種操作的演算法結構
必須包含判斷框
3循環結構

8. 數據結構中圖的克魯斯卡爾演算法的基本思想是

基本思想是：設有一個有n個頂點的連通網路N=｛V，E｝，最 初先構造一個只有n個頂點，沒有邊的非連通圖 T=｛ V，￠｝，圖中每個頂點自成一個 連通分量。當在E中選到一條具有最小權值的邊時，若該邊的兩個頂點落在不同的連通 分量上，則將此邊加人到T中；否則將此邊捨去，重新選擇一條權值最小的邊。如此重復 下去，直到所有頂點在同一個連通分量上為止。

9. 外部排序演算法基本思想是什麼

外部排序的基本思路

假設有一個72KB的文件，其中存儲了18K個整數，磁碟中物理塊的大小為4KB，將文件分成18組，每組剛好4KB。

首先通過18次內部排序，把18組數據排好序，得到初始的18個歸並段R1~R18，每個歸並段有1024個整數。

然後對這18個歸並段使用4路平衡歸並排序：

第1次歸並：產生5個歸並段

R11 R12 R13 R14 R15

其中

R11是由{R1,R2,R3,R4}中的數據合並而來

R12是由{R5,R6,R7,R8}中的數據合並而來

R13是由{R9,R10,R11,R12}中的數據合並而來

R14是由{R13,R14,R15,R16}中的數據合並而來

R15是由{R17,R18}中的數據合並而來

把這5個歸並段的數據寫入5個文件：

foo_1.dat foo_2.dat foo_3.dat foo_4.dat foo_5.dat

第2次歸並：從第1次歸並產生的5個文件中讀取數據，合並，產生2個歸並段

R21 R22

其中R21是由{R11,R12,R13,R14}中的數據合並而來

其中R22是由{R15}中的數據合並而來

把這2個歸並段寫入2個文件

bar_1.dat bar_2.dat

第3次歸並：從第2次歸並產生的2個文件中讀取數據，合並，產生1個歸並段

R31

R31是由{R21,R22}中的數據合並而來

把這個文件寫入1個文件

foo_1.dat

此即為最終排序好的文件。

二 使用敗者樹加快合並排序

外部排序最耗時間的操作時磁碟讀寫，對於有m個初始歸並段，k路平衡的歸並排序，磁碟讀寫次數為

|logkm|，可見增大k的值可以減少磁碟讀寫的次數，但增大k的值也會帶來負面效應，即進行k路合並

的時候會增加演算法復雜度，來看一個例子。

把n個整數分成k組，每組整數都已排序好，現在要把k組數據合並成1組排好序的整數，求演算法復雜度

10. 演算法設計的基本思想與方法是什麼

本書圍繞演算法設計技術組織素材，對每種演算法技術選擇了多個典型範例進行分析。本書將直觀性與嚴謹性完美地結合起來。每章從實際問題出發，經過具體、深入、細致的分析，自然且富有啟發性地引出相應的演算法設計思想，並對演算法的正確性、復雜性進行恰當的分析、認證。