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

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

问题描述

共有 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])

 


结语

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

目录
相关文章
|
25天前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
29天前
|
算法 JavaScript 前端开发
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
22 1
|
9天前
|
算法 Java
Java数据结构与算法:冲突解决方法
Java数据结构与算法:冲突解决方法
|
22天前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
|
22天前
|
算法 机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
|
25天前
|
SQL 算法 数据可视化
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】
|
2月前
|
算法 定位技术 C语言
推箱子游戏(算法设计)
推箱子游戏(算法设计)
|
2月前
|
存储 算法 PHP
开发一款扑克游戏,请给出一套洗牌算法,公平的洗牌并将洗好的牌存储在一个整形数组里?
开发一款扑克游戏,请给出一套洗牌算法,公平的洗牌并将洗好的牌存储在一个整形数组里?
21 1
开发一款扑克游戏,请给出一套洗牌算法,公平的洗牌并将洗好的牌存储在一个整形数组里?
|
2月前
|
算法 JavaScript 前端开发
游戏物理系统 - 如何在JavaScript中实现基本的碰撞检测算法?
在JavaScript中实现2D矩形碰撞检测,常用AABB方法,适合简单游戏。创建Rectangle类,包含位置和尺寸属性,并定义`collidesWith`方法检查两矩形是否相交。通过比较边界位置判断碰撞,当四条边界条件均满足时,认定发生碰撞。基础算法适用于初级需求,复杂场景可采用更高级的碰撞检测库。
30 1
|
2月前
|
机器学习/深度学习 算法 测试技术
【动态规划】【C++算法】1563 石子游戏 V
【动态规划】【C++算法】1563 石子游戏 V