博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
两个容积互质的水杯可倒出任意从1到容积和的水量
阅读量:5739 次
发布时间:2019-06-18

本文共 650 字,大约阅读时间需要 2 分钟。

即: 两个水杯A、B,容积分别为 x 和 y ,(x,y)=1。则可以通过相互倒水的方法倒出从1到(x+y)的任意自然数体积的水来。(假设睡无限)

例: x=5,y=3,倒出4升水。

  1. A倒满,B空: A剩5,B剩0
  2. A的水倒满B: A剩2,B剩3
  3. B倒空,A水倒至B:  A剩0,B剩2
  4. A倒满: A剩5,B剩2
  5. A的水倒满B:A剩4,B剩3   

 

数学证明:(转自:http://www.guokr.com/question/206848/)

第一种情况:水是无限量供应的。

假设现在有这样两个杯子,容积分别是x和y并且互质,那么对于任何整数a和b,下面的同余方程:(用==表示同余的符号)
z == a (mod x)
z == b (mod y)
都有解,这个结论叫做中国剩余定理,而且它的证明是个构造性证明,也就是说证明本身给出了一个解这个方程的办法。
现在假设x > y,a是需要的水的体积,令b = 0,解这个方程可以得到一个整数z。z除以y余数为0,所以只要用小杯装z/y杯水,然后向大杯中倒,大杯满了就全倒光再接着从小杯中续水,直到把z升水全部用完,大杯中剩下的就是a升水。
也就是说这类问题总是有解的,但是这个解可能不是最优的(用水最少或者折腾次数最少)。
第二种情况:水是有限的,比如大杯中一开始有x升,小杯中一开始有y升。
在这种情况下肯定需要第三个容器,如果这个容器足够大的话应该和第一种情况一样。
如果第三个容器比较小的话,那就需要更多的讨论了(比小杯还小、比小杯大比大杯小等等)。

转载地址:http://vpyzx.baihongyu.com/

你可能感兴趣的文章
htm5新特性(转)
查看>>
Linux-Centos启动流程
查看>>
php 设计模式
查看>>
后端技术精选 - 收藏集 - 掘金
查看>>
Laravel 服务容器
查看>>
mac安装kubernetes并运行echoserver
查看>>
多页架构的前后端分离方案(webpack+express)
查看>>
算法(第4版) Chapter 1
查看>>
前端技术选型的遗憾和经验教训
查看>>
“亲切照料”下的领域驱动设计
查看>>
SRE工程师到底是做什么的?
查看>>
解读:Red Hat为什么收购Ansible
查看>>
PHP json_encode() 函数介绍
查看>>
js动态设置元素高度
查看>>
Ossim下的安全合规管理
查看>>
DelphiWebMVC框架下BPL热部署实现
查看>>
C++与MySQL的冲突
查看>>
siki学习之观察者模式笔记
查看>>
PYQT窗口可视化编程
查看>>
单元测试
查看>>