编程算法集锦

article/2025/1/16 18:05:55

编程算法集锦

  • 一、分治法
    • 1.分治法介绍
    • 2.归并排序
    • 3.快速排序
    • 4.中值问题
  • 二、贪心法
    • 1.贪心法
    • 2.最小生成树Kruskal算法
    • 3.Huffman编码
    • 4.单源点最短路径
  • 三、回溯法
    • 1.回溯法-n皇后问题
    • 2.子集和数
  • 四、动态规划
    • 1.数塔问题
    • 2.最长公共子序列
    • 3.求序列-2 11 -4 13 -5 -2的最大字段和
    • 4.求最长的单调递增子序列长度
    • 5.矩阵连乘问题
  • 五、分支界限法
    • 1.0/1背包问题
    • 2.旅行商问题
  • 六、其他典型算法
    • 1.DFS与BFS
    • 2.求第k小个元素
    • 3.约瑟夫斯问题
    • 4.开散列与闭散列

一、分治法

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）——从分界点开始往左的最大连续和Lv=0;r=A[m];for(int i=m;i<y;i++) r = max(r,v+=A[i]);//分治第三步：合并（2）——从分界点往右的最大连续和Rreturn 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++];elseB[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);elsereturn 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;  // 如果最大的体重(最右边索引的人)大于船的最大载重，那么直接输出 noelse{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 100int 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]  elsemaxhere += 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 4000using 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;                   //第一步 走城市1isIn[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关键码所在位置ii=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){//插入关键码kint i;if(findPos(k,i))return false;if(info[i]!=Active){table[i]=k;info[i]=Active;return true;}elsereturn false;}bool remove(int k){//删除关键码kint 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;elsereturn 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

http://chatgpt.dhexx.cn/article/eGKuvu8t.shtml

相关文章

富文本的使用 NSMutableAttributedString

富文本的使用 NSMutableAttributedString

文章内容大纲 1、NSMutableAttributedString的基本使用2、NSMutableAttributedString的简易封装3、使用开源代码GOBMarkupPaser处理富文本4、UITextKit简介5、编程思想的相关思考 前言 富文本使用案例&#xff1a; 这里我自己也用了富文本实现了简单的却也是常用的例子&#x…
阅读更多...
iOS 开发 富文本

iOS 开发 富文本

http://www.itnose.net/detail/6177538.html 文章内容大纲 1、NSMutableAttributedString的基本使用2、NSMutableAttributedString的简易封装3、使用开源代码GOBMarkupPaser处理富文本4、UITextKit简介5、编程思想的相关思考 前言 富文本使用案例&#xff1a; 这里我自己也用…
阅读更多...
软工第三次作业-结对编程

软工第三次作业-结对编程

结对项目-最长英语单词链 哈哈&#xff0c;这次记住了&#xff0c;来&#xff0c;初始化&#xff01; 项目内容这个作业属于哪个课程2023年北航敏捷软件工程社区这个作业的要求在哪里结对项目-最长英语单词链我在这个课程的目标是学习软件开发的原则、方法&#xff0c;并对敏捷…
阅读更多...
Python基础编程习题

Python基础编程习题

警察局抓了a&#xff0c;b&#xff0c;c&#xff0c;d四名偷窃嫌疑犯&#xff0c;其中只有一人是小偷。审问中 a说&#xff1a;“我不是小偷。” b说&#xff1a;“c是小偷。” c说&#xff1a;“小偷肯定是d。” d说&#xff1a;“c在冤枉人。” 现在已经知道四个人中三人说的…
阅读更多...
四面体的表面积_如何求正四面体的体积和表面积？

四面体的表面积_如何求正四面体的体积和表面积？

当正四面体的棱长为a时&#xff0c;体积&#xff1a;√2a/12&#xff0c;表面积√3a^2。 解答过程如下&#xff1a; 正四面体是由四个全等的正三角形所组成的几何体。它有四个面、四个顶点、六条棱。每个二面角均为7032’&#xff0c;有四个三面角&#xff0c;每个三面角的面角…
阅读更多...
空间四面体的面积、体积运算

空间四面体的面积、体积运算

基于C#窗体应用程序。通过添加控件&#xff08;Button、Label、TextBox&#xff09;来实现相应的功能。 目录 一、界面设计 二、编写代码 1、计算体积 2、计算面积 三、编译调试 四、实现效果 一、界面设计 二、编写代码 1、计算体积 double A1, A2, A3, A4, value; A…
阅读更多...
四面体体积求法

四面体体积求法

四面体&#xff08;三棱锥&#xff09;体积 &#xff1a; 设 有&#xff1a; 不过这是有向的。如果知道那四个顶点&#xff0c;用这个公式即可求出体积。 如果不知道四点仅知道6条边长&#xff0c;就得用下面的方法——欧拉四面体公式 写成行列式&#xff1a; 那么有&…
阅读更多...
matlab 四面体体积

matlab 四面体体积

计算方法&#xff1a; 已知四面体顶点坐标分别为 (x1,y1,z1)&#xff0c; (x2,y2,z2)&#xff0c; (x3,y3,z3)&#xff0c; (x4,y4,z4)&#xff0c; 可以通过如下两种方法求四面体体积&#xff1a; 1. 利用向量的混和积 过一顶点的三向量设为a&#xff0c;b&#xff0c;…
阅读更多...
C++：使用类方法根据四点计算四面体体积

C++：使用类方法根据四点计算四面体体积

一个四面体有四个点&#xff0c;分别为a (x1, y1, z1), b (x2, y2, z2), c (x3, y3, z3), 以及d (x4, y4, z4)&#xff0c;计算该四面体的体积。 &#xff08;1&#xff09;四面体计算公式 &#xff08;2&#xff09;三维空间的两点的点乘 &#xff0…
阅读更多...
【HDU1411】四面体的体积公式

【HDU1411】四面体的体积公式

1.题目链接。题目大意&#xff1a;就是给出一个四面体的六条边&#xff0c;求出这个四面体的体积。 2.这个&#xff0c;如果知道坐标是很好解决的&#xff0c;假设我们知道的是坐标&#xff1a; 体积就是混合积的六分之一。&#xff08;什么&#xff1f;x,y,z是啥&#xff1f;…
阅读更多...
tomcat7安装版的详细步骤

tomcat7安装版的详细步骤

如图&#xff1a;直接双击tomcat安装包进入安装流程。 出现安装界面&#xff0c;点击“next”下一步继续。 在这个界面点击i aggress &#xff0c;“我同意”继续下一步。 当出现这个界面的时候&#xff0c;不要做任何修改&#xff0c;直接点击下一步继续。 在这个界面…
阅读更多...
tomcat7.0安装及配置教程(win10)

tomcat7.0安装及配置教程(win10)

一、前言 Tomcat 服务器是一个开源的轻量级Web应用服务器&#xff0c;在中小型系统和并发量小的场合下被普遍使用&#xff0c;是开发和调试Servlet、JSP 程序的首选。 二、安装前准备 1.确保安装过jdk&#xff0c;安装过可跳过。 如果没有安装可以参考本人另外写的博文win1…
阅读更多...
Tomcat7.0的安装及配置

Tomcat7.0的安装及配置

本篇文章集合网上的零散经验加上2次实践整合&#xff0c;主要为大家提供如何正确使用Tomcat方法。本人安装的是7.0.77版本。 所需软件&#xff1a; JDK6.0/7.0 Tomcat 7.0 步骤&#xff1a; 1.安装JDK&#xff0c;配置好环境变量&#xff1a;JAVA_HOME、Classpath、Path 2…
阅读更多...
win10安装tomcat7的安装与配置【详细教程】

win10安装tomcat7的安装与配置【详细教程】

1、tomcat传送门&#xff0c;群文件自取&#xff1b;群号&#xff1a;708072830 2、下载解压之后&#xff0c;先安装好tomcat 第一步&#xff1a; 在Tomcat bin路径下 找到 startup.bat 双击 打开&#xff0c;闪退表示 安装或者配置 失败&#xff1b;如下&#xff1b;界面不…
阅读更多...
Tomcat7.0/8.0 详细安装配置

Tomcat7.0/8.0 详细安装配置

Tomcat 7.0 、Tomcat8.0 详细安装配置图解，以及UTF-8编码配置 注意：安装配置tomcat7.0及以上，需要先安装JDK1.7及以上才能支持。 1、先下载tomcat压缩包 Tomcat 7 ：http://tomcat.apache.org/download-70.cgi Tomcat 8 : http://tomcat.apache.org/download-80.cgi …
阅读更多...
tomcat7.0安装

tomcat7.0安装

下载地址 tomcat7.0下载地址 https://tomcat.apache.org/download-70.cgi 同事推荐别安装最新版&#xff0c;说是不稳定&#xff01; 安装前说明 安装tomcat之前一定要有jdk。 下载包分为安装版与免安装版&#xff0c;我使用的是安装版&#xff0c;安装完成后不需要配置环…
阅读更多...
CentOS8-Tomcat7安装并设置开机自启动

CentOS8-Tomcat7安装并设置开机自启动

CentOS8-Tomcat7安装并设置开机自启动 1、安装 将压缩包文件apache-tomcat-7.0.57.tar.gz利用Xftp 6工具上传到/usr/local中并解压&#xff08;为了以后可能会安装多个Tomcat,我将解压后的文件移动到了新建目录tomcat-cluster下并重命名&#xff09;&#xff1a; tar -xvf a…
阅读更多...
java和 Tomcat9.0 Tomcat7 安装配置

java和 Tomcat9.0 Tomcat7 安装配置

工具/原料 JDK1.7.0 WIN7 方法/步骤 安装JDK 选择安装目录 安装过程中会出现两次 安装提示 。第一次是安装 jdk &#xff0c;第二次是安装 jre 。建议两个都安装在同一个java文件夹中的不同文件夹中。&#xff08;不能都安装在java文件夹的根目录下&#xff0c;jdk和jre安装…
阅读更多...
如何安装Tomcat

如何安装Tomcat

本篇文章主要讲解的是如何安装Tomcat&#xff08;超详细&#xff09;。 下面是详细步骤&#xff08;具体操作可看图片上的标记&#xff09;&#xff1a; 1、如果你看完我上一篇文章“如何下载Tomcat”后&#xff0c;你会看到下图&#xff0c;在这我主要讲解的是在windows系统…
阅读更多...
ubuntu安装Tomcat7

ubuntu安装Tomcat7

Tomcat7安装包已经被下载 需要传输到Ubuntu上 使用filezilla软件进行传输 在Ubuntu中安装ssh远程连接 sudo apt install openssh-server我在安装的ssh过程中出现了 如下问题&#xff1a; 时出现提示无法修正错误&#xff0c;因为您要求某些软件包保持现状&#xff0c;就是它…
阅读更多...
推荐文章

Copyright @ 2022~2023