数博弈

【Puzzle】甜食爱好者

字数统计: 881字   |   阅读时长: 3分
, , ,

摘要: 一个博弈方面的逻辑题，参考《程序员面试逻辑题解析》

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

参考：程序员面试逻辑题解析

问题描述

有两块完全一样的长方形蛋糕，A 和 B 玩游戏，游戏规则是这样的:

  • A 先把一块蛋糕切成两份，大小随意
  • A 切完后，B 决定是否要先选蛋糕
    • 如果 B 先选，会选那份大的
    • 如果 A 先选，B 可以预料 A 会选那份大的
  • 随后 A 把另一块也切成两份
    • 如果之前 B 先选，则这次 A 先选
    • 如果之前是 A 先选的，则这次 B 先选
1
2
考察点:
- 逻辑

热身问题

假设每个人的目标是分得尽可能多的蛋糕，则对 A 来说最好的策略是什么。

正式问题

还是两个人游戏，一模一样的蛋糕变成了 3 块，同时规则也有更新

还是 A 负责切蛋糕，但是 B 有两次先选的机会。即 A 切第一块，第二块，第三块之后，均由 B 决定由谁先选蛋糕，只是 B 至少要给 A 一次先选的机会。

问题 1

新规则下，A 怎样切可以得到最多，最多能得多少。

问题 2

假设蛋糕变成 7 块，B 有 6 次先选机会，谁有优势？有多大优势？

问题 3

假设总是让 A 切蛋糕，有没有办法保证两个人能得到一样多的蛋糕

思路参考

热身问题

用 f 和 1 - f 来表示第一块蛋糕被切分后两部分的大小, 其中 f >= 1/2。假设下面两种情况:
第一种, B先选, 拿走了 f 那块;
第二种, N后选, 拿走了 1 - f 那块。
依次分析这两种情况下的结果。

分析结果: 第一刀切 3/4，第二刀切 1/2，不论 A 选择先拿还是后拿，最终 A 得 5/4, B 的 3/4

问题1:

第一刀切为 f 和 1 - f，且 f >= 1/2

  • 若第一刀 A 先取 f，B 取 1 - f，则后两刀平分，最终 A 得 f + 1, B 得 2 - f
  • 若第一刀 B 先取 f，A 取 1 - f，则后两刀变为热身问题(A 得 5/4，B 得 3/4)，最终 A 得 9/4 - f, B 得 f + 3/4

取 f + 1 = 9/4 - f 得第一刀切 f = 5/8，不论 A 是否选择先拿，最终都是 A 得 13/8，B 得 11/8

问题2:

记 n 块蛋糕，A 又一次先选机会，最终 A 可以得到的蛋糕数量为 $g(n)$

第一刀切为 f 和 1 - f，且 f >= 1/2

取两种情况最终所得相等，求得 f

代回 $g(n)$:

初始值：$g(2) = \frac{5}{4}$。

代码实现一下:

1
2
3
4
5
6
7
8
def g(n):
    if n == 2:
        return  5 / 4
    return (n + 1) / 4 + g(n - 1) / 2

def solve(n):
    float_ans = g(n)
    return float.as_integer_ratio(float_ans)

将答案 n = 7 代入，$solve(7) = (449, 128)$。

问题3:

每次都让 B 先选。

Share