保龄球计分
这周的codingdojo玩了一道很有收获的题,终于搞明白了保龄球的计分方法。原题可以在reddit上的daily programmer上找到,这里我分享一下我的解题思路。
机制
保龄球的一局可以分成两个阶段,从第一轮到第九轮是一个阶段,第十轮是第二个阶段。
一到九
一到九的这九轮中,每一轮最多有两次掷球机会。如果一下全中的话,直接进入下一轮。
一击全中
如果一次就打中十个瓶的话,就得了一个Strike, 用X做标记。之所以用X标记,是为了表示它的最终得分还暂时未知。这是因为一击全中是有奖励的,除了先得十分之外,接下来的两次掷球的得分,也会加到这个X上。
两击全中
如果用两次机会打完,就得了一个Spare, 用第一个球的得分加”/“来标记。比如说第一个球得6分,第二球4分,那么就是6/。同样地道理,/表示暂时未知,两击全中也有奖励,但只会加入接下来一次掷球的得分。
没有全中
如果两次机会用完,都还没有全中,那么这一轮的得分就直接知道了,第一球加第二球的得分。比如先得了6分,又得了2分,那么就记为62, 6+2得8分。如果的零分的话,用一横杠表示。
第十轮
第十轮比较特殊。这一轮至少有两次机会,最多可以有三次。如果在前两次之内能全中的话,那么就可以再掷第三球,否则的话,两次就完事。
除此之外,第十轮的每个球都单独计分,没有奖励机制。
举例
讲完了这些规则之后,大家可以猜一猜,保龄球一局的最高得分是多少?怎样才能的最高分呢,那就是每次都一击全中,由下表可见,最高分能达到300分。
轮数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
结果 | X | X | X | X | X | X | X | X | X | XXX |
裸分 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 10 10 |
奖励 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 0 0 0 |
总分 | 30 | 30 | 30 | 30 | 30 | 30 | 30 | 30 | 30 | 10 10 10 |
下面这个例子的总得分应该140分。
轮数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
结果 | 62 | 71 | X | 9- | 8/ | X | X | 35 | 72 | 5/8 |
裸分 | 62 | 71 | 10 | 90 | 82 | 10 | 10 | 35 | 72 | 5 5 8 |
奖励 | 0 | 0 | 9 | 0 | 10 | 13 | 8 | 0 | 0 | 0 0 0 |
总分 | 8 | 8 | 19 | 9 | 20 | 23 | 18 | 8 | 9 | 5 5 8 |
算法
一旦理解了计分机制,算法就很直观了。建模的时候,主要有两个重点:
- 计分应该分成两个阶段,前九轮和第十轮
- 计分单位应该以球为单位,而不是以轮为单位
Scala很简洁很直观地实现了这个计分算法
计算前第九轮成绩的时候,一定不要忘记把第十轮的前两球考虑进去,以便奖励第九轮可能出现的全打
1 | object Solution { |
如果你需要训练算法,或者准备面试,推荐你破解这些题目:https://github.com/huiwang/cracking-the-coding-interview