文档章节

关于两容器倒水问题的感悟(ACM)

吟啸_徐行
 吟啸_徐行
发布于 2013/01/09 19:59
字数 392
阅读 318
收藏 0

纯个人感悟,解释错误的地方希望可以指出来,谢谢!这里是ACM的题目感悟,可惜不记得题目了,晕!估计做ACM的都见过容器倒水问题和捕捉神兽问题,以下就是这两个问题分析后的感悟:

两个杯倒水问题中,能否到处满意的水可以这样判断:

   抓神兽的问题中,将直线转化为2倍直线长度的圆考虑,也就是求神兽每次跳跃的n在长度为m的圆中能否跳到距标记起点position长度的地方(求余),现在的问题其实转化为求mn的最大公约数问题(因为:设m=a*y1,n=a*y2(这里a为最大公约数,y1y2互质,y1,y2的线性差可以构造出任意的整数),若是能到达position,则(t*n)%m=position(t,x为未知的整数)即:t*a*y2=a*y1*x+position(x为未知的整数),即:t*y2=y1*x+position/a)若要求t有解则a一定能被position整除,即:position要是m,n的最大公约数的倍数才有解。

  类似的可以推广到两容器倒水问题(将一个容器的水不停的往另一个容器倒的类似捕神兽的圆圈问题),也可以用所求水的容积是否为两容器的最大公约数的倍数(当然,所求体积不能大于最大容器的容量)。

© 著作权归作者所有

共有 人打赏支持
吟啸_徐行
粉丝 18
博文 109
码字总数 15832
作品 0
深圳
高级程序员
私信 提问
水壶问题(向水壶中倒z升水) Water and Jug Problem

问题: You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exac......

叶枫啦啦
2017/12/27
0
0
关于TCP流模式与UDP数据报文模式区别

“TCP是一种流模式的协议,UDP是一种数据报模式的协议”,这句话相信大家对这句话已经耳熟能详~但是,“流模式”与“数据包模式”在编程的时候有什么区别呢?以下是我的理解,仅供参考! 1、...

长平狐
2012/09/03
176
0
怎么用一个6升和5升的容器,称出3升的水

怎么用一个6升和5升的容器,称出3升的水 5升装满倒进6升桶 5-0 6-5 5升桶装满倒进6升桶 5-4 6-6 6升倒掉,5倒进6升桶 5-0 6-4 5装满倒进6升桶 5-3 6-6 完毕...

beves
2011/09/25
0
5
热门智力题 过桥问题和倒水问题

热门智力题 过桥问题和倒水问题 过桥问题和倒水问题都是笔试面试中的热门智力题,不但微软、GOOGLE、百度、腾讯等公司采用,甚至在IQ测试与公务员考试中都能见到。本文不但教你如何快速用手算...

长平狐
2012/12/10
130
0
制作花肥方法大全 WYF收集整理

豆渣沤肥——无臭!简单!零技术! 之所以豆渣沤肥让花友执着,是因为豆渣里富含蛋白质,可以降解成植物需要的氮,作为一种有机肥料还能改善土壤,复杂的成分可以给植物提供多种元素。但是也...

wx5a0cd1844a571
2017/11/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

区块链安全 - 以太坊短地址攻击

1 基础知识 EVM虚拟机在解析合约的字节码时,依赖的是ABI的定义,从而去识别各个字段位于字节码的什么地方。关于ABI,可以阅读这个文档: https://github.com/ethereum/wiki/wiki/Ethereum-C...

HiBlock
9分钟前
0
0
自定义函数及内部函数

变量的作用域 局部变量 global $Global及其他超全局数组 静态变量 仅初始化赋值 保留于内存直到response才销毁 global和static变量的区别 global:局部变量全局话 static:定义静态局部变量 函...

关元
10分钟前
0
0

中国龙-扬科
22分钟前
1
0
python包

https://www.lfd.uci.edu/~gohlke/pythonlibs/

陆朋
33分钟前
1
0
一文弄懂“分布式锁”,一直以来你的选择依据正确吗?

本文主要会关注的问题是“分布式锁”的问题。 多线程情况下对共享资源的操作需要加锁,避免数据被写乱,在分布式系统中,这个问题也是存在的,此时就需要一个分布式锁服务。 常见的分布式锁实...

Java干货分享
40分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部