网易数据分析实习试题2018-部分解题思路

1. 有2堆宝石，A和B一起玩游戏，假设俩人足够聪明，规则是每个人只能从一堆选走1个或2个或3个宝石，最后全部取玩的人获胜，假设2堆宝石的数目为12和13，请问A怎么可以必胜？

• 让A先取

• 让B先取

• 没有策略能够让A必胜

• 说法都不正确

  涉及知识点：动态规划算法，但本题中不需要写code也可直接得出答案，思路如下：

1 想象只剩下1个宝石，拿的人必胜；（必胜点W）
2 想象剩下2个宝石，拿的人一定会选择拿2个（必胜点W）
3 想象剩下3个宝石，拿的人一定会选择拿3个（必胜点W）
4 想象剩下4个宝石，拿的人无论拿几个，下一个人一定能选择拿完（必败点L）
5 想象剩下5个宝石，拿的人一定会选择拿1个（必胜点W）
6 想象剩下6个宝石，拿的人一定会选择拿2个（必胜点W）
...

因此一定要使得最后剩下为4的倍数 。A必胜策略：让A先选，只需要第一轮取走数目为13的那堆宝石中的1个，使得B无论怎样选，A在B选之后保持宝石堆剩下数目为4的倍数即可获胜。

2. 从数字集合{1,2,3,4,…,20}中选出4个数字的子集，如果不允许两个相连的数字出现在同一集合中，那么能够形成多少个这种子集？

思路：逆向思维，排列组合问题，编程解决
1 一共种子集
2 找出存在相连数字的子集（编程实现：检索）
3 相减即为不存在相连数字的子集

# R语言实现过程
total <- choose(20, 4)  # 总个数
df <- t(combn(20, 4))   # 排列组合可能性，每行代表20个选4个的一种情形

continue.test <- function(vec){  # 检测是否存在连续的元素
  any((vec + 1) %in% vec)
}

continue.exist <- sum(apply(df, 1, continue.test))  
# 计算连续子集的总数目

total - continue.exist
# 相减即为没有连续数字出现的数目2380

最后得出答案为2380

3. 将4个不一样的球随机放入5个杯子中，则杯子中球的最大个数为3的概率是?

思路：逆向思维，排列组合问题，可直接计算求解

1. 一共5⁴ = 625种
2. 杯子中球的最大个数为3，说明4个球一共只占据了2个杯子，数目分别为1个和3个。本题答案即为2只杯子的组合数乘4个不同球分为两堆（有序）的组合数。
3. = 10，说明选择杯子共10种情况，4个不同球分为1+3有=4种，由于2个杯子存在先后顺序，可得本题答案为10*4*2/625 = 80/625 = 16/125。

参考：

1. 牛客网网易数据分析实习试题2018
2. 博弈思路