[今天我们思考8]

[silwile]

Let's go on:)

前面在[今天我们思考6]里的第二题还没有人给出一个比较好的答案，在这里顺便提一下，那是一个很好的问题。存在一种很简洁的策略，使得两个人玩这个游戏不需要很大的计算量(也就是说，只要我们从大街上顺便sample两个人，告诉他们这个策略，他们就可以成功地玩好这个游戏:-)。什么时候闲着，就多想想这个问题吧。就像pongba一直说的，重要的不是一个问题的答案本身，而是我们去求解问题的过程本身： 即在我们最终成功地解决了一个问题后，得回过头去看看我们在求解这个问题时走过了一条怎样的路，在走这条路的过程中，是不是有某种规则在指导着我们，这些规则到底是什么，它们是不是对一般性的解题具有指导意义，我们能不能以把它们成功地传授给别人； 当然，有很多时候，当我们虽然非常努力的去求解一个问题，但仍然未果。然后看到了别人的求解结果，或恍然大悟，或拍案叫绝。这时，我们也要回头看看自己求解问题的过程，到底是什么妨碍了我们成功的抵达问题的最终解的 。是仅仅因为不知道某一个知识点（比如如果不知道正圆柱体是什么样的图形，大概很难求解出"精确地确定杯中的水是不是半杯"这个问题），还是因为知道的知识点反而限制了我们的思考时的思维（比如pongba提到的那个拾荒者游戏的那个问题）；是因为我们的联想能力不够？类比能力不够？可视化能力不好？观察能力不够？归纳能力不够？发散性思维不好？...如果真是这样，那么这些所谓的能力到底有没有可塑性，还是由生来的神经元及其连接决定了的；如果有可塑性，那么是在多大程度上？存在什么好的方法吗？

好了，接下来我们还是一起来做题吧。两个都是小题目，但也不是那么简单的:-)

1.现在你在一条大河边，有一个4升和一个9升的杯子，以下容量的水那些是可以成功倒出来的： 1,2,3,4,5,6,7,8,9? 如果是一个a升 的杯子，一个b升的杯子，a,b都是整数。那么你能成功倒出的水的容量应该满足什么样的条件？

2.现在你在一个房间里，屋外有10个人。你一次可以叫他们中的一个人进来，如果这个人在屋外的话；或者可以叫他们中的一个人出去，如果这个人在屋里的话。初始时刻，你的房间里只有你一个人，他们10个人都在屋外。问是否存在这样的一种策略，使得他们10个人的所有的不同配置都能在你的房间里出现（所谓他们10个人的配置，即为由他们10个人组成的集合的所有子集）？如果存在，你该怎么做？如果不存在，请说明理由。

Have fun :-)

[windstorm]

第一题1,2,3,4,5,6,7,8,9都可以，那个条件.......是不是b%a到b都可以？假设b比a大

吃完饭看看第二题

2008/4/19 silwile <sil...@gmail.com>:

--
web: http://www.forwind.cn
msn: likunarmstrong at hotmail.com

[王小康]

第一题相当easy,有一定理,说的就是这个,并且可以推广.
说,又A升和B升的杯子各一个,问能否导出C升水来.
只要A和B的最大公约数能整除C,那么就可以倒出来.lol,可以推广到n个杯子的情形.

但是至于怎么倒出来,这个就不好弄了.
4升和9升的杯子,可以倒出所有正整数升的水.

在08-4-19，windstorm <likunar...@gmail.com> 写道：

--
http://egmkang.cnblogs.com/

[王小康]

第二题.存在.
因为你可以叫一个人出去(存在),叫一个人进来(也是存在).但是并没有人数的限制.也就是说,你可以连续叫进来n个人,只要那些人都在外面等着你~~~
那么,可以先不叫人,就是空集,第一个子集;
分别叫进来1,2,......10,中间夹杂叫1,2,....9出去的动作,工10个子集;
在分别叫12,13,...............等等,包含两个人的子集.
....
以此类推,共2^10个子集.
看看对不?

在08-4-19，王小康 <egm...@gmail.com> 写道：

--
http://egmkang.cnblogs.com/

[windstorm]

Yes, I think 存在这样的一种策略，使得他们10个人的所有的不同配置都能在你的房间里出现

2008/4/19 silwile <sil...@gmail.com>:

[alai]

TAOCP, Vol4, 7.2.1.1, 格雷码就可以满足这个条件

在 08-4-19，windstorm<likunar...@gmail.com> 写道：

[silwile]

对，这个定理是正确的。
关键是你是怎么推出这个定理的？推一下试一试，也许你会发现这个推理蛮有意思的。

2008/4/19 王小康 <egm...@gmail.com>:

[王小康]

这个需要数论知识,可是我对数论一窍不通........

在08-4-19，silwile <sil...@gmail.com> 写道：

--
http://egmkang.cnblogs.com/

[silwile]

yes, it is  actually  the Gray Code.
so this problem becomes easy for guys who study in computer science.

一个很好的编程联系就是写个小程序产生满足条件的格雷码。

2008/4/19 alai <ala...@gmail.com>:

[just4fan]

第一题不太明白，如果题设的要求是只有这两个容器那么貌似只有1，4，5，8，9可以被倒出来吧

[windstorm]

都可以的。再算算。

2008/4/21 just4fan <just...@gmail.com>:

> 第一题不太明白，如果题设的要求是只有这两个容器那么貌似只有1，4，5，8，9可以被倒出来吧
>
> >
>

--

[TeEmo]

尝试着推理一下。
要用A升和B升的杯子各一个,导出C升水来。从数学的角度来看，也就是要满足：| m*A - n*B | = C(m, n均为非负整数)，即A的m
倍与B的n倍之差的绝对值要等于C。
我们设r为A和B的最大公约数，令A = p*r，B = q*r，其中p、q均为正整数，那么上式可以化为：| m*p - n*q | * r
= C。
如果C能够被 r 整除，那么式 | m*A - n*B | = C 就成立，我们也就可以用A升和B升的杯子各一个，导出C升的水。

[windstorm]

这个应该属于知道了答案推证明吧，如果一开始不知道答案的时候，怎么去想到这个"最大公约数"？

2008/4/28 TeEmo <teem...@gmail.com>:

[hujing]

最大公约数的计算过程就是一个互相倒水的过程。

On Apr 19, 10:09 pm, alai <ala...@gmail.com> wrote:
> TAOCP, Vol4, 7.2.1.1, 格雷码就可以满足这个条件
>

> 在 08-4-19，windstorm<likunarmstr...@gmail.com> 写道：

>
> > Yes, I think 存在这样的一种策略，使得他们10个人的所有的不同配置都能在你的房间里出现
>

> > 2008/4/19 silwile <silw...@gmail.com>:

[hujing]

最大公约数的计算过程就是一个倒水过程。

On Apr 19, 2:51 pm, silwile <silw...@gmail.com> wrote:
> Let's go on:)
>

> 前面在[今天我们思考6<https://groups.google.com/group/pongba/browse_thread/thread/3601904ca...>
> ]里的第二题还没有人给出一个比较好的答案，在这里顺便提一下，那是一个很好的问题<https://groups.google.com/group/pongba/browse_thread/thread/8410bf55b...>。存在一种很简洁的策略，使得两个人玩这个游戏不需要很大的计算量(也就是说，只要我们从大街上顺便sample两个人，告诉他们这个策略，他们就可以成功地玩好这个游戏:-)。什么时候闲着，就多想想这个问题吧。就像pongba一直说的，重要的不是一个问题的答案本身，而是我们去求解问题的过程本身：