冒泡发一题（正解在3楼、4楼）

36675 · 发表于 2016-12-29 19:19:38

本帖最后由夜布郎于 2016-12-30 18:41 编辑
桌上有10枚正面朝上的硬币，假设每次只能翻转且必须其中的7枚硬币，至少需要几次才能使全部为反面朝上？步骤是什么？

41994 · 发表于 2016-12-29 21:45:12

至少需要4次，我做出来两种方法：
（用1表示正面，0表示反面，则开始时为1111111111）
第一种：
①0000000111
②0001111000
即0000001111
③0111110011
即0001111111
④0000000000
第二种：
①0000000111
②0011111001
即0000111111
③1111000111
即0001111111
④0000000000
由于一次翻7（奇数）个硬币
第一次必为0000000111反面朝上为奇数
第二次有4种：0000001111，0000111111，0011111111，1111111111（当然我只是举出这种情况）反面朝上为偶数，但无法得到0000000000
第三次只能得到反面朝上为奇数的情况，所以也无法得到0000000000
那么翻4次应该为最少次数了

39673 · 发表于 2016-12-29 22:02:15

最后一次翻动前必然是 3up,7down.  第一次翻动后的结果也必然是 7up,3down. 那么问题就变了:
[10, 0]  -> [3,7]  -> 翻转n次 -> [7,3] -> [0,10].
注:[up, down]
假设是n = 1.  则在当前是[3, 7]下,只有以下4种情况
(-3,-4) => [4, 6] ,
(-2,-5) => [6, 4],
(-1,-6) => [8, 2],
(-0,-7) => [10, 0];
可以看出n = 1,不成立及 (-x, -y) => [3-x +y,  10 - (7-x +y)]  &&  x + y = 7 &&  x 小于等于 up, && y 小于等于 down.
那么 n = 2,
对 [4, 6]  使4 - x + y = 7成立.  则 y - x = 3; => (x=2  ,y=5), nice
对 [6, 4]  使6 - x + y = 7成立,  则 y - x = 1; => (x=4  ,y=3), nice
...
所以解就是
最少需要4(2+2)次.
步骤是 [10, 0]  -> [3,7]  -> [4, 6]/[6, 4]/...  -> [7,3] -> [0,10].

41369 · 发表于 2016-12-29 21:42:20

两次吗？

[逻辑推理] 冒泡发一题（正解在3楼、4楼）