一找最大和最小元素与归并分类算法实现(用分治法)
一、实验目的
1.掌握能用分治法求解的问题应满足的条件;
2.加深对分治法算法设计方法的理解与应用;
3.锻炼学生对程序跟踪调试能力;
4.通过本次实验的练习培养学生应用所学知识解决实际问题的能力。
二.实验内容
(1)找最大最小元素:输入n个数,找出最大和最小数的问题。
(2)归并分类:对n个数用归并方法排序。
三.实验要求
(1)用分治法求解问题
(2)上机实现所设计的算法;
四.实验过程设计(算法设计过程)
常规的做法是遍历一次,分别求出最大值和最小值,但我这里要说的是分治法(Divide and couquer),将数组分成左右两部分,先求出左半部份的最大值和最小值,再求出右半部份的最大值和最小值,然后综合起来求总体的最大值及最小值。这是个递归过程,对于划分后的左右两部分,同样重复这个过程,直到划分区间内只剩一个元素或者两个元素。
解决问题的策略:
蛮力策略:对金块逐个进行比较查找。(扫描数组一轮,寻找最大和最小的数。)该策略需要进行(n-1)次的比较才能得到max和min。
分治法(二分法)策略:问题可以简化为在n个数里面寻找最大和最小值。
(1)将数据等分为两组(两组数据的个数可能相差1),目的是分别选取其中的最大(小)值。
(2)递归分解直到每组元素的个数<=2,则可以简单地找到其中的最大(小)值。
(3)回溯时合并子问题的解,在两个子问题的解中大者取大,小者取小,即合并为当前问题的解。
五.源代码
(1)找最大最小元素:
- #include <iostream>
- using namespace std;
-
- void findMinMax(int a[],int l,int r,int *maxnum,int *minnum){
- if(l==r){//如果只有一个元素,则最小最大都是这个元素
- *maxnum = *minnum = a[l];
- return;
- }
- int mid,lmin,rmin,lmax,rmax;
- mid = (l+r)/2;
- findMinMax(a,l,mid,&lmax,&lmin);//寻找数组左边的最大最小元素
- findMinMax(a,mid+1,r,&rmax,&rmin);//寻找数组右边的最大最小元素
- *maxnum = lmax>rmax?lmax:rmax;//比较左右边的最大元素找出更大的
- *minnum = lmin<rmin?lmin:rmin;//比较左右边的最小元素找出更小的
- }
- int main()
- {
- int a[] = {1,2,3,4,5,6,7,8,9};
- int max,min;
- findMinMax(a,0,8,&max,&min);
- cout<<"max = "<<max<<"\n";
- cout<<"min = "<<min<<"\n";
- return 0;
- }
复制代码
程序运行结果如下图所示: (2)归并分类:
- #include <stdio.h>
- #include <stdlib.h>
- void merge(int low,int mid,int high,int a[]){
- int h,i,j,k;
- h = i = low;
- j = mid+1;//把数组a从mid分成两个集合
- int b[high];//数组b为辅助数组
- while(h <= mid && j <= high){//当两个集合都没有取尽时
- if(a[h] <= a[j]){
- b[i] = a[h];
- h++;
- }else{
- b[i] = a[j];
- j++;
- }
- i++;
- }
- /*处理剩余的元素*/
- if(h > mid){//前一个数组先取完
- for(k = j;k <= high;k++){
- b[i] = a[k];
- i++;
- }
- }else{//后一个数组先取完
- for(k = h;k <= mid;k++){
- b[i] = a[k];
- i++;
- }
- }
- /*将已经合并的集合从辅助数组复制到原数组*/
- for(k = low;k <= high;k++){
- a[k] = b[k];
- }
- }
-
- void mergeSort(int low,int high,int a[]){
- if(low < high){
- int mid = (low+high)/2;//求集合的分割点
- mergeSort(low,mid,a);//将前半个集合分类
- mergeSort(mid+1,high,a);//将后半个集合分类
- merge(low,mid,high,a);//归并两个已经分类的集合
- }
- }
-
- int main()
- {
- int a[] = {2,4,3,6,1,7,8,5,9};
- mergeSort(0,8,a);
- for(int i = 0;i <= 6;i++){
- printf("\t%d\n",a[i]);
- }
- return 0;
- }
复制代码
程序运行结果如下图所示:
实验二 背包问题和最小生成树算法实现(用贪心法)
一、实验目的
1.掌握能用贪心法求解的问题应满足的条件;
2.加深对贪心法算法设计方法的理解与应用;
3.锻炼学生对程序跟踪调试能力;
4.通过本次实验的练习培养学生应用所学知识解决实际问题的能力。
二.实验内容
有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
三.实验要求
(1)用贪心法求解背包问题;
(2)上机实现所设计的算法;
四.实验过程设计(算法设计过程)
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
基本思路
建立数学模型来描述问题;
把求解的问题分成若干个子问题;
对每一子问题求解,得到子问题的局部最优解;
把子问题的解局部最优解合成原来解问题的一个解。
算法实现
从问题的某个初始解出发。
采用循环语句,当可以向求解目标前进一步时,就根据局部最优策略,得到一个部分解,缩小问题的范围或规模。
将所有部分解综合起来,得到问题的最终解。
实例分析
实例1 背包问题
问题描述
有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。 - 问题分析
1.目标函数: ∑pi最大,使得装入背包中的所有物品pi的价值加起来最大。
2.约束条件:装入的物品总重量不超过背包容量:∑wi<=M( M=150)
3.贪心策略:
- 选择价值最大的物品
- 选择价值最大的物品
- 选择单位重量价值最大的物品
有三个物品A,B,C,其重量分别为{30,10,20},价值分别为{60,30,80},背包的容量为50,分别应用三种贪心策略装入背包的物品和获得的价值如下图所示:
三种策略 - 计算出每个物品单位重量的价值
- 按单位价值从大到小将物品排序
- 根据背包当前所剩容量选取物品
- 如果背包的容量大于当前物品的重量,那么就将当前物品装进去。否则,那么就将当前物品舍去,然后跳出循环结束。
五.源代码
(1)背包问题
- #include <iostream>
- #include<algorithm>
- using namespace std;
- /*定义物品的结构体*/
- struct Object{
- double weight;//物品重量
- double value;//物品价值
- double avg;//单位重量价值
- double prop;//放入比例:0表示没有放入,1表示全部放入
- };
-
- /*定义物品排序的标准*/
- bool cmp(Object a,Object b){
- return a.avg>b.avg;
- }
-
- int main()
- {
- Object *ob;
- double volume;//背包容量
- int num;//物品种类
- double maxValue = 0;//背包中的最大价值
- cout<<"请输入所有物品数量和背包容量\n";
- cin>>num>>volume;
- ob = new Object[num];
- /*初始化物品的重量和价值,并计算单位重量价值*/
- for(int i = 0;i<num;i++){
- cout<<"输入第"<<i+1<<"个物品的重量和价值\n";
- cin>>ob[i].weight>>ob[i].value;
- ob[i].avg = ob[i].value/ob[i].weight;
- }
- sort(ob,ob+num,cmp);//物品按单位重量价值降序
- int i;
- /*开始装入物品*/
- for(i = 0;i<num;i++){
- if(ob[i].weight <= volume){//如果这个物品能全部装入
- volume = volume -ob[i].weight;
- ob[i].prop = 1;//表示全部装入
- maxValue = maxValue + ob[i].value;
- } else{//这个物品已经不能全部装人
- break;
- }
- }
- if(i<num){//有一个物品不能全部装入
- ob[i].prop = volume/ob[i].weight;//装入的比例
- volume = 0;
- maxValue = maxValue + ob[i].prop*ob[i].value;
- }
- cout<<"放入的物品的重量,价值,比例\n";
- for(int i = 0;i<num;i++){
- cout<<ob[i].weight<<" "<<ob[i].value<<" "<<ob[i].prop<<"\n";
- }
- cout<<"放入物品的总价值:"<<maxValue;
- return 0;
- }
复制代码
程序运行结果: (2)最小生成树 - /*
- S:当前已经在联通块中的所有点的集合
- 1. dist[i] = inf
- 2. for n 次
- t<-S外离S最近的点
- 利用t更新S外点到S的距离
- st[t] = true
- n次迭代之后所有点都已加入到S中
- 联系:Dijkstra算法是更新到起始点的距离,Prim是更新到集合S的距离
- */
- #include <iostream>
- #include <cstring>
- using namespace std;
- const int N = 510, INF = 0x3f3f3f3f;
-
- int n, m;//n=|V|,m=|E|
- int g[N][N], dist[N];
- //邻接矩阵存储所有边
- //dist存储其他点到S的距离
- bool st[N];
-
- int prim() {
- //如果图不连通返回INF, 否则返回res
- memset(dist, INF, sizeof dist);
- int res = 0;
-
- for(int i = 0; i < n; i++) {
- int t = -1;
- for(int j = 1; j <= n; j++)
- if(!st[j] && (t == -1 || dist[t] > dist[j]))
- t = j;
- //寻找离集合S最近的点
- if(i && dist[t] == INF) return INF;
- //判断是否连通,有无最小生成树
-
- if(i) res += dist[t];
- //cout << i << ' ' << res << endl;
- st[t] = true;
- //更新最新S的权值和
-
- for(int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
- }
-
- return res;
- }
-
- int main() {
- cout << "顶点数和边数:" << endl;
- cin >> n >> m;//n=|V|,m=|E|
- int u, v, w;//u,v,w,表示点u和点v之间存在一条权值为w的边
-
- for(int i = 1; i <= n; i++)
- for(int j = 1; j <= n; j++)
- if(i ==j) g[i][j] = 0;
- else g[i][j] = INF;
-
- while(m--) {
- cout<< "两顶点和边长:" << endl;
- cin >> u >> v >> w;
- g[u][v] = g[v][u] = min(g[u][v], w);
- }
- int t = prim();
- cout <<"最小生成树的树边权重之和:"<< t << endl;
- }
复制代码
程序运行结果:
实验三 多段图和货郎担问题算法实现(用动态规划方法)
一.实验目的
1.掌握能用动态规划方法求解的问题应满足的条件;
2.加深对动态规划方法的理解与应用;
3.锻炼学生对程序跟踪调试能力;
4.通过本次实验的练习培养学生应用所学知识解决实际问题的能力。
二.实验内容
(1)多段图:对于任意数目的n个节点,分别用1~n编号,对于k段,分别用1~k编号,则这个问题归结为在k段n个节点的带权图中寻找从节点1到节点n的最短路径。(自己添加的内容)
(2)货郎担:对于任意数目的n个城市,分别用1~n编号,则这个问题归结为在有向带权图中,寻找一条路径最短的哈密尔顿回路问题。
三.实验要求
(1)用动态规划方法货郎担问题;实现多段图问题
(2)上机实现所设计的算法;
四.实验过程设计(算法设计过程)
动态规划的思想实质是分治思想和解决冗余。 与分治法类似的是,将原问题分解成若干个子问题,先求解子问题,再从这些子问题的解得到原问题的解。与分治法不同的是,经分解的子问题往往不是互相独立的。若用分治法来解,有些共同部分(子问题或子子问题)被重复计算了很多次。如果能够保存已解决的子问题的答案,在需要时再查找,这样就可以避免重复计算、节省时间。动态规划法用一个表来记录所有已解的子问题的答案。
动态规划方法的基本思想是,把求解的问题分成许多阶段或多个子问题,然后按顺序求解各子问题。最后一个子问题就是初始问题的解。
由于动态规划的问题有重叠子问题的特点,为了减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。
五.源代码
(1)多段图 - #include <iostream>
- using namespace std;
- #define INFI 65535 //定义两节点之间的最大路径
- int c[12][12]; //两节点之间路径长度的数组
-
- /**/
- void FGRAPH(int n,int k){
- int cost[n];//第n个节点到最后一个节点的最端路径
- for(int i = 0;i<n;i++){
- cost[i] = INFI;//初始化所有节点的最短路径为无穷大
- }
- cost[n-1] = 0;
- int j,r;
- int p[k],d[n];//p为段决策,d为节点决策
- int min;
- /*寻找所有节点到最后一个节点的最短路径和节点决策)*/
- for(j = n-2;j>=0;j--){
- min = INFI;
- for(r = 0;r<=n-1;r++){
- if(c[j][r]+cost[r]<min){
- min = c[j][r] + cost[r];
- d[j] = r; //r即为j节点的节点的决策
- }
- }
- cost[j] = min; //j节点的最短路径
- }
- p[0] = 0;
- p[k-1] = n-1;
- for(int j = 1;j<=k-1;j++){
- p[j] = d[p[j-1]];//上一个段的段决策的节点决策即为下一个段的段决策
- }
- for(int j = 0;j<=k-1;j++){
- cout<<p[j]<<"\n";
- }
- }
- int main()
- {
- int N = 12;
- /*节点之间距离初始化*/
- for(int i = 0;i<N;i++){
- for(int j = 0;j<N;j++){
- if(i == j)
- c[i][j] = 0;
- else{
- c[i][j] = INFI;
- c[j][i] = INFI;
- }
-
- }
- }
- c[0][1] = 9;
- c[0][2] = 7;
- c[0][3] = 3;
- c[0][4] = 2;
- c[1][5] = 4;
- c[1][6] = 2;
- c[1][7] = 1;
- c[2][5] = 2;
- c[2][6] = 7;
- c[3][7] = 11;
- c[4][6] = 11;
- c[4][7] = 8;
- c[5][8] = 6;
- c[5][9] = 5;
- c[6][8] = 4;
- c[6][9] = 3;
- c[7][9] = 5;
- c[7][10] = 6;
- c[8][11] = 4;
- c[9][11] = 2;
- c[10][11] = 5;
- FGRAPH(N,5);//调用多段图函数
- return 0;
- }
复制代码
程序运行结果如下图所示:
(2) 货郎担 - #include<iostream>
- #include<iomanip>
- using namespace std;
-
- int n;
- int cost[20][20];
- bool done[20]={1};
- int start = 0; //从城市0开始
- int imin(int num, int cur)
- {
- if(num==1) //递归调用的出口
- return cost[cur][start]; //所有节点的最后一个节
- //最后返回 最后一个节点到起点的路径
- int mincost = 10000;
- for(int i=0; i<n; i++)
- {
- cout<<i<<" i:"<<done[i]<<endl;
- if(!done[i] && i!=start) //该结点没加入且非起始点
- {
- done[i] = 1; //递归调用时,防止重复调用
- int value = cost[cur][i] + imin(num-1, i);
- if(mincost > value)
- {
- mincost = value;
- cout<<mincost<<endl;
- }
- done[i] = 0;//本次递归调用完毕,让下次递归调用
- }
- }
- return mincost;
- }
-
- int main()
- {
- n=4;
- int cc[4][4]={{0,4,1,3},{4,0,2,1},{1,2,0,5},{3,1,5,0}};
- for(int i=0; i<n; i++)
- {
- for(int j=0; j<n; j++)
- {
- cost[i][j]=cc[i][j];
- }
- }
- cout << imin(n, start) << endl;
- return 0;
- }
复制代码
程序运行结果如下图所示:
实验四 皇后与子集和数问题算法实现(用回溯法) 一、实验目的 1.掌握能用回溯法求解的问题应满足的条件; 2.加深对回溯法算法设计方法的理解与应用; 3.锻炼学生对程序跟踪调试能力; 4.通过本次实验的练习培养学生应用所学知识解决实际问题的能力。 二.实验内容 (1)n皇后问题 由N2个方块排成N行N列的正方形,称为N元棋盘,在N元棋盘上放置N个皇后,如果某两个皇后位于N元棋盘的同一行或同一列或同一斜线(斜率为±1)上,则称它们在互相攻击,试设计算法找出使N个皇后互不攻击的所有布局。 (2)子集和数问题 子集和数问题是假定有n个不同的正数(通常称为权),要求找出这些数中所有事的某和数为M的组合。 (1)我们假设一个前提条件:这些正数是按照非降次序排列的。 (2)引入一个记号:B(X(1),...,X(k))表示是否可以把第K个正数加入进来,所以它的取指为true或者false。 那么当我们考虑是否要把第K个正数加入到解向量中的时候,我们就能找到两个条件组成这个限界函数了: (1)这个公式的含义是:当你考虑是否要把第K个正数加入到解向量的时候,不管你要加进来或者是不打算把它加进来,前K个解向量的和(包括第K个,当然X(k)可能是0或者1),加上后面所有的数的和一定要大于等于M,否则你把剩下的数都加了进来还比M小,这次的决策X(k)=0或者1肯定得不到满足条件的解向量。所以也就没有必要扩展这个结点的左儿子或者右儿子了。 (2)这个公式的含义是,当你考虑是否要把第K个正数加入到解向量的时候,不管你要加进来或者是不打算把它加进来,提前往后看一步,判断如果把第K+1个正数算进来后的值大于M,就不把第K个正数加进来。也就是说不生成第K-1个节点的儿子。 三.实验要求 (1)用回溯法算法设计方法求解N元皇后问题; (2)找出N皇后问题的互不攻击的所有解; (3)皇后数N由键盘动态输入; (4)上机实现所设计的算法; (5)分析所设计的算法的时间/空间复杂性。 四.实验过程设计(算法设计过程) (1)分析N皇后问题的约束条件,并将其显示化,选择存储结构建立相应的数学模型; (2)根据所建立的数学模型,设计求解该问题的粗略算法; (3)对所设计的粗略算法求精,得具体算法; (4)在C/C++下实现所设计的算法; (5)分析运行结果的正确性; (6)进行算法效率分析; (7)课后写出实验报告。 五.源代码 (1) n皇后问题
- #include <iostream>
- using namespace std;
- const int N = 20;
-
- // bool数组用来判断搜索的下一个位置是否可行
- // col列,dg对角线,udg反对角线
- // g[N][N]用来存路径
- //count表示第几个解
-
- int n;
- char g[N][N];
- bool col[N], dg[N], udg[N];
- int count = 0;
- void dfs(int u)
- {
- // u == n 表示已经搜了n行,故输出这条路径
- if (u == n)
- {
- count++;
- cout<<"第"<<count<<"个解:"<<endl;
- for (int i = 0; i < n; i ++ ) cout << g[i] << endl;
- cout<<endl;
- return;
- }
-
- //对n个位置按行搜索
- for (int i = 0; i < n; i ++ )
- // 剪枝(对于不满足要求的点,不再继续往下搜索)
- //udg[n - u + i],+n是为了保证大于0
- if (!col[i] && !dg[u + i] && !udg[n - u + i])
- {
- g[u][i] = 'Q';
- col[i] = dg[u + i] = udg[n - u + i] = true;
- dfs(u + 1);
- // 恢复现场 这步很关键
- col[i] = dg[u + i] = udg[n - u + i] = false;
- g[u][i] = '.';
-
- }
- }
-
- int main()
- {
- cout<<"请问这是几皇后问题:"<<endl;
- cin >> n;
- cout<<endl;
- for (int i = 0; i < n; i ++ )
- for (int j = 0; j < n; j ++ )
- g[i][j] = '.';
-
- dfs(0);
- return 0;
- }
复制代码
运行结果:
(2) 子集和数问题
- #include <iostream>
- using namespace std;
-
- //求解函数
- void sumOfSub(float s, int k, float r, int *x, float m, float *w);
- void sumOfSub(int *x, int n, float m, float *w);
-
- int main()
- {
- int n; //n表示集合元素个数
- float m; //m表示目标和
- cout << "请输入集合元素个数:";
- cin >> n;
- cout << "请输入目标和:";
- cin >> m;
- float *arr = new float [n + 1];
- int *x = new int [n + 1]; //求解状态
- cout << "请输入" << n <<"个集合元素(正值):";
- for(int i=0; i < n; i++)
- {
- cin >> arr[i];
- }
- cout << "可行解:\n";
- sumOfSub(x, n, m, arr);
-
- return 0;
- }
-
- void sumOfSub(float s, int k, float r, int *x, float m, float *w)
- {
- x[k] = 1;
- if(s + w[k] == m)//一个可行解
- {
- for(int j = 0;j <= k; j++)//两种输出方式任选
- {
- if(x[j] == 1) //完成输出,输出选取的元素
- cout << w[j] << " ";
- }
- cout << endl;
- }
- else if(s + w[k] + w[k+1] <= m)
- {
- sumOfSub(s+w[k], k+1, r-w[k], x, m, w);//搜索左子树
- }
- if((s + r - w[k] >= m)&&(s + w[k]+1 <= m))
- {
- x[k] = 0;
- sumOfSub(s, k+1, r - w[k], x, m, w); //搜索右子树
- }
- }
- void sumOfSub(int *x, int n, float m, float *w)
- {
- float r = 0;
- for(int i = 0; i < n; i++) r += w[i];//计算总值,判断是否有解
- if(r >= m && w[0] <= m) sumOfSub(0, 0, r, x, m, w);
- }
复制代码
运行结果:
完整的Word格式文档51黑下载地址:
|