某视频厂的面试题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2547 天前的主题，其中的信息可能已经有所发展或是发生改变。

一个袋子，有 m 个红球，n 个黑球，每次取出两个球，如果球的颜色相同则将取出的球遗弃，并且红球数量+1，如果取出的球的颜色不同，那么红球数量-1，取出的球放回，问最后剩下的那个球的颜色是什么？计算方式是怎么样的？

各位有思路吗？说是会有一个公式可以确定结果，咋做呀

第 1 条附言 · 2017-11-22 17:52:40 +08:00

可能是我描述有误，结合各位的意见我重述一下：
一个袋子，有 m 个红球，n 个黑球，每次取出两个球，如果球的颜色相同则将取出的球遗弃，并且从其他地方再找一个红球，扔进袋子里，如果取出的球的颜色不同，扔掉红球，黑球放回，问最后剩下的那个球的颜色是什么？

第 2 条附言 · 2017-11-23 11:26:50 +08:00

谢谢诸位，没想到会收到这么多关注，非常感谢！

取出

颜色

球

遗弃

53 条回复 • 2017-11-23 21:25:39 +08:00

yagokoro

2017-11-22 16:36:39 +08:00 via Android

答案：m,n 是否均大于等于 1，n 是否为奇数

fffflyfish

2017-11-22 16:38:09 +08:00

@yagokoro 怎么说？

sensui7

2017-11-22 16:40:55 +08:00

网游武器锻造, 开箱子的算法吗

yagokoro

2017-11-22 16:44:40 +08:00 via Android

@fffflyfish

n % 2 ？黑：红
直说，递归写过没；委婉的说，您可能不太适合创造性工作

fffflyfish

2017-11-22 16:45:42 +08:00

@sensui7 额，啥意思？我当时被问蒙了，还是这种看起来很数学的题目，脑子一片空白

takanasi

2017-11-22 16:50:07 +08:00

什么鬼题，如果里面只有一个红和一个黑岂不是无限循环了？

fffflyfish

2017-11-22 16:51:46 +08:00

@yagokoro 你一说递归我就明白了，非常感谢，您教训的是，我脑子确实不灵光

am241

2017-11-22 16:51:57 +08:00 via Android

红黑的操作方式有三种[ -1, 0], [1, -2], [1, 0]

codexu

2017-11-22 16:53:49 +08:00

为什么我之前一家小公司也是这个题，只不过是确定的数字

yagokoro

2017-11-22 16:57:23 +08:00 via Android

@fffflyfish 抱歉我这刚才……态度太差言过了，大概就是看到这类问题先想临界情况就是 OTZ

fffflyfish

2017-11-22 17:09:14 +08:00

@yagokoro 没关系，您能告知思路已经很感激了，非常感谢

binux

2017-11-22 17:18:09 +08:00 via Android

我不理解这里拿球做例子，红球还能+-1 的，无中生有吗

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 红] 。

所以，最后可红可黑。

Thexz

2017-11-22 17:27:41 +08:00 via iPhone

@sensui7 头像不错😂

xupefei

2017-11-22 17:37:29 +08:00

出题的人数学功底不足啊。红球的数量是一个真值，没有什么概率问题。
类似的概念错误经常出现在置信区间的计算里：真值永远是一个固定值，并不是什么“真值有 95%可能性在这个区间里”。

把谬误删除后剩下的问题应该是：

一个袋子，有 m 个红球，n 个黑球，每次取出两个球，如果球的颜色相同则将取出的球遗弃；如果取出的球的颜色不同，取出的球放回。最后剩下的那个球的颜色是什么？

答案是：
i) m 和 n 都为偶数：没有球剩下。
ii) m 和 n 都为奇数：红黑各剩下一个。
iii) 一奇一偶：剩下奇数个的那种。

czheo

2017-11-22 17:40:57 +08:00

@xupefei 题目里红球数量+-1 怎么没了？

fffflyfish

2017-11-22 17:42:26 +08:00

@binux 你这个关注点哈哈

xupefei

2017-11-22 17:42:33 +08:00

@czheo #16 红球的数量是个真值，有多少就是多少。还能人为设定的？

fffflyfish

2017-11-22 17:45:14 +08:00

@xupefei 这个题意的目的就是不管你怎么取，每次整体的数量都会减少一个，也就是说不管按照哪种方式取最后都会只剩下一个吧，m，n 值没有定，就是想让人确定出最后什么情况下会剩下哪个球

xhystc

2017-11-22 17:45:47 +08:00 via Android

题目的意思是要抓到袋子里就剩下一个球，而不是一种颜色，这样的话当袋子里黑球剩 2 个的话，无论红球有多少个，剩下的都会是红球，如果袋子里剩 1 或 3 个黑球，无论袋子里有几个红球，剩下的都是黑球，而黑球总是两个两个丢，所以黑球个数为奇数时剩黑球，反之剩红球

xupefei

2017-11-22 17:46:45 +08:00

@czheo #16 换种说法：
> 如果取出的球的颜色不同，那么红球数量-1，取出的球放回
这里的问题是，如果取出了红黑各一个，然后又放了回去，那么盒子里的红球数量没有变化。为什么红球数量会-1 ？
出题人改变了宇宙真理。

chairuosen

2017-11-22 17:47:56 +08:00

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

fffflyfish

2017-11-22 17:49:11 +08:00

@xupefei #21 我的错，描述有误，如果取出的球颜色不同，那么只放回黑色的球，红色的球扔掉。

l00t

2017-11-22 17:49:33 +08:00

这题我都没看懂。红球怎么+1-1 ？

acros

2017-11-22 17:56:12 +08:00

这题目好迷啊。
看流程，只有抓到两个黑的时候，才出现黑色减少红色增加，其他情况下都是红色减少黑色恒定。
总体趋势不是在红黑平衡<->红少黑多之间变化？
结果不应该是算概率吗，恒定的?!

czheo

2017-11-22 17:56:38 +08:00

审题有误，最后剩下一个球，我还以为最后剩下一种颜色就停止了。。。

fffflyfish

2017-11-22 17:56:48 +08:00

@l00t 重新组织了下语言，在 append，sorry 哈

binux

2017-11-22 17:57:40 +08:00 via Android

@fffflyfish 那取出两个黑球，红球怎么+1 ？无中生有吗

fffflyfish

2017-11-22 17:58:57 +08:00

@acros 我当时也是用概率做的，然后一直往概率的方向想，如果能往递归的原理想想，比如#4，#22，就不至于答不出来了。。。

fffflyfish

2017-11-22 18:00:06 +08:00

@binux 算是吧，你就当从别的地方拿来一个红球，然后扔进去嘛，只要满足颜色相同就可以这么干

Andiry

2017-11-22 18:01:44 +08:00

红球用 0 代替，黑球用 1 代替，最后剩下的值就是所有球的易或，所以只取决于黑球数量是奇数还是偶数

l00t

2017-11-22 18:02:32 +08:00

看了补充描述，那么看 n 是不是奇数。是奇数的话剩下的就是黑的。是偶数的话，那早晚黑的会全部取出，剩下的是红的

nigelvon

2017-11-22 18:04:14 +08:00

22 楼没毛病

acros

2017-11-22 18:10:20 +08:00

根据 append 重新列了下，22 对了~

ZxBing0066

2017-11-22 18:14:05 +08:00

红球数量+1-1 是指放一个或拿出一个红球？题目看的我蒙蔽

introom

2017-11-22 18:49:20 +08:00 via Android

这种题，到底是证明个什么

Tink

2017-11-22 18:57:10 +08:00 via iPhone

22 楼厉害

BlackCat02

2017-11-22 19:57:09 +08:00

22 楼正解，比我的解法简单明了多了

yuang

2017-11-22 20:17:17 +08:00

22 楼牛逼。我居然还写了段代码才做出来。

xml123

2017-11-22 20:37:47 +08:00

22 楼说的很清楚了，不过其实还可以简化成一句话：
黑球数量的奇偶性不会改变，所有剩下的颜色是 n%2==0?R:B

kdplus

2017-11-22 20:41:57 +08:00

这... 题目条件要分析分析撒，这关键黑球只有-2 的选项啊，n 是奇数的时候，必剩下黑球撒

chengchuan1009

2017-11-22 21:53:26 +08:00

31 楼简单明了

sensui7

2017-11-23 00:21:08 +08:00

@chairuosen 仰望, 我只能这样

scnace

2017-11-23 01:27:55 +08:00 via Android

异或解法 666666

66beta

2017-11-23 08:48:15 +08:00

受教了，希望多来点这种分享帖

xiaojunjor

2017-11-23 09:26:33 +08:00

厉害厉害，学习了

void1208

2017-11-23 09:26:38 +08:00

《编程珠玑》第四章出现过这道题，正好刚看的。。

LeoNG

2017-11-23 10:04:48 +08:00

受教了。

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 则红球几率大。

justicelove

2017-11-23 14:05:07 +08:00

#22 楼牛逼，N 的奇偶性不会变。66666

xiaoyao9933

2017-11-23 15:28:59 +08:00

#31 楼比 #22 楼还屌。。这题就是考 XOR 的。发现了问题的本质啊。

lengyihan

2017-11-23 19:12:15 +08:00 via Android

@Thexz 头像是 pronhub 的色彩吧

Thexz

2017-11-23 21:25:39 +08:00 via iPhone

@lengyihan 老司机哟