Microsxxxxxxx-面试总结

策略题

There are four kinds of cards, respectively, 1,2, 3,4 numbers. There are seven cards for each type of card. At this point, there are two players, and two players take one card in turn. When the sum of the cards is equal to 27, the next player wins. Which strategy can be used to ensure that the player wins?

假设两个玩家分别是A,B。此时来倒推。

A+B 剩余 先拿先赢或者输 做法
26 1  A+B=26,此时只能拿1,输
25 2  拿1剩1,剩1输
24 3  拿2剩1,剩1输
23 4  拿3剩1,剩1输
22 5  拿4剩1,剩1输
21 6  拿1剩5,剩5时先拿先赢(此时剩5拿4赢),拿1输;拿2剩4,剩4时先拿先赢(此时剩4拿3赢),拿2输;拿3剩3,剩3时先拿先赢(此时剩3拿2赢),拿3输;拿4剩2,剩2时先拿先赢(此时剩2拿1),拿4输
20  赢   拿1剩6,剩6输
19  赢   拿2剩6,剩6输
18  赢   拿3剩6,剩6输
17  10  赢   拿4剩6,剩6输
16  11  输   拿1剩10,剩10赢(此时剩10拿4赢),拿1输;拿2剩9,剩9时先拿先赢(此时剩9拿3赢),拿2输;拿3剩8,剩8时先拿先赢(此时剩8拿2赢),拿3输;拿4剩7,剩7时先拿先赢(此时剩7拿1),拿4输
15  12  赢   拿1剩11,剩11输
14  13  赢   拿2剩11,剩11输
13  14  赢   拿3剩11,剩11输
12  15  赢   拿4剩11,剩11输
11  16  输   拿1剩15,剩15赢(此时剩15拿4赢),拿1输;拿2剩14,剩14时先拿先赢(此时剩14拿3赢),拿2输;拿3剩13,剩3时先拿先赢(此时剩13拿2赢),拿3输;拿4剩12,剩12时先拿先赢(此时剩12拿1),拿4输
10  17  赢   拿1剩16,剩16输
18  赢   拿2剩16,剩16输
19  赢   拿3剩16,剩16输
20  赢   拿4剩16,剩16输
21  输   拿1剩20,剩20赢(此时剩20拿4赢),拿1输;拿2剩19,剩19时先拿先赢(此时剩19拿3赢),拿2输;拿3剩18,剩18时先拿先赢(此时剩18拿2赢),拿3输;拿4剩17,剩17时先拿先赢(此时剩17拿1),拿4输
22  赢   拿1剩21,剩21输
23  赢   拿2剩21,剩21输
24  赢   拿3剩21,剩21输
25  赢   拿4剩21,剩21输
26  输   拿1剩25,剩25赢(此时剩25拿4赢),拿1输;拿2剩24,剩24时先拿先赢(此时剩24拿3赢),拿2输;拿3剩23,剩23时先拿先赢(此时剩23拿2赢),拿3输;拿4剩22,剩22时先拿先赢(此时剩22拿1),拿4输

则可以看出,

当A+B=5n+1时,先拿者先输

当A+B=5n+2时,先拿者先赢,拿4

当A+B=5n+3时,先拿者先赢,拿3

当A+B=5n+4时,先拿者先赢,拿2

当A+B=5n时,先拿者先赢,拿1

结论:想要赢者,必须先拿1,当对手拿1、2、3、4时,先拿1者分别对应拿4、3、2、1必胜。

原文地址:https://www.cnblogs.com/lijuanhu321/p/8619499.html