算法创作|找出游戏的获胜者问题解决方法

简介: 算法创作|找出游戏的获胜者问题解决方法

问题描述

共有 n 名小伙伴一起做游戏。小伙伴们围成一圈,按 顺时针顺序 从 1 到 n 编号。确切地说,从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置,其中 1 <= i < n ,从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。

游戏遵循如下规则:

从第 1 名小伙伴所在位置 开始 。

沿着顺时针方向数 k 名小伙伴,计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数,一些小伙伴可能会被数过不止一次。

你数到的最后一名小伙伴需要离开圈子,并视作输掉游戏。

如果圈子中仍然有不止一名小伙伴,从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始,回到步骤 2 继续执行。

否则,圈子中最后一名小伙伴赢得游戏。

给你参与游戏的小伙伴总数 n ,和一个整数 k ,返回游戏的获胜者。

 

来源:力扣(LeetCode)

实例1:

输入:n = 5, k = 2

输出:3

实例2:

    输入:n = 6, k = 5

    输出:1


解决方案

由题目的意思,我们可以为小伙伴们编号,有多少位小伙伴,就有多少号,由n = 5,k = 2我们可以得出第一位输掉比赛的是2,然后又由第三位小伙伴开始淘汰掉4,游戏到这里还剩下三位小伙伴,分别是1 3 5,到第五位小伙伴时,又要回到开头,也就是将1淘汰,依次像这样进行,直到只剩下一位小伙伴时游戏结束,该伙伴则为获胜者。


为实现上述条件,我们往往采用的方法是取模,取模也就是我们常说的的余数,我们可以很快的发现余数(z)也被除数(x)之间的关系(0 <=z < x),在python中,这一关系可以实现一种循环,可以很好的帮我们解决问题,因此本题也可以运用取模这一方法。

代码清单

n = int(input())
k = int(input())
lis = [i for i in range(1,n+1)]
a = 0
while len(lis) != 1:
    a = (a + (k-1))%len(lis) # 取模,加a是为了每次淘汰一人时,都能从该位置继续向下,继续游戏

     lis.pop(a)
print(lis[0])

 


结语

每当我们做题时,都要先理清我们的思路,用什么方法能将该题解决出来,能否用代码表示出来。无论我们在做什么时,思路最为重要。此外,我们还可以思考有没有其它方法可以解决该问题,要知道每个题都不只一种方法可以解决,因此我们还可以多锻炼我们的思路,加强我们的逻辑能力,这样才能让我们越来越厉害。

目录
相关文章
|
1月前
|
人工智能 算法 Java
【搜索算法】数字游戏(C/C++)
【搜索算法】数字游戏(C/C++)
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
50 1
|
3月前
|
算法
互动游戏解决遇到问题之基于射线投射寻路算法的问题如何解决
互动游戏解决遇到问题之基于射线投射寻路算法的问题如何解决
|
3月前
|
算法 Python
【python】python基于 Q-learning 算法的迷宫游戏(源码+论文)【独一无二】
【python】python基于 Q-learning 算法的迷宫游戏(源码+论文)【独一无二】
|
5月前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
5月前
|
算法 JavaScript 前端开发
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
81 1
|
5月前
|
算法 Java
Java数据结构与算法:冲突解决方法
Java数据结构与算法:冲突解决方法
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
|
5月前
|
算法 机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
|
5月前
|
SQL 算法 数据可视化
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】