| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1006 人关注过本帖, 1 人收藏
标题:求杨大哥证明
只看楼主 加入收藏
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
结帖率:95.24%
收藏(1)
已结贴  问题点数:50 回复次数:11 
求杨大哥证明
话说 Tom 和 Jerry 向来不合。虽然 Tom 一直想尽办法要捉到 Jerry,但总是事与愿违。

这次 Tom 又把 Jerry 困到了一个圆形池塘的正中央,Jerry 能够再次成功逃脱么?我们知道,猫是不会游泳的,Tom 也不例外。


我们已知池塘的半径为 R,Jerry 速度是 1,Tom 的速度是 N。由于到了岸上后,Jerry 可以借助灌木丛进行掩护,所以只要 Jerry 到达岸边的时候,Tom 没有到达 Jerry 的身边,我们就认为 Jerry 可以成功逃离。并且 Tom 和 Jerry 在以往的冲突中积累了丰富的经验,我们认为他们都足够聪明。这里,我们不考虑 Tom 和 Jerry 的体力问题。

为了简化问题,我们假设 R 和 N 都是整数。

输入
输入包含多组数据。
每行一组数据。每行两个正整数 R 和 N(1 <= N,R <= 109),为池塘的半径和 Tom 的速度。
当 R = N = 0 时输入结束。

输出
对于每组数据输出一行,如果 Jerry 一定能够逃脱,则输出 "Yes",反之输出 "No"(不输出引号)。

顺便问一下  那种角速度方法对不
搜索更多相关主题的帖子: 成功 大哥 
2012-03-28 18:04
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:25 
呵呵,等一下,我来组织一下语言

重剑无锋,大巧不工
2012-03-28 18:35
君莫笑
Rank: 2
等 级:论坛游民
帖 子:22
专家分:58
注 册:2012-3-2
收藏
得分:0 
虚心求教
2012-03-28 18:50
silent_world
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:258
专家分:1138
注 册:2011-9-24
收藏
得分:0 
呵呵,这个问题思路如下:
1、如果Jerry在池塘中拐弯,会相对浪费时间。
   可以证明,一个三角形一边固定,角度设定的情况;
2、从tom的对面逃生机会最大。
   可以证明。
3、剩下的仅仅是一个简单的C语言而已。

若有遗漏,欢迎指出讨论。
2012-03-28 19:13
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
回复 4楼 silent_world
呵呵  看来你的思路是从Tom对面沿着半径方向逃离啦

                                         
===========深入<----------------->浅出============
2012-03-28 19:39
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:25 
呵呵,我小学看过的一本数学书上有一道类似的题,不过当然没这么复杂,不过为这道题倒是提供了一个思路

首先,老鼠围着一个小的圆游并保证老鼠游这个圆所花费的时间=猫走一大圈的时间,2*pi*r1=2*p1*r/N   -->   r1=r/N;
图片附件: 游客没有浏览图片的权限,请 登录注册

然后老鼠把这个圆缩小无限小,即r1'=r1-1/无穷大,这样由于老鼠游一圈所花的时间比猫要少,所以他就能随意调整自己和猫的相对位置,而当到了图中位置时无疑是最好的(这个用画图画的。,。不解释了)

此时如果(r-r1')/1<pi*r/N,即N<pi+1则能逃脱,否则失败
2012-03-28 20:17
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
久等了,造句一直不是我的强项。
先看看这个问题的AC代码。
程序代码:
#include<stdio.h>
int main()
{
    int n;
    while(scanf("%d%d", &n, &n), n)//不要怀疑这句,就是这样。看不懂说明你的基础还很差,继续努力吧
    puts(n <= 4 ? "Yes" : "No");
    return 0;
}

是不是极度简单?但简单的只是它的外表。

这只是冰山浮出水面的一角。我们来看看支撑这简单一角下面的理论基础是什么吧。

Tom 和 Jerry 足够聪明。这句话不起眼,但却是一个很关键条件。

这意味着双方完全明白自己和对方能采取哪些策略,以及自己采取某一策略后对方会如何应对。所以不要耍小聪明。

这是博弈论的一个重要题设。

对于Tom来说,它的目的是抓住Jerry。为实现这一目的它的策略就是随时保持与Jerry的距离最短。

对于Jerry来说,它的目的是逃离池塘不被Tom抓到。为实现这一目的它的策略是尽量靠近池塘边缘并尽量与Tom保持足够远的距离。

这一问题的结构决定了在极坐标系下分析它更合适。

设Jerry在池塘中的位置到中心的距离为r,则它与池塘边缘的最大距离为r + R(R为池塘半径)。这也是Jerry在池塘该位置里能与Tom保持的最大距离。

由于Tom和Jerry的线速度是有上限的,并且不等。所以Jerry不可能在池中任何位置都与Tom保持在最大位置,越靠近池边Jerry运动的角速度越小,Tom将有机会绕到近处。

那么Jerry能保持的这个最大距离中的r到底可以有多大呢?Jerry的最大速度为1,这个速度可以分解为两个速度的矢量和,一个平行于极径指向外,一个垂直于极径。

平行于极径的速度分量使得Jerry靠近池塘边,垂直于极径的速度分量用于与Tom周旋。

两个速度的和是一个定值,所以当Jerry的速度全部用于与Tom周旋时将达到r的最大值。

此时Tom和Jerry的角速度相同,即

N / R == 1 / r

==> r = R / N

这时,Jerry距离池塘边还差R - r == R * (1 - 1 / N)

Jerry要做的就是在Tom到来前先上岸,它该以什么方式上岸呢?

直接沿最短距离R - r游上岸,这样它用的时间最短(在数量上所用时间也等于R - r)。但同样这时Tom跑到它面前所需要的时间也是最短的。

沿一条螺线游上岸,Tom会不会需要的时间更长一些?会。但同样Jerry上岸需要的时间也更长。具体该怎么做,需要分析一下了。

设Jerry以与极径保持u的夹角向岸边极力游去。

这时,Jerry游到岸边需要的时间为Tj = (R - r) / cos(u)

Jerry游过的角度是一个定积分式

w = S(sin(u) * dt / ( r + cos(u) * dt))[0 -> Tj]

==> w = ln(R - r) * tan(u)

这时Tom追到Jerry上岸的地点所需时间为Tt = (ln(R - r) * tan(u) + PI) * R / N

我们希望Tt 尽量大于 Tj, 即

sin(u) * ln(R - r) + PI * cos(u) > R * (R - r) / N

由于r = R / N,上式右边是常数,那么就代入左边

sin(u) * ln(N / (N - 1)) + PI * cos(u)

由于N为整数,当N > 1时,ln(N / (N - 1)) < PI,所以上式取最大值时u为0。

所以Jerry沿直线游向岸边是最佳策略。

由此,Jerry想成功逃跑的条件就是

R - r < PI * R / N

==> R * (1 - 1 / N) < PI * R / N

==> N < PI + 1

由这个推导过程可以看出,决定Jerry能否逃跑的因素与池塘的大小无关,只与Tom的速度有关。

由于N的取值为整数,所以在我的代码中上面条件简化成了 N <= 4。

重剑无锋,大巧不工
2012-03-28 20:50
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
回复 6楼 czz5242199
首先谢谢草兄弟   也谢谢杨大哥   总结一下这两天做题的错误

昨天:判断字符串的八进制数 我写的是 if(a[i]>='0' && a[i]<='9')

今天:一个数除另外两个数相除的结果  比如x除y/z的结果  我写的是  x/y/z


说说猫和老鼠的这个题   之前已经想到这种思路了  我是这样想的


老鼠的最优策略是和猫周旋到角速度相同的点   然后半径方向逃跑  并且二者连线经过圆心


因为老鼠在圆心的角速度是无穷大的  在达到相同角速度之前都是比猫的角速度大  所以二者一定可以周旋到上述状态


于是我就求出了老鼠的达到和猫相同角速度时的半径 但是我是这样求的  r1 = 1/N/r


1是老鼠的线速度  N是猫的线速度  r是大圆的半径  呵呵 这一求救注定Wrong Answer了

[ 本帖最后由 laoyang103 于 2012-3-28 20:53 编辑 ]

                                         
===========深入<----------------->浅出============
2012-03-28 20:51
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
呵呵,我猜小曹也会来的。这算是物以类聚、人以群分吧
我还在等你对炮兵阵地那个问题的解答。呵呵,我的WA让我很郁闷,很想知道问题所在。

重剑无锋,大巧不工
2012-03-28 21:16
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
回复 9楼 beyondyf
那道题我以前做过的,本来准备昨天复习一下写个解析,估计自己都忘得差不多了,但这两天刚好学院里事情比较多,就没写了,得再过几天才行,到时候在好好看看杨大哥的代码
2012-03-28 22:08
快速回复:求杨大哥证明
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.051585 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved