07-图4 哈利·波特的考试 (25分)(C语言实现)

2023-11-28 18:58
文章标签 语言 实现 25 考试 07 哈利 波特

本文主要是介绍07-图4 哈利·波特的考试 (25分)(C语言实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

07-图4 哈利·波特的考试 (25分)(C语言实现)

数据结构(浙江大学)

哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。

现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。

输入格式:
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。

输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。

输入样例:
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
输出样例:
4 70

我们先分析此道题目，本题主要是求解哈利波特带哪只动物去参加考试,文章要求输出最长的变形魔咒的那只动物编号和魔咒长度。
首先:

程序框架搭建


int main()
{MGraph G=BuildGraph();//读入图FindAnimal(G);//分析图return 0;
}

先进行一些前面的定义

#include<stdio.h>
#include<stdlib.h>
#define MAX 100   //定义邻接图的大小
#define INFINITY 65535  //为了初始化邻接图的权重
typedef int Vertex;
typedef int WeightType;
/*定义图的结构体*/
typedef struct GNode *PtrToGNode;
struct GNode
{int Nv;int Ne;WeightType G[MAX][MAX];
};
typedef PtrToGNode MGraph;
/*定义边的结构体*/
typedef struct ENode *Edge;struct ENode {Vertex V1;  Vertex V2;WeightType Weight;};

总的函数声明如下:

MGraph Create(int VertexNum);//初始化图 
void InsertEdge(MGraph Graph,Edge E); //插入边
MGraph BuildGraph(); //建造图
void Find(MGraph G);
void Floyd( MGraph Graph, WeightType D[][MAX]);//佛洛依德算法
Vertex FindMax(WeightType D[][MAX],int i,int n);//找出最大的那个值

在这在这里我们需要先创造一个没有插入权重的空图，然后再进行输入，进行插入边。关于初始化图的函数:

MGraph Create(int Vertexnum)//初始化图,在这里要传入顶点的个数{MGraph G;G=(MGraph)malloc(sizeof(struct GNode));G->Nv=Vertexnum;G->Ne=0;for(int i=0;i<Vertexnum;i++){for(int j=0;j<Vertexnum;j++)G->G[i][j]=INFINITY;//初始化权重为很大的值}return G;}

关于插入边的函数InsertEdge():

void InsertEdge(MGraph G,Edge E){G->G[E->V1][E->V2]=E->Weight;   //在相应的邻接图存入相应的权重G->G[E->V2][E->V1]=E->Weight;}

接着就是BuildGraph()函数的定义:

MGraph BuildGraph(){Edge E;MGraph G;int Nv;scanf("%d",&Nv);G=Create(Nv);scanf("%d",&(G->Ne));if(G->Ne!=0){E=(Edge)malloc(sizeof(struct ENode));for(int i=0;i<G->Ne;i++){scanf("%d%d%d",&(E->V1),&(E->V2),&(E->Weight));E->V2--;E->V1--; InsertEdge(G,E); //插入边}}return G;}

在这里说明为什么要- -，因为数组下标是从0到n-1的，所以当你传入2-3的权重时,实际上是存到数组[1][2]当中去的.

好了，关于图的定义我们已经弄好了，接下来就是关于查找的问题了,在查找时候我们设计到一个很重要的算法:弗洛伊德算法.

void Floyd(MGraph Graph,WeightType D[][MAX]){Vertex i,j,k;for(i=0;i<Graph->Nv;i++)  //初始化,建立个和邻接图一样的二维数组{for(j=0;j<Graph->Nv;j++){D[i][j]=Graph->G[i][j];}}/*进行判断*/for(k=0;k<Graph->Nv;k++)for(i=0;i<Graph->Nv;i++)for(j=0;j<Graph->Nv;j++)if(D[i][j]>D[i][k]+D[k][j])D[i][j]=D[i][k]+D[k][j];}

在这个函数中，参数需要传来一个二维数组，我们需要对此二维数组进行改造.首先,我们需要复制一个和图节点的数组一模一样的数组,然后对此数组进行改造.那么这个三层循环是用来干什么的呢?
这就是弗洛伊德算法的作用:求最短路径，而且是有向图.在这里插入图片描述
假如给了你这样一张图，那我们进行分析:
在这里插入图片描述
在这里插入图片描述
由此可见，这三层循环会将D这个二维数组进行改变，除了对角点，其他节点都有了值.

接下来的代码就迎刃而解了

void find(MGraph G)
{WeightType D[MAX][MAX],Max = 0,Min = INFINITY;Vertex Animal,i;Floyd(G,D);//弗洛伊德算法for(i=0;i<G->Nv;i++)//进行循环{Max=FindMax(D,i,G->Nv);//找出i节点所对应的最大值if(Max==INFINITY)//如果最大值是INFINITY，说明只能带一只动物,显然是不行的.{printf("0\n");//直接输出返回return;}if(Max<Min)//已经是最大值了,不可能比INFINITY大的，所以对应着最大的权重{Min=Max;Animal=i+1;//因为数组是从下标为0开始存入的}}printf("%d %d\n",Animal,Min);//最后那个最大的那个动物
}

找出最大值的那个函数:

int FindMax(WeightType D[][MAX],int i,int n)
{int j,max = 0;for(j = 0; j < n; j++){if(i != j && D[i][j] > max)//如果缺少i!=j，那么max永远都是65535max = D[i][j];}return max;
}

总的代码如下:请认真思考再写代码！！！
希望大家都能有所收获!!!

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define INFINITY 65535
typedef int Vertex;
typedef int WeightType;
typedef struct ENode *Edge;struct ENode {Vertex V1;Vertex V2;WeightType Weight;};typedef struct GNode *PtrtoGNode;struct GNode //定义一个图的结构体{int Nv;int Ne;WeightType G[MAX][MAX];};typedef PtrtoGNode MGraph;MGraph Create(int VertexNum);//初始化图 
void InsertEdge(MGraph Graph,Edge E); //插入连接线 
MGraph BuildGraph();
void Find(MGraph G);
void Floyd( MGraph Graph, WeightType D[][MAX]);
Vertex FindMax(WeightType D[][MAX],int i,int n);int main(){MGraph G = BuildGraph();find(G); }MGraph Create(int Vertexnum){MGraph G;G=(MGraph)malloc(sizeof(struct GNode));G->Nv=Vertexnum;G->Ne=0;for(int i=0;i<Vertexnum;i++){for(int j=0;j<Vertexnum;j++)G->G[i][j]=INFINITY;}return G;}void InsertEdge(MGraph G,Edge E){G->G[E->V1][E->V2]=E->Weight;   //在相应的邻接图存入相应的权重G->G[E->V2][E->V1]=E->Weight;}MGraph BuildGraph(){Edge E;MGraph G;int Nv;scanf("%d",&Nv);G=Create(Nv);scanf("%d",&(G->Ne));if(G->Ne!=0){E=(Edge)malloc(sizeof(struct ENode));for(int i=0;i<G->Ne;i++){scanf("%d%d%d",&(E->V1),&(E->V2),&(E->Weight));E->V2--;E->V1--; //因为输入边是从1开始的，而插入是从0开始的;InsertEdge(G,E); //插入边}}return G;}
void Floyd(MGraph Graph,WeightType D[][MAX]){Vertex i,j,k;for(i=0;i<Graph->Nv;i++)  //初始化,建立个和邻接图一样的二维数组{for(j=0;j<Graph->Nv;j++){D[i][j]=Graph->G[i][j];}}/*进行判断*/for(k=0;k<Graph->Nv;k++)for(i=0;i<Graph->Nv;i++)for(j=0;j<Graph->Nv;j++)if(D[i][j]>D[i][k]+D[k][j])D[i][j]=D[i][k]+D[k][j];}
void find(MGraph G)
{WeightType D[MAX][MAX],Max = 0,Min = INFINITY;Vertex Animal,i;Floyd(G,D);for(i=0;i<G->Nv;i++){Max=FindMax(D,i,G->Nv);if(Max==INFINITY){printf("0\n");return;}if(Max<Min){Min=Max;Animal=i+1;}}printf("%d %d\n",Animal,Min);
}
int FindMax(WeightType D[][MAX],int i,int n)
{int j,max = 0;for(j = 0; j < n; j++){if(i != j && D[i][j] > max)max = D[i][j];}return max;
}

这篇关于07-图4 哈利·波特的考试 (25分)(C语言实现)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/430119。

相关文章

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源：安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供，流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材，流动式起重机司机大纲整理而成（含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析），掌握本资料和学校方法，考试容易。流动式起重机司机考试技
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
hdu 2093 考试排名（sscanf）

hdu 2093 考试排名（sscanf）

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()"，有时候又没有。而它也不会给我们提示。 这种情况下，就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和
阅读更多...
科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

介绍 R语言的扩展物种堆积图是一种数据可视化工具，它不仅展示了物种的堆积结果，还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异，为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2