计算机算法基础实验程序及运行结果

ID:632295 · 发表于 2019-10-29 21:11

一找最大和最小元素与归并分类算法实现（用分治法）
一、实验目的

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++下实现所设计的算法；