【算法作业】实验五：神奇宝贝大军 & 到迷宫出口的最短路径

2022 年 10 月 09 日
湖南
本文字数：2804 字
阅读完需：约 9 分钟

第一题：神奇宝贝大军

1.题目

![在这里插入图片描述](https://img-blog.csdnimg.cn/f95e264f0f7c4832a58515774dfb81ff.png =600x)

输入描述输入第一行包含一个整数 n 表示神奇宝贝的个数输入第二行 n 个不同的整数，表示神奇宝贝的力量输出描述输出一个整数表示军队可以取得的最大力量样式输入 71 2 5 4 3 6 7 样式输出 9 样式解析构造军队的方式为 5 3 7，军队力量为 5-3+7=9

2.问题分析与算法设计思路

类似地将皮卡丘的战斗力与标号的关系看作函数： $a = f (b)$ 。则我们只需遍历一次这些皮卡丘，同时过程中挑出所有的极大值和极小值，然后将这些皮卡丘作为军队，即可取得最大军队力量。

为什么这样可以得到最大的军队力量？自己举几个例子就能发现，不取极值点的情况，总可以用取了极值点的情况来替代同时获得更大的军队力量。

或者，你可以发现军队力量将来自函数曲线的下降阶段。若从前往后每两只神奇宝贝为一组，则每一组都相当于在曲线上截取一段；截取的下降落差越大，则军队的力量越大。而前面介绍的神奇宝贝挑选方法，将覆盖曲线上所有的下降阶段。（如果曲线右端是上翘的，可以等效为最后再加一只战斗力为 0 的神奇宝贝）

3.算法实现

1）更新版本

1-更新介绍

记住我们的目标是：尽可能截取函数的下降阶段。

主要改变了极大值和极小值的判定方式：

极大值：对于 $a [i]$ ，需满足 $a [i] > a [i - 1] 且 a [i] > a [i + 1]$
极小值：对于 $a [i]$ ，需满足 $a [i] < a [i - 1] 且 a [i] < a [i + 1]$

这样判断极值点更加清晰明确

对于端点单独考虑：

左端点：若 $a [i] > a [i + 1]$ ，则作为极大值。永远不作为极小值。
右端点：若 $a [i] > a [i - 1]$ ，则作为极大值；若 $a [i] < a [i - 1]$ ，则作为极小值；

程序过程：

输入神奇宝贝数组
遍历数组，对每个点进行分类（非极值点、极大值点、极小值点）
遍历过程中，每找到一个极小值（在这之前一定也找到了一个极大值），更新一次军队总战斗力： $总战斗力 + = 极大值 - 极小值$

2-版本代码

#include<iostream>using namespace std;
const int Big = 100;//神奇宝贝最大数量 
int amy(int bkm[], int n){  int sum = 0;//总战斗力  int max = 0;//极大值  int min = 0;//极小值     //左端点   if(bkm[0] > bkm[1]){    max = bkm[0];  }  //中间部分   for(int i = 1; i <= n-2; i++){    bool found_min = false;//本次循环是否找到极小值     if(bkm[i] > bkm[i-1] && bkm[i] > bkm[i+1]){      max = bkm[i];    }    else if(bkm[i] < bkm[i-1] && bkm[i] < bkm[i+1]){      min = bkm[i];      found_min = true;    }    if(found_min){      sum += max - min;    }  }  //右端点   if(bkm[n-1] < bkm[n-2]){    min = bkm[n-1];    sum += max - min;  }  return sum;}
int main(){  int bkm[Big] = {};//所有神奇宝贝的战斗力   int n = 0;//神奇宝贝的数量   //输入   cin>>n;  for(int i = 0; i < n; i++){    cin>>bkm[i];  }    int sum = amy(bkm, n);  cout<<sum;    return 0;}

复制代码

2）初有问题版本

1-找到问题的输入测试

输入 55 1 4 1 7 运行结果

2-问题原因

代码中同时进行神奇宝贝的输入和处理，在找极大值和找极小值过程的衔接有问题。

后面改来改去，老出现新的 bug，就干脆重写了。

3-版本代码

#include<iostream>using namespace std;int main(){  int n=0;  int temp=0;  int sum=0;//军队的总战斗力     int i=0;  int a=0;  int b=0;    cin>>n;    while(true){        cin>>a;    i++;    //找局部最大值    while(i<n){      cin>>b;      i++;      if(a<b) a = b;      else break;    }    int max = a;        if(i ** n){      sum += max;      break;    }    //找局部最小值    while(i<n){      cin>>b;      i++;      if(a>b) a = b;      else break;    }    int min = a;        if(i ** n){      sum += min;      break;    }    //作差，加入总战斗力     sum += max - min;  }    cout<<sum;  return 0;}

复制代码

4.运行结果

5.算法分析

时间复杂度为： $o (n)$ 。

第二题：到迷宫出口的最短路径

1.题目

当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。假设你已经得到了一个 n*m 的迷宫的图纸，请你找出从起点到出口的最短路。输入描述第一行是两个整数 n 和 m(1<=n,m<=100)，表示迷宫的行数和列数。接下来 n 行，每行一个长为 m 的字符串，表示整个迷宫的布局。字符'.'表示空地，'#'表示墙，'S'表示起点,'T'表示出口。只能进行上、下、左、右四个方向的搜索。输出从起点到出口最少需要走的步数。样式输入 3 3S#T.#....样式输出 6

2.问题分析与算法设计思路

采用回溯法的思路，不过为了提高算法的效率，可以在搜索的过程中记录走过的地方。使用深度优先和广度优先都是可以的，我这里使用的深度优先搜索。

3.算法实现

代码：

//迷宫起点到出口的最短路径 #include<iostream>using namespace std;
int count=123456789;//到出口所用步数 
void dfs(char mg[100][100], int n, int m, int xy[2], int BuShu){//  cout<<"xy:"<<xy[0]<<' '<<xy[1]<<endl;  //出来了吗？  if(mg[xy[0]][xy[1]] ** 'T'){    if(BuShu < count){      count = BuShu;    }    return;  }   //1  if(xy[0] < n - 1) {    mg[xy[0]][xy[1]] = '#';    xy[0]++;    if(mg[xy[0]][xy[1]] != '#'){//      cout<<"下"<<endl;      dfs(mg,n,m,xy,BuShu+1);    }    xy[0]--;    mg[xy[0]][xy[1]] = '.';  }  //2  if(xy[0] > 0) {    mg[xy[0]][xy[1]] = '#';    xy[0]--;    if(mg[xy[0]][xy[1]] != '#'){//      cout<<"上"<<endl;      dfs(mg,n,m,xy,BuShu+1);    }    xy[0]++;    mg[xy[0]][xy[1]] = '.';  }  //3  if(xy[1] < m - 1) {    mg[xy[0]][xy[1]] = '#';    xy[1]++;    if(mg[xy[0]][xy[1]] != '#'){//      cout<<"右"<<endl;      dfs(mg,n,m,xy,BuShu+1);    }    xy[1]--;    mg[xy[0]][xy[1]] = '.';  }  //4  if(xy[1] > 0) {    mg[xy[0]][xy[1]] = '#';    xy[1]--;    if(mg[xy[0]][xy[1]] != '#'){//      cout<<"左"<<endl;      dfs(mg,n,m,xy,BuShu+1);    }    xy[1]++;    mg[xy[0]][xy[1]] = '.';  }}
int main(){  char mg[100][100] = {};  int n=0;//迷宫的高(第一维）   int m=0;//迷宫的宽（第二维）  int start[2]={};//起点位置     cin>>n>>m;    //输入迷宫   for(int i = 0; i < n; i++){    for(int j = 0; j < m; j++){      cin>>mg[i][j];      if(mg[i][j] ** 'S'){        start[0] = i;        start[1] = j;      }    }  }     //走迷宫——深度搜索  dfs(mg,n,m,start,0);  //  cout<<"count:"<<count<<endl;  cout<<count<<endl;     return 0;}

复制代码

4.运行结果

5.算法分析

略😅

感谢阅读

博主主页：CSDN清风莫追

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/1a9cf0331221105fe32256035】。文章转载请联系作者。

清风莫追

关注

还未添加个人签名 2022.08.09 加入

编程一学生

发布

暂无评论

创作场景

【算法作业】实验五：神奇宝贝大军 & 到迷宫出口的最短路径

第一题：神奇宝贝大军

1.题目

2.问题分析与算法设计思路

3.算法实现

1）更新版本

1-更新介绍

2-版本代码

2）初有问题版本

1-找到问题的输入测试

2-问题原因

3-版本代码

4.运行结果

5.算法分析

第二题：到迷宫出口的最短路径

1.题目

2.问题分析与算法设计思路

3.算法实现

4.运行结果

5.算法分析

清风莫追

评论