Floyed算法[通俗易懂]

Floyed算法[通俗易懂]这一讲简单介绍一下Floyed算法。话不多说,先放一道题帮助理解(其实是懒得描述具体应用场景)。FroggerFreddyFrogissittingonastoneinthemiddleofalake.SuddenlyhenoticesFionaFrogwhoissittingonanotherstone.Heplanstovisit

大家好,又见面了,我是你们的朋友全栈君。

这一讲简单介绍一下Floyed算法。
话不多说,先放一道题帮助理解(其实是懒得描述具体应用场景)。
Frogger

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.

Input
The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy’s stone, stone #2 is Fiona’s stone, the other n-2 stones are unoccupied. There’s a blank line following each test case. Input is terminated by a value of zero (0) for n.
Output
For each test case, print a line saying “Scenario #x” and a line saying “Frog Distance = y” where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.
Sample Input

2
0 0
3 4

3
17 4
19 4
18 5

0

Sample Output

Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414

严格来说,这并不是一道标准的Floyed题,题意是:在所有通路中,找到每一条通路中的最大距离,在这所有的距离中,找到一个最小值。
之所以也放到这里,首先是因为Floyed算法标志性的三重循环,其次也是想借此拓展一下该算法灵活的应用方式


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define maxsize 1010
#define inf 99999999
int x[maxsize],y[maxsize],sum=1;
double dis[maxsize][maxsize];//用来记录任意两点通路的单步最大长度

//计算两点间的距离
double caldistance(int x1,int y1,int x2,int y2)
{
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
int main()
{
    int m;
    while(scanf("%d",&m)!=EOF)
    {
        if(m==0)
        {
            break;
        }
        int i,j,k;

        //输入每个点的坐标
        for(i=1;i<=m;i++)
        {
            scanf("%d %d",&x[i],&y[i]);
        }

        //计算任意两个点间的距离
        for(i=1;i<=m;i++)
        {
            for(j=i;j<=m;j++)
            {
                if(j==i) dis[i][j]=0;
                else
                dis[i][j]=dis[j][i]=caldistance(x[i],y[i],x[j],y[j]);
            }
        }
        //算法标志性的三重循环
        //特别暴力的找到所有情况然后更新
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=m;j++)
            {
                for(k=1;k<=m;k++)
                {
                    if(dis[j][k]>max(dis[j][i],dis[i][k]))
                    {
                        dis[j][k]=max(dis[j][i],dis[i][k]);
                        //注意i,j,k的顺序和位置,最初写错了,怎么都找不到问题错在哪里,一定要注意,
                        //如果是找最短路径的正宗Floyed,比较的就是dis[j][k]和dis[j][i]+dis[i][k]的大小,取小的那个
                    }

                }
            }
        }

        printf("Scenario #%d\nFrog Distance = %.3f\n\n", sum++, dis[1][2]);
    }
    return 0;
}

这个题巧妙的一点改动就实现了功能的“巨大”改变。

算法的核心就是那个三重循环及其嵌套顺序。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/147969.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • linux设备驱动程序第四部分:从如何定位oops对代码的调试方法,驱动线「建议收藏」

    linux设备驱动程序第四部分:从如何定位oops对代码的调试方法,驱动线

  • 6种不同画法画平行线_平行线的画法_中小学试题|家庭教育题库|辅导习题「中国戏曲学院附属中等戏曲学校」…

    6种不同画法画平行线_平行线的画法_中小学试题|家庭教育题库|辅导习题「中国戏曲学院附属中等戏曲学校」…平行线怎么画第五章《数学活动1》—-你有几种画平行线的方法【活动理念】通过让学生积极参与此次活动,获得成功的体验,感受活动课的乐趣.通过观察、操作、推理归纳,让学生进一步知道相交线、平行线以及垂线的概念,利用平行线的判定解决一些实际问题,利用平移可以绘制一些优美的图案等.【活动目标】一、知识与技能1、两直线平行的条件,掌握两种以上最快捷的画平行线的方法.2、进一步理解相交线、平行线以及垂线的概…

  • 玩转挖矿:家庭矿机组装全攻略!

    玩转挖矿:家庭矿机组装全攻略!离上次发挖矿的教程已经过去两个多月了。这两个多月发生了什么事情呢?特斯拉买入15亿美刀BTC美图也不修图买BTC和ETH去了美国一大波ETF申请中加密币交易所coinbase快要上市了20多万一枚的比特币冲到了40万2100一张的二手1660s涨到4000多了…..这段时间我也没有闲着,断断续续收了十几张卡,装了三台矿机。趁着第一波投入已经回本的好心情,给大家分享一下装显卡矿机的经验。(不做投资建议,不送显卡,要不要高位站岗完全看你们自己!)我本来是没时间来.

    2022年10月22日
  • 为什么我用LaTeX排版的那个双引号编译出来很奇怪,如下图,怎么做才能出现对的?[通俗易懂]

    为什么我用LaTeX排版的那个双引号编译出来很奇怪,如下图,怎么做才能出现对的?[通俗易懂]为什么我用LaTeX排版的那个双引号编译出来很奇怪,如下图,怎么做才能出现对的?)我是个LaTeX小白,百度了很久,没有解决办法,求救。引号是在英文输入法下输的,左引号连按两次esc下边那个键,右引号连按两次enter左边那个键。…

  • webpack基础打包命令_webpack打包原理

    webpack基础打包命令_webpack打包原理没有配置文件的打包如果我们没有使用配置文件webpack.config.js,那么我们就需要通过命令来打包案例我们首先创建一个webpackTest文件夹,然后在文件夹中再创建2个子文件夹dis

  • 一阶惯性滤波特点_传递函数的固有频率怎么求

    一阶惯性滤波特点_传递函数的固有频率怎么求文章(一)一阶惯性环节采用后置反馈的方式可以实现较精确的系统跟踪性能。上述系统的传递函数为因此启动性能良好,另,一阶惯性环节无超调量,因此可通过修改反馈参数实现最优的跟踪性能。因此在针对温度等变化较小的物理量方面的控制上是较占优势的,但精确跟踪也就意味着出现高频干扰、低频干扰、白噪声时,传感器也会精确地将这些干扰输出。这对一些容易受到干扰的系统是极为不利的。如下图为加入高频正弦信号后上述系统的输出(幅值为1,频率为1000(rad/sec))可见,系统虽然有一定的滤.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号