试题D:路径
创始人
2024-06-02 14:36:09
0

试题D:路径

文章目录

  • 试题D:路径
  • 一、前置知识
  • 二、分析
    • 1、数据分析
    • 2、过程分析
  • 三、代码
  • 四、参考材料

题目描述

​ 小蓝学习了最短路径之后特别高兴,他定义了一个特别的图,希望找到图中的最短路径。小蓝的图由2021 个结点组成,依次编号1 至2021。

对于两个不同的结点a, b,如果a 和b 的差的绝对值大于21,则两个结点之间没有边相连;如果a 和b 的差的绝对值小于等于21,则两个点之间有一条长度为a 和b 的最小公倍数的无向边相连
​ 例如:结点1 和结点23 之间没有边相连;结点3 和结点24 之间有一条无向边,长度为24;
结点15 和结点25 之间有一条无向边,长度为75。
​ 请计算,结点1 和结点2021 之间的最短路径长度是多少。
​ 提示:建议使用计算机编程解决问题。

解析:



一、前置知识

问题1:怎么求两个数a,b的最小公倍数呢?

答:【公式】a,b最小公倍数=a×b/a,b的最大公因数a,b最小公倍数 = a \times b / a,b的最大公因数a,b最小公倍数=a×b/a,b的最大公因数.

问题2:怎么求最大公因数呢?

答:辗转相除法

public static int gcd(int a,int b){return b==0?a:gcd(b,a%b);
}

问题3:阈值的选取

答:这一步很重要,下午调试了很久都是因为阈值没选好。阈值不能很大,因为这样可能会使扩展部分的加法查出long型范围;阈值不能太小,太小导致答案在阈值外面。

问题4:long型和Long型的区别

int转long型自然转换,int转Long型强制转换。




二、分析

1、数据分析

  • 0 < i 和 j 两个节点之间的差的绝对值 <22,distance[i][j] =a,b最小公倍数
  • i 和 j 两个节点之间的差的绝对值==0,distance[i][j] =0
  • i 和 j 两个节点之间的差的绝对值 > 21,distance[i][j] = 阈值,阈值十分重要,本次屡次在这犯错

2、过程分析

​ 在图中求一个点到另一个点的距离,可以使用Dijkstra和Floyd方法。可以使用Floyd方法是因为本题是填空题,时间复杂度不重要。

​ 关于Dijkstra和Floyd方法可以查看Dijkstra和Floyd




三、代码

1、Dijkstra代码

public class ExaminationD_Dijkstra {//求解最大公因数public static long gcd(long a,long b){return b==0?a:gcd(b,a%b);}//求解a,b的最小公倍数public static long lcm(long a,long b){return a*b/gcd(a,b);}public static long[] dijkstra(long[][] distance,int n,int origin){//辅助数组boolean[] used = new boolean[n];long[] minDis = new long[n];int pathIndex = origin-1;//初始化数组for (int i = 0; i < n; i++) {minDis[i] = distance[origin-1][i];}used[origin-1] = true;for (int i = 1; i < n; i++) {long min = Long.MAX_VALUE;//选取部分for (int j = 0; j < n; j++) {if (!used[j]&&minDis[j]//System.out.println(String.format("变化前minDis[%d]=%d,min=%d",j,minDis[j],min));min = minDis[j];//System.out.println(String.format("变化后minDis[%d]=%d,min=%d",j,minDis[j],min));pathIndex = j;}}used[pathIndex]= true;//扩展部分for (int k = 0; k < n; k++) {if (distance[pathIndex][k]!=Long.MAX_VALUE) {//选取合适的阈值使答案在这个范围又要使下面的加法不差过long范围if (minDis[pathIndex]+distance[pathIndex][k]minDis[k] = minDis[pathIndex] + distance[pathIndex][k];System.out.println(String.format("扩展minDisk[%d]=%d",k,minDis[k]));}}}}return minDis;}public static void main(String[] args) {int n = 2021;long[][] dis = new long[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (Math.abs(i-j)<=21&&Math.abs(i-j)>0) {dis[i][j] = dis[j][i] = lcm(i+1,j+1);}else if(i==j){dis[i][j] = 0;//在扩展部分可能会加上去}else if(Math.abs(i-j)>21){dis[i][j] = Long.MAX_VALUE;}}}long[] res = dijkstra(dis, n, 1);System.out.println(res[n-1]);}
}

2、Floyd代码

//麻烦的是怎么设定一个阈值
public class ExaminationD_Floyd {//求解最大公因数public static long gcd(long a,long b){return b==0?a:gcd(b,a%b);}//求解a,b的最小公倍数public static long lcm(long a,long b){return a*b/gcd(a,b);}public static long[][] floyd(long[][] distance,int n,int origin){for (int k = 0; k for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (distance[k][j]!=99999999L) {//设定阈值使小于阈值的两个数相加不超过long范围if (distance[i][k]+distance[k][j]distance[i][j] = distance[i][k]+distance[k][j];}}}}}return distance;}public static void main(String[] args) {int n = 2021;long[][] dis = new long[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (Math.abs(i-j)<=21&&Math.abs(i-j)>0) {dis[i][j] = dis[j][i] = lcm(i+1,j+1);}else if(i==j){dis[i][j] = 0;}else if(Math.abs(i-j)>21){dis[i][j] = 99999999L;}}}long res[][] = floyd(dis,n,1);System.out.println(res[0][n-1]);}
}




四、参考材料

蓝桥杯2021初赛 路径 Java

[2]2021蓝桥杯 java路径

相关内容

热门资讯

王者定位怎么关安卓系统,轻松实... 你是不是也和我一样,对王者荣耀这款游戏爱得深沉呢?不过,有时候游戏里的设置让人头疼,比如安卓系统的王...
树莓派安卓系统流畅,打造便携式... 亲爱的读者们,你是否曾想过,将树莓派与安卓系统结合,会擦出怎样的火花呢?今天,就让我带你一起探索这个...
安卓系统智能机顶盒,引领家庭娱... 你有没有想过,家里的电视也能变得智能起来?没错,就是那个陪伴我们多年的老电视,现在也能摇身一变,成为...
安卓系统很差了吗现在,性能优劣... 最近是不是有不少朋友在讨论安卓系统的问题呢?有人说它越来越差了,也有人觉得它还是那个熟悉的“老朋友”...
安卓系统uc安装包,Andro... 你有没有发现,手机里的安卓系统越来越强大了?今天,咱们就来聊聊这个话题——安卓系统中的UC安装包。你...
安卓系统谷歌能删吗,谷歌能否删... 你有没有想过,那个一直陪伴你手机生活的安卓系统,它背后的谷歌爸爸,是不是也能被你随意删掉呢?这可不是...
安卓系统会不会更耗电,解析其功... 你有没有发现,手机用着用着,电池就有点不给力了?尤其是那些用安卓系统的手机,有时候感觉电就像流水一样...
安卓系统中无效目录,安卓系统无... 你有没有遇到过在安卓系统中,明明文件夹就在那里,但是就是找不到的情况?别急,今天就来给你揭秘安卓系统...
国产安卓机哪个系统好用,探寻最... 你有没有想过,国产安卓机哪个系统最好用呢?这可是个让人纠结的问题,毕竟每个系统都有它的特色和亮点。今...
安卓系统cpua9,引领性能与... 你有没有发现,最近你的安卓手机运行得是不是比以前顺畅多了?这可多亏了那个强大的安卓系统CPUA9啊!...
安卓系统usb驱动程序,功能、... 你有没有遇到过这种情况:手机里存了那么多宝贝照片和视频,想传输到电脑上保存,结果电脑却像个小顽皮,死...
安卓操作系统怎么关闭,轻松关闭... 手机里的安卓操作系统是不是有时候让你觉得有点儿烦呢?别急,今天就来手把手教你如何轻松关闭安卓操作系统...
追星手机壳推荐安卓系统,盘点热... 你有没有发现,现在追星族们对手机壳的热爱简直到了疯狂的地步?没错,就是那种能让你一秒变身偶像迷妹的手...
ios系统用安卓系统游戏下载软... 你有没有想过,明明是iOS系统的手机,却想玩安卓系统的游戏?这可不是什么天方夜谭,现在就有这么神奇的...
安卓高系统怎么用美化,打造专属... 亲爱的安卓用户们,你是不是也和我一样,对手机系统美化情有独钟呢?想要让你的安卓手机焕然一新,变得个性...
安卓系统怎么开夜间模式,安卓系... 亲爱的手机控们,你是不是在夜晚使用安卓手机时,眼睛感到有些不适?别担心,今天我要给你揭秘一个超级实用...
王者安卓系统用苹果人脸,一场视... 你知道吗?最近在手机圈里可是掀起了一股不小的波澜呢!那就是王者安卓系统竟然用上了苹果人脸识别技术!是...
安卓444怎么升级系统,轻松迈... 你那安卓444的小家伙是不是已经有点儿落伍了?别急,今天就来给你详细说说怎么给它来个系统升级,让它焕...
安卓系统raw修图软件,探索安... 你有没有发现,手机拍照越来越方便了,但有时候拍出来的照片还是不够完美呢?别急,今天就来给你安利几款安...
安卓系统的王者切换苹果,从安卓... 你知道吗?最近身边的朋友圈里掀起了一股热潮,那就是安卓系统的王者们纷纷切换到苹果阵营。这可真是让人大...