转跳到内容

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


推荐贴

(已经施工完毕,大家可以读题了~刚才一不小心点到了enter)

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

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

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

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

题目描述:

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

简单:如何转移水才能使得条件达成?(也就是水一分为二)

困难:最少转移多少次才能使得条件达成?(添加了约束条件)

 

,由abc602456615修改
注释
Eternalcycle Eternalcycle 80.00节操
链接到点评
  • AlGoRiThM将标题更改为#0 数 学 算 法 挑 战 - 约束编程之 《木桶问题》

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

8-3;3-5;8-3;3-5;5-8;3-5;8-3;3-5 (具体每次每个杯子里有多少我懒得写了:huaji2:

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

链接到点评

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

-2021-12-02-122428.png-2021-12-02-122357.png

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

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

链接到点评
10 分钟前, ymh9588 说道:

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

8-3;3-5;8-3;3-5;5-8;3-5;8-3;3-5 (具体每次每个杯子里有多少我懒得写了:huaji2:

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

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

抓水母ty得到了穿越资格,兴奋过度从而砸坏了键盘.-2节操

链接到点评
8 小时前, ymh9588 说道:

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

8-3;3-5;8-3;3-5;5-8;3-5;8-3;3-5 (具体每次每个杯子里有多少我懒得写了:huaji2:

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

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

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

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

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

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

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

 

链接到点评
2 小时前, abc602456615 说道:

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

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

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

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

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

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

 

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

链接到点评
  • 骚男锁定了本主题
游客
此主题已关闭。
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款