编程算法集锦
一、分治法
1.分治法介绍
最大序列和问题：给出一个长度为n的序列A1 ，A2 ，A3 ，A4 ，……，An ，求最大序列连续和。换句话说，要求找到 1 ≤ i ≤ j ≤ n，使得Ai + Ai+1 + …… + Aj 尽量大。
#include<iostream>
using namespace std;
int maxsum(int* A,int x,int y){ // 返回数组在左闭右开区间[x,y)中最大连续和
/************ Begin ************/
int v,l,r,maxs;
if(y-x==1) return A[x]; //只有一个元素，直接返回
int m = x + (y-x)/2; //分治第一步，划分为[x,m)和[m,y)
maxs = max(maxsum(A,x,m),maxsum(A,m,y));//分治第二步：递归求解
v=0;l=A[m-1];
for(int i=m-1;i>=x;i--) l = max(l,v+=A[i]); // 分治第三步：合并（1）——从分界点开始往左的最大连续和L
v=0;r=A[m];
for(int i=m;i<y;i++) r = max(r,v+=A[i]);//分治第三步：合并（2）——从分界点往右的最大连续和R
return max(maxs,l+r);//把子问题的解L和R比较
/************ End ************/
}
int main(){
/************ Begin ************/
int n;
int A[1000];
cin>>n;
for(int i=0;i<n;i++){
cin>>A[i];
}
cout<<maxsum(A,0,n);
/************ End ************/
return 0;
}
测试样例：
4
4 1 -4 2
2.归并排序
归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
#include <iostream>
using namespace std;
void merge_sort(int *A,int x,int y,int *B){
// A 待排序数组；x 首索引；y 数组长度；B 附加空间
/********** Begin **********/
if(y-x>1)
{
int m=x+(y-x)/2;
int p=x,q=m,i=x;
merge_sort(A,x,m,B);
merge_sort(A,m,y,B);
while(p<m||q<y)
{
if(q>=y||(p<m&&A[p]<=A[q]))
B[i++]=A[p++];
else
B[i++]=A[q++];
}
for(int i=x;i<y;i++)
A[i]=B[i];
}
/********** Begin **********/
}
int main(){
/********** Begin **********/
int A[105],B[105],n;
cin>>n;
for(int i=0;i<n;i++)
cin>>A[i];
merge_sort(A,0,n,B);
for(int i=0;i<n;i++)
cout<<A[i]<<" ";
/********** Begin **********/
return 0;
}
测试样例：
4
3 1 2 4
3.快速排序
快速排序是最快的通用内部排序算法。它由 Hoare 于1962年提出，相对于归并排序来说，不仅速度更快，并且不需要辅助空间。按照分治三步法，将快速排序算法做如下介绍：
划分问题：把左右两部分，使得左边任意元素都小于或等于右边任意元素。
递归求解：把左右两部分分别排序。
合并问题：不用合并，因为此时数组已经完全有序。
#include<iostream>
using namespace std;
const int maxn=20000;
int a[maxn];
void qsort(int l, int r)
{
/*********** Begin **********/
if(l >= r)
return;
int i = l, j = r;
int key = a[r];
while(i < j) {
while(i < j && a[i] <= key)
i++;//此处比较数值与key大小必须是<=，不然a[i]==key的情况下，i不变就造成死循环。
a[j] = a[i];//若没有=，遇到1122这样(含等值的项)的序列在两个相等的数比较时会造成死循环
while(i < j && a[j] >= key)
j--;
a[i] = a[j];
}
a[i] = key;
qsort(i, r);
qsort(l, i-1);
/*********** End **********/
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
qsort(0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<' ';
cout<<endl;
return 0;
}
测试样例：
4
3 1 2 4
4.中值问题
输入n个整数和一个正整数k (1 ≤ k ≤ n)，输出这些整数从小到大排序后的第k个(例如，k=1就是最小值)。n≤107。快速排序的时间复杂度为：最坏情况O(n2)；平均情况O(nlogn)，但实践中几乎不可能达到最坏情况，效率非常高。根据快速排序思想，可以在平均O(n)时间内选出数组中第 k 小的元素。
#include<iostream>
using namespace std;
int Partition(int low, int high, int a[])
{
int temp = a[low];//基准点
if (low < high)
{
while (low < high)
{
while (low < high && temp <=a[high]) //从后往前找到第一个比基准点大的
high--;
if (low < high)
a[low] = a[high]; //放到基准点位置也就是第一个
while (low < high && a[low] <temp)//从前往后找到第一个比基准点小的
low++;
if (low < high)
a[high] = a[low];//放到high位置 即完成一对交换
}
a[low] = temp;//最后low位置放置基准点数值
}
return low;
}
int best_sort_k(int *A,int x,int y,int k){
/*
A 序列
x 首索引
y 末尾索引
k 找第几大的元素
*/
/********** Begin **********/
int tmp = Partition(x, y, A);
if (k-1==tmp-x) //刚好基准点在k-1位置
return A[tmp];
else if (k-1<tmp-x) //在前半部分找K大
return best_sort_k(A, x, tmp-1,k);
else
return best_sort_k(A, tmp + 1, y,k - (tmp-x)-1);
/********** End **********/
}
int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++) cin>>a[i];
int k,k_value;
cin>>k;
k_value=best_sort_k(a,0,n-1,k);
cout<<k_value<<endl;
return 0;
}
测试样例：
7
4 7 5 3 6 2 1
3
二、贪心法
1.贪心法
乘船问题: 给出 n 个人，第 i 个人重量为 wi。每艘船的最大载重量均为 C，且最多只能乘两个人。用最少的船装载所有人。有解输出船的个数，无解输出 “no”。
将人的重量按照从小到大排序。比j更重的人只能每人坐一艘船。这样，只需要两个下表i和j分别表示当前考虑的最轻的人和最重的人，每次先将j往左移动，直到i和j可以共坐一艘船，然后将i+1，j-1，并重复上述操作。
#include<iostream>
using namespace std;
const int maxn=10000;
void fast_sort(int *a,int begin,int end){
int l,r,m;
l=begin,r=end,m=(begin+end)>>1;
while(l<=r){
while(a[l]<a[m]) l++;
while(a[r]>a[m]) r--;
if(l<=r){
int t=a[l];
a[l]=a[r];
a[r]=t;
l++;
r--;
}
}
if(l<end) fast_sort(a,l,end);
if(begin<r) fast_sort(a,begin,r);
}
int main(){
int n,c;
int a[maxn];
/********** Begin **********/
cin>>n>>c;
for(int i=0;i<n;i++){
cin>>a[i];
}
fast_sort(a,0,n-1);
int p=0,q=n-1,s=0; // p代表左索引，q代表右索引
if(a[q]>c) cout<<"no"<<endl; // 如果最大的体重(最右边索引的人)大于船的最大载重，那么直接输出 no
else{
for(int i=0;i<n;i++){ // 遍历所有人
if(p>q) break;
if(a[p]+a[q]>c) q--; // 如果最小体重的人和当前最大的人不能同船，那么当前体重最大的人就要一个人一个船。
else p++,q--; // 当前体重最小的人和当前体重最大的人同船
s++;
}
cout<<s<<endl;
}
/********** End **********/
return 0;
}
测试样例：
10 85
5 84 85 80 84 83 55 77 6 11
2.最小生成树Kruskal算法
Kruskal算法是一种贪心算法的应用，首先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。
#include<bits/stdc++.h>
using namespace std;
int n,m;//n为节点总数，m为边数
int ans=0;//ans记录最小权值，
int k=0;//k记录已连接的边数
int fat[200010];//记录根节点
struct node//结构体储存边
{
int from,to,dis;
}edge[200010];
bool cmp(node a,node b)//sort排序 从小到大排列
{
return a.dis<b.dis;
}
int father(int x)//找根节点，并查集的查
{
if(fat[x]!=x)
return father(fat[x]);
else return x;
}
void unionn(int x,int y)//加入集合，并查集的并
{
fat[father(y)]=father(x);
}
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
{
cin>>edge[i].from>>edge[i].to>>edge[i].dis;
}
for(int i=1;i<=n;i++) //初始化 没加边之前 每个节点的根节点都是自己
{
fat[i]=i;
}
sort(edge+1,edge+1+m,cmp); //排序后，从最小的边开始，满足更新节点就加入集合
for(int i=1;i<=m;i++)
{
if(k==n-1) break;//连接n个点需要n-1条边
if(father(edge[i].from)!=father(edge[i].to))//节点是否更新
{
unionn(edge[i].from,edge[i].to);//加入集合
ans+=edge[i].dis;//加上权值
k++;//边数加1
}
}
cout<<ans;
return 0;
}
测试样例：
10 6
1 3 1
1 2 6
1 4 5
2 3 5
2 5 3
3 5 6
5 6 6
3 4 5
3 6 4
4 6 2
3.Huffman编码
哈夫曼（Huffman）编码算法是基于二叉树构建编码压缩结构的，它是数据压缩中经典的一种算法。算法根据文本字符出现的频率，重新对字符进行编码。因为为了缩短编码的长度，我们自然希望频率越高的词，编码越短，这样最终才能最大化压缩存储文本数据的空间。实现如下：
⑴ 初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1，T2，…，Tn}；
⑵ 选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；
⑶ 删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中；
⑷ 重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。
#include<bits/stdc++.h>
using namespace std;
typedef struct//哈夫曼树的存储表示
{
char s;
int weight; //权值
int parent, lChild, rChild; //双亲及左右孩子的下标
}HTNode, *HuffmanTree;
void Select(HuffmanTree hT, int n, int &s1, int &s2)//选择两个最小节点
{
s1 = s2 = 0;
int i;
for(i = 1; i < n; ++ i)//选择两个未有双亲的节点
{
if(hT[i].parent == 0)
{
if(0 == s1)
{
s1 = i;
}
else
{
s2 = i;
break;//后面一个for循环的标记
}
}
}
if(hT[s1].weight > hT[s2].weight)//确保s1>s2
{
int t = s1;
s1 = s2;
s2 = t;
}
for(i+=1;i<n;++i)//选择s2即break 故从i+1开始选择两个最小节点
{
if(hT[i].parent==0)
{
if(hT[i].weight < hT[s1].weight)
{
s2 = s1;
s1 = i;
}
else if(hT[i].weight < hT[s2].weight)
{
s2 = i;
}
}
}
//cout<<s1<<" "<<s2<<"**"<<endl;
}
void CreateHufmanTree(HuffmanTree &hT)//构造哈夫曼树
{
int n,m;
cin>>n;
m = 2*n - 1;
hT = new HTNode[m + 1];
hT[0].weight=m; // 0号节点用来记录节点数量
for(int i = 1; i <= m; ++ i)
{
hT[i].parent = hT[i].lChild = hT[i].rChild = 0;//初始化
}
for(int i = 1; i <= n; ++ i)
{
cin >>hT[i].s>>hT[i].weight; // 输入权值
}
for(int i = n + 1; i <= m; ++ i)//建立过程
{
int s1, s2;
Select(hT, i, s1, s2);
hT[s1].parent = hT[s2].parent = i;
hT[i].lChild = s1; hT[i].rChild = s2; //作为新节点的孩子
hT[i].weight = hT[s1].weight + hT[s2].weight; //新节点为左右孩子节点权值之和
}
}
int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth)//递归计算WPL
{
if(hT[i].lChild == 0 && hT[i].rChild == 0)
{
return hT[i].weight * deepth;
}
else
{
return HuffmanTreeWPL_(hT, hT[i].lChild, deepth + 1) + HuffmanTreeWPL_(hT, hT[i].rChild, deepth + 1);
}
}
int HuffmanTreeWPL(HuffmanTree hT)//计算WPL
{
return HuffmanTreeWPL_(hT, hT[0].weight, 0);
}
void DestoryHuffmanTree(HuffmanTree &hT)//销毁哈夫曼树
{
delete[] hT;
hT = NULL;
}
int main()
{
HuffmanTree hT;
CreateHufmanTree(hT);
cout << HuffmanTreeWPL(hT) << endl;
DestoryHuffmanTree(hT);
return 0;
}
测试样例：
6
a 45
b 13
c 12
d 16
e 9
f 5
4.单源点最短路径
Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T
1.初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
2.从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点，
3.继续从dis数组选择最小值，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
4.重复上述动作，直到T中包含了图的所有顶点。
#include<iostream>
using namespace std;
/********** Begin **********/
#define N 100
#define Min(a,b) a>b?b:a
#define INF 1000
int dis[N], bj[N];
int mp[N][N];
int n;
void djsk(int v, char** names)
{
int i, j, k, min;
for (i = 0; i < n; i++)
dis[i] = mp[v][i];//初始化dis数组,代表从起始点到i点的最短距离
dis[v] = 0;// v 代表起始节点 自己到自己为0
bj[v] = 1;// 标记 已找到短路
cout << names[0] << " " << dis[0] << endl;
for (i = 0; i < n; i++)// i 代表已经找到的最短路条数
{
min = INF; k = 0;
for (j = 0; j < n; j++)//从未找到最短路径元素中找一个路径最短的
if (!bj[j] && dis[j] < min) { min = dis[j], k = j; }
if (k != 0)
cout << names[k] << " " << dis[k] << endl;
bj[k] = 1;// 标记 已找到短路
for (j = 0; j < n; j++)//用但前最短路节点更新未找到最短路的节点
if (dis[j] > (dis[k] + mp[k][j]))dis[j] = dis[k] + mp[k][j];
}
}
/********** End **********/
int main(){
/********** Begin **********/
cin >> n;
char** names = new char* [5];
char from[3], to[3];
int len;
for (int i = 0; i < 5; i++) {
names[i] = new char[5];
names[i][0] = 'v';
names[i][1] = (i + 1) + '0';
names[i][2] = 0;
dis[i] = INF;
for (int j = 0; j < 5; j++) {
mp[i][j] = INF;
}
}
fflush(stdin);
for (int i = 0; i < n; i++) {
cin >> from;
cin >> to;
cin >> len;
mp[from[1] - '0' - 1][to[1] - '0' - 1] = len;
mp[to[1] - '0' - 1][from[1] - '0' - 1] = len;
}
n = 5;
djsk(0, names);
for (int i = 0; i < 5; i++) {
delete[] names[i];
}
delete[] names;
/********** End **********/
return 0;
}
测试样例：
7
v1 v2 10
v2 v3 50
v3 v4 20
v3 v5 10
v4 v5 60
v1 v5 100
v1 v4 30
三、回溯法
1.回溯法-n皇后问题
八皇后问题：在8x8的棋盘上放置八个皇后，使得它们互不攻击，此时每个皇后的攻击的攻击范围为同行同列和同对角线，要求找出所有解。
n皇后问题：在棋盘上nxn的棋盘上放置n个皇后，使它们互不攻击，找出所有解。
#include<iostream>
#include<math.h>
using namespace std;
const int M = 100;
int N;
int queenPos[M];//存放皇后的摆放位置
int sum = 0;//记一共有多少种解决方案
void NQueen(int k)
{
int i;
if (k == N)//N个皇后已经全部摆好
{
sum++;
return;
}
for (i = 0; i < N; i++)//在一行中逐个检测每个位置
{
int j;
for (j = 0; j < k; j++)//和语句摆好的前几个皇后进行冲突检测
{
if (queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j))
{
break;//发生冲突，则检测下一个位置
}
}
if (j == k)//该位置不与前面的皇后发生冲突
{
queenPos[k] = i;//将第k个皇后放在第i的位置上
NQueen(k + 1);
}
}
}
int main()
{
cin >> N;
NQueen(0);//摆放第0个皇后
cout<<sum<<endl;;
return 0;
}
测试样例：
8
2.子集和数
已知n个不重复的正数：wi，1 ≤ i ≤ n, 和M，要求找出wi的所有子集使得子集内元素之和等于M。
#include<iostream>
using namespace std;
class SubsetSum {
private:
int n, * s, * x, m;
bool b = false;
public:
SubsetSum(int N, int M);
void backtrack(int k, int sum);
void showY();
void showN();
~SubsetSum();
};
SubsetSum::SubsetSum(int N, int M)
{
int i, j;
n = N;
m = M;
s = new int[n];
for (i = 0; i < n; i++)
cin >> s[i];
x = new int[n];
}
void SubsetSum::backtrack(int k, int sum)
{
if (k >= n)
{
if (sum == m)
{
b = true;
showY();
}
return;
}
for (int i = 0; i <= 1; i++)
{
x[k] = i;
//if (sum + s[k] * i <= m)
backtrack(k + 1, sum + s[k] * i);
}
}
void SubsetSum::showY()
{
for (int i = 0; i < n; i++)
if (x[i])
cout << s[i] << " ";
cout << endl;
}
void SubsetSum::showN()
{
if (!b)
cout << "No Solution" << endl;
}
SubsetSum::~SubsetSum()
{
delete[] s;
delete[] x;
}
int main()
{
int n, m;
cin >> n >> m;
SubsetSum s(n, m);
s.backtrack(0, 0);
s.showN();
return 0;
}
测试样例：
10 7
1 3 6 2 5 4 -1 9 7 10
四、动态规划
1.数塔问题
求上图从顶层到底层的一个路径，使路径上的数字和最大。要求输出最大的数字和max和数值和最大的路径。
#include <stdio.h>
/********** Begin **********/
int main()
{
int n = 5;
int towel[5][5] = { {9}, {12, 15}, {10, 6, 8}, {2, 18, 9 , 5},{19, 7, 10, 4, 16} };
int res[5][5] = { {9}, {12, 15}, {10, 6, 8}, {2, 18, 9 , 5},{19, 7, 10, 4, 16} };
for (int i = n-2; i >=0; i--) {
for (int j = 0; j <= i; j++) {
int left = res[i][j] + res[i + 1][j];
int right = res[i][j] + res[i + 1][j+1];
res[i][j] = left > right ? left : right;
}
}
int max ;
int mIndex = 0;
printf("max=%d\n", res[0][0]);
for (int i = 0; i < n-1; i++) {
max = res[i][0];
mIndex = 0;
for (int j = 1; j <= i; j++) {
if (res[i][j] > max) {
max = res[i][j];
mIndex = j;
}
}
res[n - 1][i] = towel[i][mIndex];
}
res[n - 1][n - 1] = res[n - 2][mIndex] - res[n - 1][n - 2];
printf("数值和最大的路径是：");
for (int i = 0; i < n; i++) {
printf("%d", res[n - 1][i]);
if (i != n - 1) {
printf("->");
}
else {
printf("\n");
}
}
}
/********** End **********/
2.最长公共子序列
求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列。
#include<stdio.h>
#include<string.h>
/********** Begin **********/
char *longestSubsequence(char *p, int lenP, char *q, int lenQ) {
char ch[100];
int i = 0, j = 0, k = 0;
while (i < lenP && j < lenQ) {
if (p[i] == q[j]) {
ch[k++] = p[i];
i++;
j++;
} else if (j + 1 < lenP && q[j + 1] == p[i]) {
j++;
} else if (i + 1 < lenP && p[i + 1] == q[j]) {
i++;
} else {
i++;
j++;
}
}
ch[k] = 0;
printf("%s\n", ch);
}
int main() {
char a[] = { 'A', 'B', 'C', 'D', 'B', 'A', 'B' };
char b[] = { 'B', 'D', 'C', 'A', 'B', 'A' };
longestSubsequence(a, 7, b, 6);
return 0;
}
/********** End **********/
3.求序列-2 11 -4 13 -5 -2的最大字段和
#include <stdio.h>
/********** Begin **********/
#define N 100
int Sum(int a[], int len)
{
int maxsum, maxhere;
maxsum = maxhere = a[0]; //初始化最大和为a【0】
for (int i = 1; i < len; i++) {
if (maxhere <= 0)
maxhere = a[i]; //如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为a[i]
else
maxhere += a[i]; //如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和
if (maxhere > maxsum) {
maxsum = maxhere; //比较当前和和已存储和并更新
}
}
return maxsum;
}
int main()
{
int a[] = { -2, 11, -4, 13, -5, -2 };
int res = Sum(a, 6);
printf("%d\n", res);
return 0;
}
/********** End **********/
4.求最长的单调递增子序列长度
给定一个长度为n的数组，找出一个最长的单调递增子序列（不一定连续，但是顺序不能乱）。
#include <stdio.h>
/********** Begin **********/
int main()
{
int n;
int a[10];
int dp[10] = { 0 };
int ans;
int prenum, maxnum;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
dp[i] = 0;
scanf("%d", &a[i]);
}
dp[0] = 1;
prenum = maxnum = a[0];
ans = dp[0];
for(int i =1;i<n;i++){
for (int j = 0; j < i; j++) {
if (a[i] > a[j]) {
dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
}
}
ans = ans > dp[i] ? ans : dp[i];
}
printf("%d\n", ans);
return 0;
}
/********** End **********/
测试样例：
10
3 18 7 14 10 12 23 41 16 24
5.矩阵连乘问题
乘法次数：若A 是p × q 矩阵，B 是 q × r 矩阵，则A ×B 的代价是p x q x r 。因为矩阵乘法满足结合律，因此矩阵连乘可以由不同的计算次序，这种计算次序可以用加括号来表示。求这矩阵连乘的最小相乘次数。
#include <iostream>
using namespace std;
/********** Begin **********/
int RecurMatrixChain(int i, int j, int** s, int* p);//递归求最优解
void Traceback(int i, int j, int** s);//构造最优解
int main()
{
int n;
cin >> n;
int* p = new int[n + 1];
int** s = new int* [n + 1];
for (int i = 1; i <= n; i++)
{
s[i] = new int[n + 1];
cin >> p[i - 1] >> p[i];
}
cout << "m[1][" << n <<"]=" << RecurMatrixChain(1, n, s, p) << endl;
//cout << "矩阵最优计算次序为：" << endl;
//Traceback(1, 6, s);
return 0;
}
int RecurMatrixChain(int i, int j, int** s, int* p)
{
if (i == j) return 0;
int u = RecurMatrixChain(i, i, s, p) + RecurMatrixChain(i + 1, j, s, p) + p[i - 1] * p[i] * p[j];
s[i][j] = i;
for (int k = i + 1; k < j; k++)
{
int t = RecurMatrixChain(i, k, s, p) + RecurMatrixChain(k + 1, j, s, p) + p[i - 1] * p[k] * p[j];
if (t < u)
{
u = t;
s[i][j] = k;
}
}
return u;
}
void Traceback(int i, int j, int** s)
{
if (i == j) return;
Traceback(i, s[i][j], s);
Traceback(s[i][j] + 1, j, s);
cout << "Multiply A" << i << "," << s[i][j];
cout << " and A" << (s[i][j] + 1) << "," << j << endl;
}
/********** End **********/
测试样例：
6
30 35
35 15
15 5
5 10
10 20
20 25
五、分支界限法
1.0/1背包问题
0-1背包问题：给定n种物品和一背包。物品i的重量是wi， 其价值为Vi， 背包的容量为C。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
#include <iostream>
using namespace std;
int maxSize=0;
/********** Begin **********/
void backtrack(int * weights, int * values, int sum, int value, int totalCapacity, int index, int num){
if(value >maxSize){
maxSize = value;
}
if (index>=num) {
return;
}
for (int i = 0; i <= 1; i++) {
if(sum + weights[index]*i <= totalCapacity){
backtrack(weights, values, sum + weights[index] * i, value + values[index] * i, totalCapacity, index + 1, num);
}
}
}
/********** End **********/
int main() {
/********** Begin **********/
int n;
int capacity;
cin >> n;
cin >> capacity;
int* weights = new int[n];
int* values = new int[n];
for (int i = 0; i < n; i++) {
cin >> weights[i];
cin >> values[i];
}
backtrack(weights, values, 0, 0, capacity, 0, n);
cout << maxSize << endl;
delete[] weights;
delete[] values;
/********** Begin **********/
return 0;
}
测试样例：
10 34
2 15
8 25
4 9
4 9
8 15
7 12
8 12
5 6
16 14
16 9
2.旅行商问题
某售货员要到若干城市去推销商品，已知各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。
#include <iostream>
#define NO_PATH -1 //没有通路
#define MAX_WEIGHT 4000
using namespace std;
/********** Begin **********/
// 函数，全局变量，结构体等
int N; //城市数目
int City_Graph[100][100]; //保存图信息
int x[100]; //x[i]保存第i步遍历的城市
int isIn[100]; //保存 城市i是否已经加入路径
int bestw; //最优路径总权值
int cw; //当前路径总权值
int bestx[100]; //最优路径
void Travel_Backtrack(int t){ //递归法
int i,j;
if(t>N){ //走完了，输出结果
if(cw < bestw){ //判断当前路径是否是更优解
for (i=1;i<=N;i++){
bestx[i] = x[i];
}
bestw = cw+City_Graph[x[N]][1];
}
return;
}
else{
for(j=1;j<=N;j++){ //找到第t步能走的城市
if(City_Graph[x[t-1]][j] != NO_PATH && !isIn[j]){ //能到而且没有加入到路径中
isIn[j] = 1;
x[t] = j;
cw += City_Graph[x[t-1]][j];
Travel_Backtrack(t+1);
isIn[j] = 0;
x[t] = 0;
cw -= City_Graph[x[t-1]][j];
}
}
}
}
/********** End **********/
int main(){
/********** Begin **********/
int i;
cin>>N;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
cin>>City_Graph[i][j];
}
}
//测试递归法
for (i=1;i<=N;i++){
x[i] = 0; //表示第i步还没有解
bestx[i] = 0; //还没有最优解
isIn[i] = 0; //表示第i个城市还没有加入到路径中
}
x[1] = 1; //第一步 走城市1
isIn[1] = 1; //第一个城市 加入路径
bestw = MAX_WEIGHT;
cw = 0;
Travel_Backtrack(2); //从第二步开始选择城市
cout<<"最优值为:"<<bestw;
cout<<"最优解为:";
for(i=1;i<=N;i++){
cout<<bestx[i];
}
cout<<endl;
/********** End **********/
return 0;
}
测试样例：
4
-1 30 6 4
30 -1 5 10
6 5 -1 20
4 10 20 -1
六、其他典型算法
1.DFS与BFS
#include<iostream>
#include<string.h>
using namespace std;
/********** Begin **********/
// 定义全局变量，结构体，函数等
struct TNode {
int data;
TNode* left;
TNode* right;
};
TNode* newnode()
{
TNode * node = (TNode*)malloc(sizeof(TNode));
node->data = -1;
node->left = NULL;
node->right = NULL;
return node;
}
char s[500];
void addnode(TNode* root, int value, char* instruct) {
int index = 0;
TNode* node = root;
while (instruct[index] != ')') {
if (instruct[index] == 'L') {
if(node->left == NULL)
node->left = newnode();
node = node->left;
}
if (instruct[index] == 'R') {
if (node->right == NULL)
node->right = newnode();
node = node->right;
}
index++;
}
node->data = value;
}
bool input(TNode* root){
bool failed=false;
while(true){
if(scanf("%s",s)!=1) return false;
if(!strcmp(s,"()")) break; // 两个字符穿相同对于零
int v;
sscanf(&s[1],"%d",&v);
addnode(root,v,strchr(s,',')+1);
}
return true;
}
void BFS(TNode* root) {
TNode* queue[100];
TNode* p;
int front = 0, rear = 0;
queue[front++] = root;
while (front != rear) {
p = queue[rear++];
printf("%d", p->data);
if (p->data == -1)
return;
if (p->left != NULL) {
queue[front++] = p->left;
}
if (p->right != NULL) {
queue[front++] = p->right;
}
if (front != rear) {
printf(" ");
}
}
printf("\n-1\n");
}
/********** End **********/
int main(){
TNode * root = newnode();
bool a = input(root);
BFS(root);
return 0;
}
测试样例：
(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
2.求第k小个元素
输入n个整数和一个正整数k (1 ≤ k ≤ n)，输出这些整数从小到大排序后的第k个(例如，k=1就是最小值)。n≤107。快速排序的时间复杂度为：最坏情况O(n2)；平均情况O(nlogn)，但实践中几乎不可能达到最坏情况，效率非常高。根据快速排序思想，可以在平均O(n)时间内选出数组中第 k 小的元素。
#include<iostream>
using namespace std;
int partition(int* A, int low, int high) {
int temp = A[low];
int i = low;
int j = high;
while (i < j) {
while (i < j && A[j] > temp)j--;
if (i < j) { A[i] = A[j]; i++; }
while (i < j && A[i] < temp)i++;
if (i < j) { A[j] = A[i]; j--; }
}
A[i] = temp;
return i;
}
int best_sort_k(int *A,int x,int y,int k){
/*
A 序列
x 首索引
y 末尾索引
k 找第几大的元素
*/
/********** Begin **********/
int i = partition(A, x, y);
if (i == k - 1) {
return A[i];
}
else if (i < k - 1) {
return best_sort_k(A, i + 1, y, k);
}
else{
return best_sort_k(A, x, i - 1, k);
}
/********** End **********/
}
int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++) cin>>a[i];
int k,k_value;
cin>>k;
k_value=best_sort_k(a,0,n-1,k);
cout<<k_value<<endl;
return 0;
}
测试样例：
7
4 7 5 3 6 2 1
3
3.约瑟夫斯问题
有n个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了n和k，一开始要站在什么地方才能避免被处决？
#include<iostream>
using namespace std;
/********** Begin **********/
// 定义全局变量，结构体，函数等
struct Node {
int data;
Node* next;
Node* pre;
};
Node* createCycleList()
{
Node* root = (Node*)malloc(sizeof(Node));
root->next = root;
root->pre = root;
return root;
}
void insert(Node* root, Node* node) {
Node* pre = root->pre;
pre->next = node;
node->next = root;
root->pre = node;
node->pre = pre;
}
void travel(Node* root) {
Node* p = root;
if (p == NULL)
return;
do {
printf("%d ", p->data);
p = p->next;
} while (p != root);
}
Node* Joesseff(Node* root, int step) {
Node* p = root;
Node* q;
if (p == NULL)
return NULL;
while (p->next != p) {
for (int i = 0; i < step; i++)
{
p = p->next;
}
q = p->next;
p->pre->next = p->next;
p->next->pre = p->pre;
free(p);
p = q;
}
return p;
}
void freeCycleList(Node* root) {
Node* pre = root->pre;
pre->next = NULL;
while (root != NULL) {
pre = root;
root = root->next;
free(pre);
}
}
/********** End **********/
int main(){
/********** Begin **********/
Node* root = (Node*)malloc(sizeof(Node));
int n, step;
cin >> n;
cin >> step;
root->data = 1;
root->next = root;
root->pre = root;
for (int i = 2; i <= n; i++) {
Node * node = (Node*)malloc(sizeof(Node));
node->data = i;
insert(root, node);
}
root = Joesseff(root, step);
cout << root->data;
/********** End **********/
freeCycleList(root);
return 0;
}
测试样例：
10 3
4.开散列与闭散列
闭散列方法：遇到哈希冲突时，从遇到冲突的位置起向后寻找空位，找到空位就将数据插入。
开散列方法：又叫链地址法，先用哈希函数计算每个数据的散列地址，把具有相同地址的元素归于同一个集合之中，把该集合处理为一个链表，链表的头节点存储于哈希表之中。
#include<iostream>
using namespace std;
enum kind{Active,Empty,Deleted};
class ArrayHashTable{//闭散列法
public:
ArrayHashTable(const int d,int sz=20){
tableSize=sz;
divitor=d;
table=new int[tableSize];
info=new kind[tableSize];
for(int i=0;i<tableSize;i++){
table[i]=0;
info[i]=Empty;
}
}
~ArrayHashTable(){
delete[] table;
delete[] info;
}
bool findPos(int k,int &i){//寻找k关键码所在位置i
i=k%divitor;
int j=i;
do{
if(info[i]==Active&&table[i]==k)
return true;
if(info[i]==Empty)
return false;
i=(i+1)%tableSize;
}
while(j!=i);
return false;
}
bool insert(int k){//插入关键码k
int i;
if(findPos(k,i))
return false;
if(info[i]!=Active){
table[i]=k;
info[i]=Active;
return true;
}else
return false;
}
bool remove(int k){//删除关键码k
int i;
if(!findPos(k,i))
return false;
table[i]=Deleted;
return true;
}
int *getArray(){
return table;
}
private:
int divitor;
int tableSize;
int *table;
kind *info;
};
class Node{
public:
int data;
Node *next;
Node(int d,Node *n=NULL){
data=d;
next=n;
}
};
class LinkedHashTable{//开散列法
public:
LinkedHashTable(int d,int sz=20){
tableSize=sz;
divitor=d;
hs=new Node*[sz];
for(int i=0;i<sz;i++)
hs[i]=new Node(0);
}
~LinkedHashTable(){
delete []hs;
}
bool findPos(int k,Node *&p,Node *&last){
int i=k%divitor;
last=hs[i];
p=hs[i]->next;
while(p!=NULL&&p->data!=k){
p=p->next;
last=last->next;
}
if(p!=NULL&&p->data==k)
return true;
else
return false;
}
bool insert(int k){
Node *p,*last;
int i=k%divitor;
if(findPos(k,p,last))
return false;
last->next=new Node(k);
return true;
}
bool remove(int k){
Node *p,*last;
if(!findPos(k,p,last))
return false;
last->next=p->next;
return true;
}
Node **getArray(){
return hs;
}
private:
int divitor;
int tableSize;
Node **hs;
};
void test(Node *&q){
q=new Node(4);
}
int main(){
//闭散列法
ArrayHashTable *hs=new ArrayHashTable(11,12);
int a[8];
int a2[8];
int len = 0;
for(int i=0;i<8;i++){
cin>>a[i];
a2[i]=a[i];
len++;
// cin>>a2[i];
}
cout<<"闭散列方法\n";
// int a[]={37,25,14,36,49,68,57,11};
/********** Begin **********/
for (int i = 0; i < len; i++) {
hs->insert(a[i]);
}
int* arr = hs->getArray();
for (int i = 0; i < 12; i++) {
cout << arr[i] << " ";
}
cout << endl;
delete hs;
/********** End **********/
cout<<"开散列方法\n";
// //开散列法
/********** Begin **********/
LinkedHashTable* lht = new LinkedHashTable(11, 12);
for (int i = 0; i < len; i++) {
lht->insert(a2[i]);
}
Node** table = lht->getArray();
/********** Begin **********/
for (int i = 0; i < 12; i++) {
Node* node = table[i]->next;
while (node) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
delete lht;
/********** End **********/
return 0;
}
测试样例：
37 25 14 36 49 68 57 11