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

哥尼斯堡七桥问题解法_酒分之一实验室 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)


相关推荐

  • clion永久激活码【2021免费激活】

    (clion永久激活码)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

  • 离散傅里叶变换和离散时间傅里叶变换_离散傅里叶变换求相位

    离散傅里叶变换和离散时间傅里叶变换_离散傅里叶变换求相位1.离散时间傅里叶变换的导出针对离散时间非周期序列,为了建立它的傅里叶变换表示,我们将采用与连续情况下完全类似的步骤进行。考虑某一序列$x[n]$,它具有有限持续期;也就是说,对于某个整数$

  • Android学习(简单使用Bottom Navigation Activity来实现底部导航栏)

    Android学习(简单使用Bottom Navigation Activity来实现底部导航栏)在我们实际编写程序时,不必每一个activity都要从零开始,利用好系统自带的模板往往可以起到事半功倍的效果。下面我们就来看看如何使用BottomNavigationActivity来完成简单的底部导航栏功能。先来看一下效果图吧:创建activity首先在创建面板,我们选择然后next,finish就OK了。创建成功以后我们来运行一下,发现已经基本实现了底部导航栏的功能了!但是还没有结…

    2022年10月31日
  • 10 种机器学习算法的要点(附 Python 和 R 代码)「建议收藏」

    10 种机器学习算法的要点(附 Python 和 R 代码)「建议收藏」前言谷歌董事长施密特曾说过:虽然谷歌的无人驾驶汽车和机器人受到了许多媒体关注,但是这家公司真正的未来在于机器学习,一种让计算机更聪明、更个性化的技术。也许我们生活在人类历史上最关键的时期:从使用大

  • node.js第十课(HTTPserver)

    node.js第十课(HTTPserver)

  • java c socket通信 中文乱码解决「建议收藏」

    java c socket通信 中文乱码解决「建议收藏」前言(扯淡)作为一个一直从事Java的人来说,突然做C++很多地方都是乱撞墙,就发送的这个乱码就让人感到十分头秃,昨天跟老板对话,老板说不行咱就花钱找别人做。。。能力别质疑的感觉真是让人糟心啊–不扯太多,程序员节快乐,大家一起头秃吧。。虽然我并不想秃。问题言归正传,c++接收信息是gb2312,Java发数据是UTF-8,我Java接收数据没有问题,但是发给C++就遇到乱码问题…

发表回复

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

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