文档章节

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

吟啸_徐行
 吟啸_徐行
发布于 2013/01/09 19:59
字数 392
阅读 312
收藏 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
161
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
107
0
制作花肥方法大全 WYF收集整理

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

wx5a0cd1844a571
2017/11/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

jQuery学习笔记180924

jQuery - AJAX 简介 什么是 AJAX? AJAX = 异步 JavaScript 和 XML(Asynchronous JavaScript and XML)。 简短地说,在不重载整个网页的情况下,AJAX 通过后台加载数据,并在网页上进行显示...

颖伙虫
17分钟前
1
0
springboot整合vue小试牛刀

序 本文主要研究一下如何在springboot工程整合vue maven <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-we......

go4it
18分钟前
1
0
使用python的profiler工具

主要用来检测python coding的执行时间 fly profiler

steel7c4
22分钟前
0
0
大数据日知录笔记

硬件成本的快速下降,使得电子设备的无处不在成为可能,数据无处不在,无时不在. IBM用3V(Volume,Velocity,Variety)来描述大数据的特点,后来又增加了Value这个维度,即价值密度低的数据成为大数据...

凌渡
31分钟前
0
0
IDEA、WebStorm最新永久激活方式

今天早上一大早打开IDEA发现激活已过期,遂开始寻找激活码。但是一直不成功,后来终于找到一种比较靠谱的激活方式。在此记录下来,以备不时之需。 目前网上现有的激活方式大概有这么三种 激活...

耒耒耒耒耒
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部