哥尼斯堡七桥问题解法_酒分之一实验室

哥尼斯堡七桥问题解法_酒分之一实验室 JOJ1200Jugs题目链接:http://acm.jlu.edu.cn/joj/showproblem.php?pid=1200题目的意思是,有两个容器,容量分别为ca和cb,cacb,初始时两个容器都是空的,水无限量供应,问如何用这两个容器量出n单位的水放在容量为cb的那个容器中?这个题目给出的数

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

 

JOJ 1200 Jugs 题目链接: http://acm.jlu.edu.cn/joj/showproblem.php?pid=1200

题目的意思是,有两个容器,容量分别为 ca cb ca < cb ,初始时两个容器都是空的,水无限量供应,问如何用这两个容器量出 n 单位的水放在容量为 cb 的那个容器中?

这个题目给出的数据是保证有解的,而且看到这个题目的人都会想到用搜索来解决这个题目。搜索也很简单,最容易想到的自然是广度搜索,直觉上这个问题和汉诺塔问题很像,也可能用类似汉诺塔那样的算法。在搜索时状态就是当前两个容量的水量 wa wb ,如果 wb 不等于 n ,则执行所允许的六种操作: fill a, fill b, empty a, empty b, pour a b, pour b a 。这个题目 AC 的代码正是用的广度搜索。

现在作为一个有趣的数学问题来看,分析一下它有什么性质。这个问题是有名的泊松分酒问题。在网上有一篇文章对此类问题作了深入分析,这篇文章是:

http://blog.sina.com.cn/s/blog_41482c9f0100cts1.html

但那些问题与这个题目的情境略微不同。对于这个题目,自己有以下几个问题非常想弄明白:

1.       fill empty 操作是填满或者清空容器, pour 操作是把一个容器的水倒入另一个直到另一个满或这个容器空。所以,很显然,任何时候,两个容器或者一个为空,或者一个为满。

2.       这个问题在什么情况下必定有解,在什么情况下必定无解。 n > cb 时必定无解,有没有一个值 n0 使得 n < n0 时也必定无解?

3.       如果能够量出 k 单位的水,是否也一定能够量出 mk 单位的水,其中 m 是正整数并且 mk <= cb

4.       直觉上这个题目和两个容量 ca, cb 的最大公约数有关,欧几里德算法在这里是否有用。 ( 并且上面给出的文章链接也介绍了二元一次不定方程的方法,二元一次不定方程的结果就是这两个数的最大公约数的倍数 )

数学功底太浅,只能想到这些问题并且都没办法证明。暂时把问题记在这里,待学习一段时间再回头来看。

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

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

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

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

(0)


相关推荐

  • Ubuntu中搭建ICE服务器(Coturn)

    Ubuntu中搭建ICE服务器(Coturn)1.WebRTC的P2P穿透WebRTC的P2P穿透部分是由libjingle实现的.步骤顺序大概是这样的:尝试直连.通过STUN服务器进行穿透无法穿透则通过TURN服务器中转STUN服务器比较简单.网上也有很多公开的STUN服务器可以用于测试,例如:stun.ideasip.com在WebRTC的P2P应用中,使用公开的STUN服务器时,有时响应比较慢,这就需要自己搭一个…

  • response contentType值的问题

    response contentType值的问题response,contentType,UTF-8,ISO-8859-1

  • 所谓的CS和BS_CS程序

    所谓的CS和BS_CS程序    我们在步入CSharp之后,新接触了CS和BS这两个概念,今天小编就给大家分享一下有关CS和BS的知识,如有雷同不胜荣幸  CS:即Cilent/Sever(客户机/服务器)结构,CS在技术上很成熟,主要特点是交互性强,具有安全的存取模式,响应速度快,利于处理大量数据,但是灵活性不好,管理和维护费用高,通常用于小型局域网络。  BS:即Browser/Sever(浏览器/服务器)结…

  • MySQL索引的使用实例

    MySQL索引的使用实例前言这是我听老师讲课做的笔记,考试要看的。这是视频地址作者:陈运智关注我的csdn博客,更多Linux笔记知识还在更新本人只在csdn写博客配套这篇文章观看效果更佳MySQL索引的使用实例一.慢查询日志二.查询分析器——explain三.索引的基本使用四.复合索引五.覆盖索引一.慢查询日志//查看是否开启慢查询日志mysql>showvariableslike’%slow%’;//临时开启慢查询日志mysql>setglobalslow_q

  • 【学生信息管理系统】与后端系统接口

    【学生信息管理系统】与后端系统接口

  • 《前端运维》二、Nginx–3静态资源服务、跨域与其他「建议收藏」

    一、静态资源服务首先,静态资源一般是指客户端发送请求到Web服务器,web服务器从内存中取得相应的文件,返回给客户端,客户端解析并渲染出来。动态资源呢,则是由客户端发起请求,先交由web容器,web

发表回复

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

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