【159.271 计算思考】159.271 Computational Thinking
Assignment 2
This assignment will be a piece of cake. That is, you need to smarten up the computer player for
a game we shall call “Piece of Cake”.
Piece of Cake
The game works as follows: We have a cake that is cut into pieces which can differ in thickness.
Players take turns in choosing a piece of cake. But they need to be polite: After the first piece of
cake has been removed, only one of the two pieces adjacent to the gap can be taken. Once the cake
is gone, the player who ate the most wins.
A simple implementation for a 2-player version of the game (computer vs human, human goes
first) is provided on the course website (if you see gaps in the cake border, that’s a bug in the graphics
library). The cake has 32 pieces (an even number ensures some measure of fairness), with thickness
ranging from 5 to 9.
Tasks
Currently, the computer player is using a simple greedy heuristic, choosing the bigger of the two pieces
available (this is done in cake picker.py - your implementation should modify this class). A better
strategy is to maximize the total amount of cake you can get regardless of how your opponent plays.
That is, you assume that your opponent always picks the piece which minimizes the overall total you
can get (and maximizes theirs).
(a) Give an example to show that the simple greedy heuristic used by the template is not optimal,
i.e., that it does not maximize the total amount of cake the computer will get when taking the
minimum among all possible choices for the human player. [2 points]
Note: The number of pieces left is always odd when the computer choses. A minimal odd-sized
example showing the non-optimality of a greedy strategy has 5 pieces.
(b) Implement an algorithm which maximizes the computer player’s guaranteed overall total in each
step (as described above). This algorithm should run in polynomial time. [6 points]
Hint: Use dynamic programming techniques.
(c) Analyze the time complexity of your algorithm, as a function of the number of pieces. [1 point]
(d) Describe briefly how to modify your algorithm if the computer player were to start. [1 point]
推荐阅读
- 算法|如何看待2021年秋招算法岗灰飞烟灭（）
- 算法|深度学习在CV领域，已经触及到了天花板（）
- 预测喜欢（在简单推荐引擎的算法中）
- Shazam如何工作（音乐识别算法，指纹识别和处理）
- 带有AsciiDoc和Knitr的Ruby算法文档
- 使用Aho-Corasick算法征服字符串搜索
- 探索监督机器学习算法
- 数据结构|数据结构（三）——详解栈和队列及完整代码实现
- 无监督的人工神经网络算法和技术