算法100游戏

大家好，算法100游戏相信很多的网友都不是很明白，包括也是一样，不过没有关系，接下来就来为大家分享关于算法100游戏和的一些知识点，大家可以关注收藏，免得下次来找不到哦，下面我们开始吧！

其中有一个带有15张卡的卡池，分别为1到15张。

两个人轮流从卡池中摘下卡。

将选择的点数添加到卡中，直到点数100。

首先以100的点使获胜者。

条件补充：每张卡最多一次一次（无返回卡池）

假设：左边的人首先选择，他如何选择确保自己获胜？还是不能赢？

先决条件：没有人犯错，很聪明

算法理解

问题的目标的总和为100，并且要扩展到更一般的情况，我们可以将目标设置为t和t是一个正整数。

卡池中的一些卡片为15，将其扩展到更普遍的情况。我们将最大卡池设置为k，这意味着总共有1个k卡可供选择。

这是一个“递归”问题。

对于递归问题，我们可以从中间的广义片段规则开始，找到递归逻辑，然后找到递归退出逻辑来解决问题。

1。我们将卡池划分为：二手（已使用的集合），未使用（将要使用的集合）

所使用的集合表示：播放器选择的卡，卡的总和代表当前总和。

设置要使用的代表：尚未选择的卡。

2。当玩家从未使用的卡中选择一张卡时，如果总和（使用） +at，则表示在当前状态下，第一个卡选择者将获胜。

3。当玩家从未使用的卡中选择一张卡时，如果sum（使用） + a t，则意味着在当前状态下，尚不知道该卡候选人是否首次获胜。

递归如下：

如果在使用的{a}的状态下选择了第一个卡片播放器，并且未使用- {a}，则当前状态肯定是第二个card播放器。

4。在当前状态下，如果所有未使用的人都已穿越，则在没有第一张卡选择器获胜的情况下，这意味着第二张卡选择器会获胜。

伪代码如下：

静态布尔FIRSTWIN（Integer T，使用SetInteger，setInteger未使用）{//计算当前使用的卡的总和Integer currentsum=used.stream.stream（）。collector.collector（collectors.summmingInt（x -x））; for（Integer Unusedcard :未使用）{//如果使用的数字和未使用的数字的总和=target的总和，请首先选择要赢的卡，如果（二手+ unusedcard=t）{return true; } //添加当前卡以使用并从未使用中扣除，并进行递归调用setInteger newused=new hashset（使用）; newused.Add（unusedcard）; setInteger newunused=new Hashset（未使用）; newunused.remove（unusedcard）； //如果下层是后选择器的获胜者，则意味着当前的选择器会赢（！firstWin（t，t，newused，newunused））{返回true; }} //尝试了所有未使用的卡后，如果没有返回它们，则意味着后者的Picker Wins wins返回false;}代码仍然具有优化空间，以及第一个Picker Wins是否被缓存的结果。 “状态”是当前使用的集合。

这可以进一步优化时间复杂性。

如果您替换一个特定数字，则目标t为100，而卡池为15，

结果是：那些首先选择卡的人将获胜。