演算法與程序設計基礎略講（附帶洛谷例題）

前言

這篇文章改編自我的選修課「演算法與程序設計」課程報告，我將裡面的大部分例子換成了洛谷上的例題，適合給想入門程序設計競賽（oi，ACM）或者剛接觸計算機編程不久的人看。其實我也只是一位大自然的搬運工，裡面的許多代碼都不是我自己的....所以如果有冒犯，請聯繫我，我立刻整改。這裡十分感謝gin同學，他為這篇文章打下了框架和脈絡，我也只是在他工作的基礎之上進行了微微的修飾。

1. 第一章程序設計概述.

2. 第二章演算法的表述方式.

3. 第三章結構化程序設計思想概述.

4. 第四章構造類型概述.

5. 第五章動態數據結構概述.

6. 第六章分治法概述與分析.

7. 第七章常見查找和排序演算法.

8. 第八章動態規劃演算法概述與分析.

9. 第九章貪心演算法概述與分析.

10. 第十章回溯法概述與分析.

11. 第十一章隨機演算法概述與分析.

第一、二、三章略....（字數有限）

5.第五章動態數據結構概述

5.1 動態數據結構定義及其特點

數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在著一種或多種關係的數據元素的集合和該集合中數據元素之間的關係組成通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索演算法和索引技術有關。

5.2 動態數據結構的基本類型和在程序中的實例及其分析

線性表：

線性表（Linear List）是由同一類型的數據元素構成的有序序列的線性結構。線性表中元素的個數稱為線性表的長度；當一個線性表中沒有元素時，稱為空表；表的起始位置稱為表頭，表的結束位置稱為表尾。

實例：約瑟夫問題（洛谷P1996）

約瑟夫是一個無聊的人！！！n個人(n<=100)圍成一圈,從第一個人開始報數,數到m的人出列,再由下一個人重新從1開始報數,數到m的人再出圈,……依次類推,直到所有的人都出圈,請輸出依次出圈人的編號。

代碼：

#include<cstdio> #include<vector> using namespace std; int main() { int n,m,s=0;scanf("%d%d",&n,&m);//入讀 vector<bool> visit(n+1,0);//visit賦初始值 for(int k=0;k<n;k++){//總共要出隊n次 for(int i=0;i<m;i++){if(++s>n)s=1;if(visit[s])i--;}//類似取模，而因為序列是從1開始的，所以不取模，加判斷；若visit過，則i--，使其繼續循環 printf("%d ",s);visit[s]=true;//輸出，記錄已出隊 } return 0; }

分析：按照題意去做，用一個長度為n+1的visit線性表（其實是vector）記錄下已經出隊了的人，然後模擬，一個個的加就行了。還要注意，一開始，加的數要賦值為0。還有visit數組要開始全部賦值為false。

總結：在實際情況下，我們往往使用數組作為線性表來使用。C++的stl裏更是提供了vector（不定長數組）類，非常方便。有序的儲存在內存裏是線性表的特點，所以它能夠以o（1）的速度訪問任意一個元素。同樣的，線性表的插入與刪除操作非常耗時。

鏈表：

鏈表可以存儲多個同類型的數據，它是動態地進行存儲分配的一種數據結構。結點是鏈表的基本存儲單位，一個結點對應鏈表中的一個數據元素，所有的結點具有相同的數據結構。每個結點佔用一段連續內存空間，而結點間可以佔用不連續的內存空間。結點與結點間使用指針鏈接在一起。

實例：

依然是剛才的「約瑟夫問題」

代碼：

#include<iostream> using namespace std; struct peo { int ID; //編號 peo *next = NULL, *front = NULL; }n[100]; void _cut(peo *num) { num = num->front; num->next = num->next->next; num = num->next; num->front = num->front->front; } int main() { int tot, outNum, nowNum = 1; peo *now = &n[0]; //指向目前報數的人的指針 cin >> tot >> outNum; //數據讀入 for (int i = 1; i < tot - 1; i++) { n[i].front = &n[i - 1]; n[i].next = &n[i + 1]; n[i].ID = i + 1; } n[0].front = &n[tot - 1]; n[0].next = &n[1]; n[tot - 1].front = &n[tot - 2]; n[tot - 1].next = &n[0]; n[0].ID = 1; n[tot - 1].ID = tot; //初始化鏈表 while (tot > 0) { if (nowNum == outNum) { cout << now->ID << " "; //輸出出局的人的編號 _cut(now); //出局 nowNum = 1; //初始化數字 tot--; //總人數-1 now = now->next; //下一個人 } else { nowNum++; //數字+1 now = now->next; //下一個人 } } return 0; }

分析：這個例子創建了一個首位相連的鏈表，直接模擬即可。

總結：鏈表的特點是可以在內存裏以非連續的方式來存儲元素信息，所以它能在o（1）的時間內實現插入與刪除功能。同樣的，它無法直接的訪問鏈表裡的一個特點元素。

棧：

棧是一種受限定的線性表，它只允許在線性表的同一端做線性表操作。通常將棧允許操作的一端稱為棧頂，而不允許操作的另一端稱為棧底；不含元素的空表稱為空棧；向棧頂插入元素的操作稱為進棧或入棧，而刪除棧頂元素的操作稱為退棧或出棧。棧的操作是一種後進先出的操作。

實例：表達式括弧匹配（洛谷P1739）

假設一個表達式有英文字母（小寫）、運算符（+，—，*，/）和左右小（圓）括弧構成，以「@」作為表達式的結束符。請編寫一個程序檢查表達式中的左右圓括弧是否匹配，若匹配，則返回「YES」；否則返回「NO」。表達式長度小於255，左圓括弧少於20個。

代碼：

#include<stack> #include<iostream> #include<cstdio> using namespace std; stack<char> zhan; int main() { char input; while(scanf("%c",&input)&&input!=@) { if(input==() zhan.push(input);//入棧 if(input==)) { if(zhan.empty()) {//判斷棧是否為空即可 printf("NO "); return 0;//至於為啥要判斷棧是否為空，大家想想，因為假如有個)，結果前面沒有對應(了，那就不行，此時就是棧空 } zhan.pop();//出棧 } } if(zhan.empty()) printf("YES ");//判斷有沒有多餘的( else printf("NO ");//也就是判斷棧是否為空 return 0; }

分析：括弧的匹配就是一個棧的操作過程，每讀入一個「（」就入棧一次，每讀入一個「）」就出棧。棧的操作是一種後進先出的操作。在處理遞歸回溯等問題上，計算機便使用了棧來儲存每個函數的信息。

隊列：

隊列也是一種受限制的線性表，但隊列的插入和刪除操作是分別在線性表的兩個不同端點進行的。允許插入數據的一端稱為隊尾，而允許刪除數據的一端稱為隊頭。

實例：依然是「約瑟夫問題」

代碼：

#include<iostream> #include<queue> using namespace std; int main() { int tot, outNum, nowNum = 1; queue<int> q; cin >> tot >> outNum; //讀取數據 for (int i = 1; i <= tot; i++)q.push(i); //初始化隊列 while (!q.empty()) //在隊列不為空時繼續模擬 { if (nowNum == outNum) { cout << q.front() << " "; //列印出局的人的編號 q.pop(); //出局 nowNum = 1; //初始化現在的數字 } else { nowNum++; q.push(q.front()); //排至隊尾 q.pop(); } } cout << endl; system("pause"); return 0; }

分析：隊列是一種先進先出的數據結構。在一些搜索演算法比如廣度優先搜索裏，便使用了隊列在存儲臨時信息。

樹：

樹是由n（n>=1）個有限節點組成一個具有層次關係的集合。把它叫做「樹」是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

每個節點有0個或多個子節點；沒有父節點的節點稱為根節點；每一個非根節點有且只有一個父節點；除了根節點外，每個子節點可以分為多個不相交的子樹。

實例：FBI樹（洛谷 P1087）

代碼：

#include<iostream> #include<string> #include<cmath> using namespace std; int n,ch[2049]={0},m; string ch2; //n是葉子有n個節點，m是整棵樹有m個節點 //ch用來存節點是F(2)或B(0)I(1) //ch2是最開始輸入的字元串 //這個dg函數s是層數，ll是樹的第ll個節點 int dg(int s,int ll) { if(s==n+1) return ch[ll]; int a=dg(s+1,ll*2),b=dg(s+1,ll*2+1); //滿二叉樹某節點左孩子編號是節點編號*2，右孩子*2+1 if(a==b&&a==1) ch[ll]=1; if(a==b&&a==0) ch[ll]=0; if(a==b&&a==2) ch[ll]=2; if(a!=b) ch[ll]=2; return ch[ll]; } //last函數是後續遍歷，ll是當前遞歸到的節點 void last(int ll) { if(ll>m) return; last(ll*2); last(ll*2+1); if(ch[ll]==0) cout<<"B"; if(ch[ll]==1) cout<<"I"; if(ch[ll]==2) cout<<"F"; } int main() { cin>>n; m=pow(2,n)*2-1; cin>>ch2; for(int i=0;i<ch2.size();i++) ch[m-i]=ch2[ch2.size()-i-1]-0; dg(1,1); last(1); }

分析：這道題使用了數組來儲存一個樹結構,並且直接模擬。從根開始找孩子的值（f是2，b是0，i是1），再用孩子的值來推出根的值。因為是滿二叉樹，所以某節點的左孩子是某節點乘二，右孩子乘二加一。

總結：樹是一種常見的數據結構，一些常見的信息比如上下級關係、優先順序關係、家庭成員關係都能用樹來儲存。

圖：

圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V，E），其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。在圖中的數據元素，我們稱之為頂點，頂點集合有窮非空。在圖中，任意兩個頂點之間都可能有關係，頂點之間的邏輯關係用邊來表示，邊集可以是空的。

實例：信息傳遞（洛谷P2661）

代碼：

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> using namespace std; int dx[300000];//存每一個人傳話的對象 bool visit[300000]={0},novisit[300000]={0};//visit存每次查找中被查到的點，而novisit存每次查找前，已經被查找過的點（及不用繼續查找了） int bs[300000]={0};//每次查找中第一次到一個節點所經過的邊數 int minn=2e9; void dfs(int node,int num) { if(novisit[node])return;//不需要繼續找了 if(visit[node])//在此次查找中出現過 { minn=min(minn,num-bs[node]);//形成一個環，取最小值 } else { visit[node]=true;//在此次循環中經過 bs[node]=num;//記錄第一次到達時的步數 dfs(dx[node],num+1);//搜索 novisit[node]=true;//已經搜過 } } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&dx[i]); } for(int i=1;i<=n;i++) { dfs(i,0);//枚舉全部節點 } printf("%d",minn);//輸出 return 0;//時間複雜度O(n) }

分析：可以把這些關係看成一個有向圖。對於任意一個節點進入，因為每個點的出度均為1，所以最多隻能構成三種情況：1、一條鏈；2、一個環鏈；3、一條鏈連接著一個環鏈。因為這三種情況極為的簡單，所以就可以如下處理：找任意一個點進入，記錄到達每一個點所走過的遍數。當走到一個在這次查找中已經出現過的節點，即找到了一個環，用當前走到的步數減去在此節點原先記錄的步數，便得到這個環的長度。由此搜遍所有點，找到這些環中最小長度的一個，並把它輸出就可以了。

總結：圖也是一種常見的數據結構，它可以用來存儲如地圖、信息中轉站、網路等信息。

小結：常用的數據結構有線性表、鏈表、棧、隊列、樹和圖等，其中鏈表、棧和隊列屬於線性表，而樹和圖是非線性數據結構。

6. 第六章分治法概述與分析

6.1 分治法的基本思想

分治法的基本思想是將一個複雜的問題分解成規模較小的相同的子問題，再將子問題分解成更小的子問題，直到子問題可以直接求解，即分而治之。

一般來說，分治法和遞歸密不可分，通過兩者的結合，可以將子問題的解合併成原問題的解。

6.2 實例及其分析

巡邏的士兵（SCAUOJ 1142）

有N個士兵站成一隊列, 現在需要選擇幾個士兵派去偵察。

為了選擇合適的士兵, 多次進行如下操作: 如果隊列超過三個士兵, 那麼去除掉所有站立位置為奇數的士兵,

或者是去除掉所有站立位置為偶數的士兵。直到不超過三個戰士，他們將被送去偵察。現要求統計按這樣的方法，

總共可能有多少種不同的正好三個士兵去偵察的士兵組合方案。

注: 按上法得到少於三士兵的情況不統計。

1 <= N <= 2的32次方-1

實現代碼：

#include <stdio.h> #include <stdlib.h> unsigned choose(unsigned n) { int remove_odd,remove_even,sum;// remove_odd代表去掉位置為奇數士兵後問題的答案，是原問題的子問題，remove_even同理。 if(n==3) return 1; else if(n<3) return 0; else { if(n%2==0)//當n為偶數時，去掉奇數的人和去掉偶數的人都是少了n/2的人 { remove_odd=choose(n/2); remove_even=choose(n/2); } else//當n為奇數時再分開來討論 { remove_odd=choose((n+1)/2); remove_even=choose((n-1)/2); } sum=remove_odd+remove_even;//合併兩個子問題 return sum; } } int main() { unsigned n; scanf("%u",&n); printf("%d ",choose(n)); return 0; }

分析：將一個大的士兵數N逐步分解為若干個類型相同的子問題求解，直到子問題的士兵數小於或等於3為止，再用遞歸的方法把子問題的解合併。

小結：分治法的精髓：

分--將問題分解為規模更小的子問題；

治--將這些規模更小的子問題逐個擊破；

合--將已解決的子問題合併，最終得出「母」問題的解。

7. 第七章常見查找和排序演算法

7.1 查找演算法

順序查找：

順序查找是在一個已知無(或有序）序隊列中找出與給定關鍵字相同的數的具體位置。

實現代碼：

int sq_search(keytype keyp[],int n,keytype key) { int i; for(i=0; i<n; i++) if(key[i] == key) return i;//查找成功 return -1;//查找失敗 }

分析：順序查找的時間複雜度為o（n），適用於難以進行位置調換或信息修改的數據。

二分查找：

二分查找又叫折半查找，指的是每次的查找範圍折半。

實現代碼：

int binSearch(const int *Array,int start,int end,int key) { int left,right; int mid; left=start; right=end; while(left<=right) { mid=(left+right)/2; if(key==Array[mid]) return mid; else if(key<Array[mid]) right=mid-1; else if(key>Array[mid]) left=mid+1;

}
return -1;
}

分析：比較次數少，查找速度快，但序列必須是有序的。每次比較後，帶查找的範圍都會變為原來的1/2，所以時間複雜度為o（logn）。

7.2 排序演算法

選擇排序：

選擇排序是指每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。

實現代碼：

int main() { int i,j,min,t; for(i=0;i<n-1;i++) { min=i;//查找最小值 for(j=i+1;j<n;j++) if(a[min]>a[j]) min=j;//交換 if(min!=i) { t=a[min]; a[min]=a[i]; a[i]=t; } } }

分析：選擇排序是不穩定的排序方法。時間複雜度最壞時為o（n^2）。

插入排序：

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。

實現代碼：

voidinsert_sort(int*array,unsignedintn) { inti,j; inttemp; for(i=1; i<n; i++) { temp=*(array+i); for(j=i; j>0&&*(array+j-1)>temp; j--) { *(array+j)=*(array+j-1); } *(array+j)=temp; } }

分析：插入排序適用於少量數據的排序，是穩定的排序方法。時間複雜度為o（n^2）。

冒泡排序：

冒泡排序是指重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。

實現代碼：

void bubble_sort(int a[], int n) { int i, j, temp; for (j = 0; j < n - 1; j++) for (i = 0; i < n - 1 - j; i++) { if(a[i] > a[i + 1]) { temp = a[i]; a[i] = a[i + 1]; a[i + 1] = temp; } } }

分析：比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。時間複雜度為o（n^2）。

快速排序：

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

實現代碼：

void sort(int *a, int left, int right) { if(left >= right) { return ; } int i = left; int j = right; int key = a[left];//選取一個分割的比較基準，基準的選取直接影響到排序的速度 while(i < j) { while(i < j && key <= a[j])//從右半邊尋找小的數 { j--; } a[i] = a[j]; while(i < j && key >= a[i])//從左半邊尋找大的數 { i++; } a[j] = a[i]; } a[i] = key; sort(a, left, i - 1); sort(a, i + 1, right); }

分析：快速排序的時間複雜度取決於對key值的選取，若key值接近待排序數列的中位數，那演算法的速度就會比較快；若key值接近待排序數列的最值，那演算法的速度就比價慢。時間複雜度最快是o（nlogn），最慢是o（n^2）。

小結：查找演算法主要有順序查找和二分查找等，排序演算法主要有選擇排序、插入排序、冒泡排序和快速排序等。

8. 第八章動態規劃演算法概述與分析

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

動態規劃演算法的基本思想是將待求解問題用不同的狀態來表示，通過不同狀態間的聯繫，從子狀態出發，求解得到最終狀態的答案。不同狀態之間的聯繫稱為狀態轉移方程。

8.2 實例及其分析

開心的金明（洛谷P1060）

實現代碼：

#include <cstdio>//頭文件 int t[1000001],m[1000001],f[1000001];//t數組是用來表示這個物品的價格（即這個物品的大小），m數組是用來表示這個物品的價值的（即這個物品的權值），f數組是用來存儲答案的。 int maxx(int x,int y)//maxx函數是用來判斷兩個數到底哪一個數大的函數 { return x>y?x:y;//如果x>y，那麼就返回x，否則就返回y } int main()//主函數 { int v=0,n=0;//v表示金明的媽媽給了金明v元錢（即這個揹包的大小），n表示金明有n件想買的物品（即有n件物品可以拿來放入揹包）。那麼，這個問題就可以簡化成：有一個揹包的大小為v，你可以選擇將這n個物品中的幾個放入這個揹包裏，使得這些放入揹包的物品的權值最大 scanf("%d %d",&v,&n);//輸入v和n（即這個揹包的容量和有n件物品可以選擇放進這個揹包裡面） for(int i=1;i<=n;i++)//讀入這n個物品的價格和重要度 { int x=0;//初始化（x是等一下要讀入的第i件物品的重要度，即題目裡面的p[i]） scanf("%d %d",&t[i],&x);//讀入第i件物品的價格和它的重要度（即題目裡面的v[i]和p[i]） m[i]=t[i]*x;//這個物品的價值（因為要求的答案是為不超過總錢數的物品的價格與重要度乘積的總和的最大值，所以將這兩個數）相乘 } for(int i=1;i<=n;i++)//從第1件物品做到第i件物品 { for(int j=v-t[i];j>=0;j--)//從樓頂做到樓底 { f[j+t[i]]=maxx(f[j]+m[i],f[j+t[i]]);//更新最大值（即與原來的值和新的值相比較，請想一下為什麼要這樣做，以及f[0]為什麼不用等於1） } } printf("%d",f[v]);//輸出最大值（即答案） return 0;//結束程序 }

分析：這是一道經典的0-1揹包問題，特點是每種物品僅有一件，可以選擇放或不放，用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的揹包可以獲得的最大價值。則其狀態轉移方程便是：f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }。這道題使用裏空間優化的手段。

小結：能用動態規劃求解的題目，必須具有最優子結構和無後效性的特點。動態規劃的程序既可以寫成「遞歸函數+用函數記錄計算結果」的形式，也可以寫成不用遞歸，在數組內由已知推未知的遞推形式。

9. 第九章貪心演算法概述與分析

9.1 貪心演算法的基本思想

貪心演算法是指從問題的初始狀態出發，通過多次的貪心選擇，最終得到整個問題的最優解。即由局部最優，得到全局最優。

9.2 實例及其分析

木棍加工（洛谷p1233）

實現代碼：

#include<iostream> #include<algorithm> using namespace std;

struct thing{
int lo,wi;
}t[5005];//木棍定義為結構體

bool comp(thing &a,thing &b){
if(a.lo==b.lo)return a.wi>b.wi;
return a.lo>b.lo;
}//定義比較函數，先按從高到低排列長度，長度相同的按從高到低排列寬度

bool used[5005]={};//是否被處理過

int main(){
ios::sync_with_stdio(false);//取消輸入流同步，加快輸入速度
int n,sum=0,twi;
cin>>n;

for(int i=1;i<=n;i++){
cin>>t[i].lo;
cin>>t[i].wi;
}//輸入

sort(t+1,t+n+1,comp);//排序

for(int i=1;i<=n;i++){//雙重循環
if(used[i]==0){//如果這個木棍被處理過就跳過
twi=t[i].wi;//保存現有寬度
for(int j=i+1;j<=n;j++){//向後搜索
if(t[j].wi<=twi&&used[j]==0){//如果有寬度小於現有寬度且沒有被處理過
used[j]=1;//處理這個木棍
twi=t[j].wi;//保存這個木棍的寬度
}
}
}
}

for(int i=1;i<=n;i++){
if(used[i]==0)sum++;//如果沒用過就加1分鐘
}

cout<<sum;//輸出
return 0;
}

先將長度排序，再依次尋找寬度不上升序列，將它們全部標記，最後尋找沒有被標記的。

小結：在對問題求解時，貪心演算法總是做出在當前看來是最好的選擇。

10. 第十章回溯法概述與分析

10.1 回溯法的基本思想

回溯法是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」

10.2 實例及其分析

八皇后（洛谷p1219）

實現代碼：

#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> using namespace std; int a[100],b[100],c[100],d[100]; //a數組表示的是行； //b數組表示的是列； //c表示的是左下到右上的對角線； //d表示的是左上到右下的對角線； int total;//總數:記錄解的總數 int n;//輸入的數，即N*N的格子，全局變數，搜索中要用 int print() { if(total<=2)//保證只輸出前三個解，如果解超出三個就不再輸出，但後面的total還需要繼續疊加 { for(int k=1;k<=n;k++) cout<<a[k]<<" ";//for語句輸出 cout<<endl; } total++;//total既是總數，也是前三個排列的判斷 } void queen(int i)//搜索與回溯主體 { if(i>n) { print();//輸出函數，自己寫的 return; } else { for(int j=1;j<=n;j++)//嘗試可能的位置 { if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))//如果沒有皇后佔領，執行以下程序 { a[i]=j;//標記i排是第j個 b[j]=1;//宣佈佔領縱列 c[i+j]=1; d[i-j+n]=1; //宣佈佔領兩條對角線 queen(i+1);//進一步搜索，下一個皇后 b[j]=0; c[i+j]=0; d[i-j+n]=0; //（回到上一步）清除標記 } } } } int main() { cin>>n;//輸入N*N網格，n已在全局中定義 queen(1);//第一個皇后 cout<<total;//輸出可能的總數 return 0; }

分析：本道題最重要的就是記錄下皇后佔領的格子（打標記的思想），通過此判斷下一個皇后是否可以在某個位置，如果可以，則繼續搜索下一個皇后可以在的位置，如果不行，則清除標記回到上一步，繼續搜索。

小結：以深度優先搜索方式獲得問題的解的演算法稱為回溯法，可用於解組合數大的問題。

11. 第十一章隨機演算法概述與分析

11.1 隨機演算法的基本思想

隨機化演算法中使用了隨機函數，且隨機函數的返回值直接或者間接的影響了演算法的執行流程或執行結果。隨機化演算法基於隨機方法，依賴於概率大小。

11.2 實例及其分析

平衡點（洛谷P1337）

分析：本題可以使用模擬退火演算法來解決。選定一個初始狀態（比如選定所有點坐標的平均數），選定一個初始溫度T。當溫度大於一個邊界值時：

　　隨機變化坐標，變化幅度為 T 。

　　計算新解與當前解的差 DE。

　　如果新解比當前解優(DE > 0)，就用新解替換當前解。

　　否則以 exp(DE / T) 的概率用新解替換當前解。

溫度乘上一個小於1的係數，即降溫。

這樣，隨著溫度不斷降低，變化幅度也越來越小，接受一個更劣的解的概率也越來越小。

實現代碼：

#include<cstdio> #include<cctype> #include<cmath> #include<cstdlib>

int Read()
{
int x=0,y=1;
char c=getchar();
while(!isdigit(c))
{
if(c==-)
{
y=-1;
}
c=getchar();
}
while(isdigit(c))
{
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x*y;
}

struct Node
{
int x,y,weight;
}node[10005];
int n;

double potential_energy(double nowx,double nowy)
{
double sum=0;
for(int i=1;i<=n;i++)
{
double delx=nowx-node[i].x;
double dely=nowy-node[i].y;
sum+=(sqrt(delx*delx+dely*dely))*node[i].weight;
//物重一定，繩子越短，重物越低，勢能越小
//勢能又與物重成正比
}
return sum;//在(nowx,nowy)處的總勢能
}

double xans,yans;//最終答案
double ans=1e18+7,t;//勢能與溫度
const double delta=0.993;//降溫係數

void simulate_anneal()
{
double xx=xans;//欽定一個初始位置
double yy=yans;
t=1926;//t是溫度
while(t>1e-14)
{
double xtemp=xans+(rand()*2-RAND_MAX)*t;
double ytemp=yans+(rand()*2-RAND_MAX)*t;
//隨機一個新的坐標，變化幅度為t
//這裡要注意rand()和rand()*2-RAND_MAX的區別
//rand()的範圍是0~RAND_MAX-1
//rand()*2-RAND_MAX的範圍是-RAND_MAX到RAND_MAX-1

double new_ans=potential_energy(xtemp,ytemp);//計算當前解的勢能
double DE=new_ans-ans;
if(DE<0)//如果是一個更優解
{
xx=xtemp;
yy=ytemp;//就接受
xans=xx;
yans=yy;
ans=new_ans;
}
else if(exp(-DE/t)*RAND_MAX>rand())//能否接受這個差
{
//更新坐標
xx=xtemp;
yy=ytemp;
}
t*=delta;//降溫
}
}

void SA()//跑三次，總有一次是對的
{
simulate_anneal();
simulate_anneal();
simulate_anneal();
}

int main()
{
n=Read();
for(int i=1;i<=n;i++)
{
node[i].x=Read();
node[i].y=Read();
node[i].weight=Read();
}
SA();
printf("%.3lf %.3lf",xans,yans);
return 0;
}

小結：對於一些可能陷入局部最優的演算法，如果能與隨機化演算法相結合，有可能獲得較好的結果。

總結：就這樣吧~~~