娱乐 #0 数 学 算 法 挑 战 - 约束编程之 《木桶问题》

[AlGoRiThM]

（已经施工完毕，大家可以读题了~刚才一不小心点到了enter）

不得不说，居然看到了站里也有喜欢数学的人~虽然我不学数学，但是计算机数学不分家嘛~再加上我研究方向也离不开算法~

第一期出一个简单点的~我大三时候写过类似的但是复杂一些的题型，希望大家喜欢~复杂一点的我大概会在第二期做~

本来第一期想做数独的，但是太简单了，所以换一个~考虑到不是所有人都会写代码，所以就搞成了数学问题。

难度：简单：高中知识 / 困难：不知道，没上过国内大学

题目描述：

你有一个8升的木桶和两个分别可以装5升和3升的木桶.要求你在桶和桶之间倒水，把水一分为二，一次必须全部倒满或者倒完~（也就是说，有两个桶里需要有四升水）

简单：如何转移水才能使得条件达成？（也就是水一分为二）

困难：最少转移多少次才能使得条件达成？（添加了约束条件）

 

十二月 2, 2021，由abc602456615修改

[久帝]

8-5 8剩3 5满

5-3 5剩2 3满

3-8 8剩6 3空

5-3 5空 3剩2

8-5 8剩1 5满

5-3 5剩4 3满

3-8 8剩4 3空

一分为二 结束

[ymh9588]

还有另一个解，不过次数要多一次，

8-3；3-5；8-3；3-5；5-8；3-5；8-3；3-5 （具体每次每个杯子里有多少我懒得写了）

顺便再出一道题好了。有12个外观完全相同的小球，其中有11个重量相同，一个重量不同（不知是轻还是重）。有一个没有砝码的天枰，如何在仅使用三次天枰的情况下，找出重量不同的小球，并且确定那个小球到底是轻于其他的还是重于其他的。

[抓水母ty]

这种题只有三个桶，其实倒来倒去如果要不发生重复的情况的话，当你进行了一步，下一步就只有一个选择了，而第一步只有两个选择（A-B和A-C），所以后面就只有两种情况了，所以我用逻辑图画了出来（ABC分别为大中小桶，A-B意思是大桶往中桶倒水）

这两种方法就能把所有情况遍历出来了，而且其实就是一个从头开始遍历，一个从尾开始遍历，而题目中分成一半的情况刚好在所有情况的正中间，而两个方法一个7步（1楼方法）一个8步（2楼方法），所以7应该就是最少步了

咱不是学算法的，这种题没仔细研究过，如果发现错误，还请帮咱指出来了(*≧︶≦))(￣▽￣* )ゞ

[抓水母ty]

10 分钟前, ymh9588 说道:

还有另一个解，不过次数要多一次，

8-3；3-5；8-3；3-5；5-8；3-5；8-3；3-5 （具体每次每个杯子里有多少我懒得写了）

顺便再出一道题好了。有12个外观完全相同的小球，其中有11个重量相同，一个重量不同（不知是轻还是重）。有一个没有砝码的天枰，如何在仅使用三次天枰的情况下，找出重量不同的小球，并且确定那个小球到底是轻于其他的还是重于其他的。

你这题从小到大见过很多遍了，虽然我还是不记得答案

[水墨潇潇]

8-3；3-5；8-3；3-5；5-8；3-5；8-3；3-5 啊 好古老的小学题啊

[AlGoRiThM]

8 小时前, ymh9588 说道:

还有另一个解，不过次数要多一次，

8-3；3-5；8-3；3-5；5-8；3-5；8-3；3-5 （具体每次每个杯子里有多少我懒得写了）

顺便再出一道题好了。有12个外观完全相同的小球，其中有11个重量相同，一个重量不同（不知是轻还是重）。有一个没有砝码的天枰，如何在仅使用三次天枰的情况下，找出重量不同的小球，并且确定那个小球到底是轻于其他的还是重于其他的。

这题好像见过awa，好想是分三组测两组，平衡略

不平衡则有两种情况，简化后也就是A轻或者B重 （same when reversed)

然后用前两组各俩称量两组的第三个球和第三个组俩球 - A12B12, A3B3C12

根据不平衡可以确定小球轻还是重，如果平衡略

不平衡则根据小球重量，取第一和第二个的交集，确定小球所在区间 （应该是2个）

……逻辑有点乱，不知道对不对……

 

[ymh9588]

2 小时前, abc602456615 说道:

这题好像见过awa，好想是分三组测两组，平衡略

不平衡则有两种情况，简化后也就是A轻或者B重 （same when reversed)

然后用前两组各俩称量两组的第三个球和第三个组俩球 - A12B12, A3B3C12

根据不平衡可以确定小球轻还是重，如果平衡略

不平衡则根据小球重量，取第一和第二个的交集，确定小球所在区间 （应该是2个）

……逻辑有点乱，不知道对不对……

 

逻辑就是这样了，不过最后一步不平衡的时候是三个球里找，两轻一重或者两重一轻