一个袋子,有 m 个红球,n 个黑球,每次取出两个球,如果球的颜色相同则将取出的球遗弃,并且红球数量+1,如果取出的球的颜色不同,那么红球数量-1,取出的球放回,问最后剩下的那个球的颜色是什么?计算方式是怎么样的?
各位有思路吗?说是会有一个公式可以确定结果,咋做呀
1
yagokoro 2017-11-22 16:36:39 +08:00 via Android 1
答案:m,n 是否均大于等于 1,n 是否为奇数
|
2
fffflyfish OP @yagokoro 怎么说?
|
3
sensui7 2017-11-22 16:40:55 +08:00
网游武器锻造, 开箱子的算法吗
|
4
yagokoro 2017-11-22 16:44:40 +08:00 via Android
|
5
fffflyfish OP @sensui7 额,啥意思?我当时被问蒙了,还是这种看起来很数学的题目,脑子一片空白
|
6
takanasi 2017-11-22 16:50:07 +08:00
什么鬼题,如果里面只有一个红和一个黑岂不是无限循环了?
|
7
fffflyfish OP @yagokoro 你一说递归我就明白了,非常感谢,您教训的是,我脑子确实不灵光
|
8
am241 2017-11-22 16:51:57 +08:00 via Android
红黑的操作方式有三种[ -1, 0], [1, -2], [1, 0]
|
9
codexu 2017-11-22 16:53:49 +08:00
为什么我之前一家小公司也是这个题,只不过是确定的数字
|
10
yagokoro 2017-11-22 16:57:23 +08:00 via Android
@fffflyfish 抱歉我这刚才……态度太差言过了,大概就是看到这类问题先想临界情况就是 OTZ
|
11
fffflyfish OP @yagokoro 没关系,您能告知思路已经很感激了,非常感谢
|
12
binux 2017-11-22 17:18:09 +08:00 via Android
我不理解这里拿球做例子,红球还能+-1 的,无中生有吗
|
13
czheo 2017-11-22 17:25:58 +08:00
感觉不是确定的啊。
以 2 红 2 黑为例: 如果取出 2 黑, [剩下 3 红] 。 如果取出 1 红 1 黑或 2 红,都剩下 1 红 2 黑。 继续 1 红 2 黑的情况: 如果取出 1 红 1 黑, [剩下 2 黑] 。 如果取出 2 黑, [剩下 2 红] 。 所以,最后可红可黑。 |
15
xupefei 2017-11-22 17:37:29 +08:00 1
出题的人数学功底不足啊。红球的数量是一个真值,没有什么概率问题。
类似的概念错误经常出现在置信区间的计算里:真值永远是一个固定值,并不是什么“真值有 95%可能性在这个区间里”。 把谬误删除后剩下的问题应该是: 一个袋子,有 m 个红球,n 个黑球,每次取出两个球,如果球的颜色相同则将取出的球遗弃;如果取出的球的颜色不同,取出的球放回。最后剩下的那个球的颜色是什么? 答案是: i) m 和 n 都为偶数:没有球剩下。 ii) m 和 n 都为奇数:红黑各剩下一个。 iii) 一奇一偶:剩下奇数个的那种。 |
17
fffflyfish OP @binux 你这个关注点哈哈
|
19
fffflyfish OP @xupefei 这个题意的目的就是不管你怎么取,每次整体的数量都会减少一个,也就是说不管按照哪种方式取最后都会只剩下一个吧,m,n 值没有定,就是想让人确定出最后什么情况下会剩下哪个球
|
20
xhystc 2017-11-22 17:45:47 +08:00 via Android 1
题目的意思是要抓到袋子里就剩下一个球,而不是一种颜色,这样的话当袋子里黑球剩 2 个的话,无论红球有多少个,剩下的都会是红球,如果袋子里剩 1 或 3 个黑球,无论袋子里有几个红球,剩下的都是黑球,而黑球总是两个两个丢,所以黑球个数为奇数时剩黑球,反之剩红球
|
21
xupefei 2017-11-22 17:46:45 +08:00
@czheo #16 换种说法:
> 如果取出的球的颜色不同,那么红球数量-1,取出的球放回 这里的问题是,如果取出了红黑各一个,然后又放了回去,那么盒子里的红球数量没有变化。为什么红球数量会-1 ? 出题人改变了宇宙真理。 |
22
chairuosen 2017-11-22 17:47:56 +08:00 26
BB: R+1 B-2
RR:R+1 R-2 = R-1 RB: R-1 可见每次操作总数-1 所以最后一个球之前的状态是最后有两个球。 最后两个球的三种状态 BB BR RR BR=B BB= R RR = R 什么时候是 BR 呢?因为每次操作 B 都是两个减,则最开始 B 的数量 n 为奇数最后两个球一定是 BR。 所以 n%2==0?R:B |
23
fffflyfish OP @xupefei #21 我的错,描述有误,如果取出的球颜色不同,那么只放回黑色的球,红色的球扔掉。
|
24
l00t 2017-11-22 17:49:33 +08:00
这题我都没看懂。红球怎么+1-1 ?
|
25
acros 2017-11-22 17:56:12 +08:00
这题目好迷啊。
看流程,只有抓到两个黑的时候,才出现黑色减少红色增加,其他情况下都是红色减少黑色恒定。 总体趋势不是在红黑平衡<->红少黑多之间变化? 结果不应该是算概率吗,恒定的?! |
26
czheo 2017-11-22 17:56:38 +08:00
审题有误,最后剩下一个球,我还以为最后剩下一种颜色就停止了。。。
|
27
fffflyfish OP @l00t 重新组织了下语言,在 append,sorry 哈
|
28
binux 2017-11-22 17:57:40 +08:00 via Android
@fffflyfish 那取出两个黑球,红球怎么+1 ?无中生有吗
|
29
fffflyfish OP @acros 我当时也是用概率做的,然后一直往概率的方向想,如果能往递归的原理想想,比如#4,#22,就不至于答不出来了。。。
|
30
fffflyfish OP @binux 算是吧,你就当从别的地方拿来一个红球,然后扔进去嘛,只要满足颜色相同就可以这么干
|
31
Andiry 2017-11-22 18:01:44 +08:00 3
红球用 0 代替,黑球用 1 代替,最后剩下的值就是所有球的易或,所以只取决于黑球数量是奇数还是偶数
|
32
l00t 2017-11-22 18:02:32 +08:00
看了补充描述,那么看 n 是不是奇数。是奇数的话剩下的就是黑的。是偶数的话,那早晚黑的会全部取出,剩下的是红的
|
33
nigelvon 2017-11-22 18:04:14 +08:00
22 楼没毛病
|
34
acros 2017-11-22 18:10:20 +08:00
根据 append 重新列了下,22 对了~
|
35
ZxBing0066 2017-11-22 18:14:05 +08:00
红球数量+1-1 是指放一个或拿出一个红球?题目看的我蒙蔽
|
36
introom 2017-11-22 18:49:20 +08:00 via Android
这种题,到底是证明个什么
|
37
Tink 2017-11-22 18:57:10 +08:00 via iPhone
22 楼厉害
|
38
BlackCat02 2017-11-22 19:57:09 +08:00
22 楼正解,比我的解法简单明了多了
|
39
yuang 2017-11-22 20:17:17 +08:00
22 楼牛逼。我居然还写了段代码 才做出来。
|
40
xml123 2017-11-22 20:37:47 +08:00 1
22 楼说的很清楚了,不过其实还可以简化成一句话:
黑球数量的奇偶性不会改变,所有剩下的颜色是 n%2==0?R:B |
41
kdplus 2017-11-22 20:41:57 +08:00
这... 题目条件要分析分析撒,这关键黑球只有-2 的选项啊,n 是奇数的时候,必剩下黑球撒
|
42
chengchuan1009 2017-11-22 21:53:26 +08:00
31 楼简单明了
|
43
sensui7 2017-11-23 00:21:08 +08:00
@chairuosen 仰望, 我只能这样
|
44
scnace 2017-11-23 01:27:55 +08:00 via Android
异或解法 666666
|
45
66beta 2017-11-23 08:48:15 +08:00
受教了,希望多来点这种分享帖
|
46
xiaojunjor 2017-11-23 09:26:33 +08:00
厉害厉害,学习了
|
47
void1208 2017-11-23 09:26:38 +08:00
《编程珠玑》第四章出现过这道题,正好刚看的。。
|
48
LeoNG 2017-11-23 10:04:48 +08:00
受教了。
|
49
justicelove 2017-11-23 13:59:30 +08:00
自己瞎想的。
有三种情况: 红 黑 -1 0 +1 -2 -1 0 假设 mn 都很大,以上三种情况出现的比例则趋向于 1:1:1, 则总的趋势也就是平均红黑减少比例 红: 黑 = 1:2 如果 M < 1/2 N, 则剩下 N 也就是黑球的几率大 M = 1/2N 红黑都有可能 M > 1/2N 则红球几率大。 |
50
justicelove 2017-11-23 14:05:07 +08:00
#22 楼牛逼,N 的奇偶性不会变。66666
|
51
xiaoyao9933 2017-11-23 15:28:59 +08:00
#31 楼比 #22 楼还屌。。这题就是考 XOR 的。发现了问题的本质啊。
|