【c++】算法设计与分析（保姆级！题目解析+答案）
算法类型
一. 分治法
可使用分治法求解的一些经典问题，可以在目录里看自己要哪些，都是先给代码，在说解析。
（1）二分搜索
（2）大整数乘法
（3）Strassen矩阵乘法
（4）棋盘覆盖
（5）归并排序
（6）快速排序
（7）线性时间选择
（8）最接近点对问题
（9）循环赛日程表
（10）汉诺塔
1. 二分搜索（太简单了，所以一定要会）
#include<iostream>usingnamespace std;#defineMAX10int a[MAX]={0,22,23,33,36,55,56,58,89,94};intSearch_two(int n){int left =0;int right = MAX-1;int mid =0;while(left<=right){ mid =(left+right)/2;if(n < a[mid]){ right = mid -1;}elseif(n > a[mid]){ left = mid +1;}elsereturn mid;}return-1;}intmain(){int searchN =0; cin>>searchN;int result =Search_two(searchN);if(result ==-1) cout <<"no find";else cout <<"yes,its "<<a[result]<<" in "<< result;return0;}思路：
第一遍：
第二遍：
2. 循环赛日程表（不如叫矩阵复制）
#include<iostream>#include<cmath>#defineMAX100int a[MAX][MAX]={0};usingnamespace std;voidCOPY(int tox,int toy,int fromx,int fromy,int r){for(int i =0; i<r ;i++){for(int j =0; j<r ; j++){ a[tox+i][toy+j]= a[fromx+i][fromy+j];}}}voidTable(int k){int n =pow(2,k);int i , j , r=0;for(i =0; i < n; i++){ a[0][i]=i+1;}for(r =1; r < n; r*=2){for(j =0; j< n; j = j +2* r){COPY(r,r+j,0,j,r);COPY(r,j,0,r+j,r);}}}intmain(){int k; cin>>k;int n =pow(2,k);Table(k);for(int i =0; i<n ; i++){for(int j =0; j<n ; j++){ cout<<a[i][j]<<" ";} cout<<endl;}return0;}思路：
赛程表满足一个规律：
左上角 右上角
左下角 右下角
可以发现对角的数值是相等的。
这里的COPY函数，可以看成互换函数，也就是把一个小矩阵里的四个数字互换：
交换的是左上右下和右上左下，
所以需要两个COPY函数：
COPY(r,r+j,0,j,r);
COPY(r,j,0,r+j,r);
可以看到第一个COPY复制的是左上角的。
3. 快速排序
#include<iostream>usingnamespace std;#defineMAX10int a[MAX]={37,89,23,58,36,55,56,22,34,9};voidquicksort(int start,int end){if(start < end){int left = start;int right = end;int temp = a[start];while(left < right){//从右边开始，要把右面小的换过去while(left < right && a[right]> temp){ right --;}//右面小了就交换 a[left]= a[right];while(left < right && a[left]< temp){ left ++;} a[right]= a[left];} a[left]= temp;quicksort(start,left-1);quicksort(right+1,end);}}intmain(){quicksort(0,9);//打印数组for(int i =0;i<10;i++){ cout<<a[i]; cout<<" ";}return0;}原理是：保留一个空位，找到那个我们选的数字在数组中的位置。
此时选择的数字左面的数字都比他小，右面的数都比他大。
接着递归左面的数字和右面的数字。
4. 斐波那契
#include<iostream>usingnamespace std;intf(int n){if(0== n)return0;if(1== n)return1;returnf(n-1)+f(n-2);}intmain(){int n; cout<<"cin n"; cin >> n;int re =f(n); cout<< re;return0;}二. 回溯
1. n皇后
代码如下：
#include<iostream>#include<cmath>usingnamespace std;int n;int pos[100];int totall;boolissafe(int r,int c){for(int i =0; i < r; i++)if(pos[i]== c ||abs(pos[i]- c)==abs(i - r))returnfalse;returntrue;}voiddfs(int r){if(r==n) totall++;for(int i =0; i < n;i++){if(issafe(r,i)){ pos[r]= i;dfs(r +1);}}}intmain(){ cout <<"Enter N: "; cin >> n; totall =0;dfs(0); cout <<"Total solutions for "<< n <<"-Queens: "<< totall << endl;return0;}原理：
1.我们首先要知道的数学知识：
横坐标之差的绝对值等于纵坐标之差的绝对值
abs(列差) == abs(行差)
假设有一个4*4的表格：
我们选取几个位置，
pos(2,2)和pos(3,3)，可以观察发现
行差：3-2=1
列差：3-2=1
pos(0,3)和pos(2,2)，可以观察发现
行差：2-0=2
列差：3-2=1
所以在n皇后的代码里，我们就可以这么判断是否在一条斜线上。abs(pos[i] - c) == abs(i - r)；
公式翻译过来就是：
|旧列 - 新列| == |旧行 - 新行|
2.代码解析
关键数组：pos[r] =c;这个数组很巧妙用了一个一维数组来记录了二维的棋盘，减少了空间的使用。例如pos[2]=3 表示在第三行的皇后在第四列。这里的pos[2] 是列，2是行。
为什么if(r==n)?
totall++;
是因为如果遍历完一次完整的棋盘，r就会等于n。
三.贪心算法
贪心算法就是每次取最好的结果。
所以首先都要排序，把结果好的放前面，开始遍历。
1. 背包问题
#include<iostream>#include<algorithm>usingnamespace std;typedefstructBOX{int id;float w;float v;float r;}BOX;boolcmp(BOX a,BOX b){return a.r > b.r;}voidbeibao(float weight,int n,BOX a[]){float sumvalue=0;for(int i=0; i<n ;i++){if(weight >0&& weight >= a[i].w){ weight = weight - a[i].w; sumvalue += a[i].r; cout<<"装入比例100%"<< endl;}else{float bili = weight / a[i].w ; sumvalue = sumvalue +(a[i].r * bili); cout<<"装入比例"<< bili << endl; weight =0;}} cout <<"总价值为"<<sumvalue<<endl;}intmain(){// === 这里是直接定义好的数据，想改就在这里改 ===// 1. 定义背包总容量float weight =50.0;// 2. 定义物品数据：{id, 重量, 价值, 0} // 注意：最后一个0是占位符，因为性价比r还没算，下面会自动算 BOX a[]={{1,30,60,0},// 这里的a[0]是占位用的，因为你的逻辑是从下标1开始{2,10,60,0},// 物品1：重10，值60{3,20,100,0},// 物品2：重20，值100{4,30,120,0}// 物品3：重30，值120};// 自动计算物品个数（减去第0个占位符）int n =sizeof(a)/sizeof(a[0]);// ============================================ cout <<"=== 背包问题自动运行 ==="<< endl; cout <<"背包总容量: "<< weight << endl; cout <<"物品总数: "<< n << endl << endl;// 自动计算性价比 rfor(int i =0; i < n; i++){ a[i].r = a[i].v / a[i].w;// 顺便打印一下初始数据，让你看清楚 cout <<"物品"<< a[i].id <<" -> 重量:"<< a[i].w <<" 价值:"<< a[i].v <<" 单价:"<< a[i].r << endl;} cout <<"----------------------"<< endl;// 排序sort(a,a+n,cmp);//beibaobeibao(weight,n,a);return0;}核心就是先排序再遍历，如果能装下全部就装，不能去全装下就取最多的能装下的装，所以贪心没办法用于0-1背包（也就是物品无法被”切开“的情况）
四. 动态规划
因为没办法用贪心解决0-1背包，所以用动态规划。
动态规划不同于递归，有点像把好的情况存起来，每次都比较放入新的好情况。
1. 0-1背包
//核心代码#include<iostream>#include<algorithm>#include<string>usingnamespace std;#defineMAX10int v[MAX];int dp[MAX][MAX];int w[MAX];intmain(){int n=3,c=5;int j = c;for(int i =1; i<=n;i++){for(j =0; j<= c ; j++){ dp[i][j]= dp[i-1][j];if(j >= w[i]){ dp[i][j]=max(dp[i][j], dp[i-1][j-w[i]]+ v[i]);}}} j = c;for(int i = n; i >=1; i--){if(dp[i][j]> dp[i-1][j]){ cout << i; j = j - w[i];}}return0;}//可运行代码#include<iostream>#include<algorithm>#include<string>// 引入string头文件，方便打印名字usingnamespace std;// 定义物品最大数量和背包最大容量，稍微开大一点constint MAX_N =100;constint MAX_C =1000;int w[MAX_N];// 重量int v[MAX_N];// 价值 string names[MAX_N];// 物品名字（为了让你看清楚选了啥）int dp[MAX_N][MAX_C];// DP表格intmain(){// === 这里直接写死你的例子 ===int n =3;// 物品数量int c =6;// 背包容量// 第1个物品：葡萄 (重量2, 价值3) names[1]="葡萄"; w[1]=2; v[1]=3;// 第2个物品：矿泉水 (重量3, 价值5) names[2]="矿泉水"; w[2]=3; v[2]=5;// 第3个物品：西瓜 (重量4, 价值6) names[3]="西瓜"; w[3]=4; v[3]=6;// ===========================// 核心算法部分for(int i =1; i <= n; i++){for(int j =0; j <= c; j++){ dp[i][j]= dp[i -1][j];if(j >= w[i]){ dp[i][j]=max(dp[i][j], dp[i -1][j - w[i]]+ v[i]);}}}// 输出结果 cout <<"=== 运行结果 ==="<< endl; cout <<"最大价值: "<< dp[n][c]<< endl; cout <<"选中物品: ";int j = c;for(int i = n; i >=1; i--){if(dp[i][j]> dp[i -1][j]){// 这里多打印了个名字，让你看得更清楚 cout << names[i]<<"("<< i <<") "; j = j - w[i];}} cout << endl;return0;}一句话解释就是，首先要考虑放不放的下，
如果放得下的话要考虑放他划算还是不放划算。
这也就是代码里的思想max( dp[i-1][j] , dp[i-1][j - w[i]] + v[i])
j是目前的最大容量。
i则表示当前的物品。所以i从1开始遍历。
j-w[i]就是目前的最大容量减去当前的物体的重量。
分辨的 前者是：没装他
后者是：装了他加上他的价值
值得注意的地方：这里的遍历i是从1开始的，因为这样在算i-1的时候就不会越界，所以下一题也是同理。
2. 最长公共子序列
//可运行代码#include<iostream>#include<algorithm>#include<string>// DP 数组稍微开大一点，防止越界#defineMAX100usingnamespace std;int dp[MAX][MAX];// 全局数组自动初始化为0，省心！intmain(){ string s1, s2;// 让我们输入两个字符串来测试一下！ cout <<"请输入第一个字符串: "; cin >> s1; cout <<"请输入第二个字符串: "; cin >> s2;int n = s1.length();// s1 的长度int m = s2.length();// s2 的长度（注意：两个字符串长度可能不一样！）// 核心逻辑开始！for(int i =1; i <= n; i++){for(int j =1; j <= m; j++)// 这里是 j <= m，不是 n 哦！{if(s1[i-1]== s2[j-1]){// ！！！一定要 +1 ！！！// 意思：在这个基础上，我们多凑出了一个相同的字符！ dp[i][j]= dp[i-1][j-1]+1;}else{// 没找到相同的？那就继承“前面最好的成绩”！ dp[i][j]=max(dp[i-1][j], dp[i][j-1]);}}} cout <<"最长公共子序列的长度是: "<< dp[n][m]<< endl;return0;}//简单代码intmain(){for(int i =1;i <= n; i++){for(int j =1; j <= n ; j++){if(s1[i-1]== s2[j-1]){ dp[i][j]= dp[i-1][j-1]+1;}else{ dp[i][j]=max(dp[i-1][j], dp[i][j-1]);}}}return0;}首先，要遍历两个字符串，
同时，判断尾巴上的字符一不一样，
如果一样：说明长度刚好就是（两个字符去掉尾巴+1）的长度
如果不一样：选择把s1的尾巴扔掉和s2的尾巴扔掉
所以有一个max（dp[i-1][j],dp[i][j-1]）
