约瑟夫问题（循环链表法和公式法）python版 |
您所在的位置：网站首页 › 约瑟夫环公式解析 › 约瑟夫问题（循环链表法和公式法）python版 |
|
约瑟夫问题
N个人站在一个等待被处决的圈子里。第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个人就是最后的胜利者。 问题描述输入：n，m。其中n为总人数，依次编号为0，1…n，m为被处决的报数数值。 输出：最后活下来人的编号。 解决方案 1.循环单链表法用循环单链表去模拟这个过程。n个人看做n个链表节点，节点1的value为1，节点1的next指向节点2，节点2的value为2，节点2的next指向节点3，…，节点n的value为n，节点n的next指向节点1，构成一个循环单链表。然后从节点1开始报数，如果报数到m就被删除，最后剩下的那个节点的value就是活下来人的编号。python代码如下: class Node: def __init__(self, value): self.value = value self.next = None def create_linkList(n): head = Node(1) pre = head for i in range(2, n+1): newNode = Node(i) pre.next= newNode pre = newNode pre.next = head return head n = 8 # 总的个数 m = 3 # 数的数目 if m == 1: # 如果被处决的报数为1，直接输出最后一个值 print(n) else: head = create_linkList(n) pre = None cur = head while cur.next != cur: # 终止条件是节点的下一个节点指向本身 for i in range(m-1): pre = cur cur = cur.next pre.next = cur.next cur.next = None cur = pre.next print(cur.value) 2.公式法递推公式： f ( n , m ) = ( f ( n − 1 , m ) + m ) m o d n f(n,m) =(f(n-1,m)+m)\ mod\ n f(n,m)=(f(n−1,m)+m) mod n f ( 1 , m ) = 0 f(1,m) = 0 f(1,m)=0 代码如下： n = 8 # 总的个数 m = 3 # 数的数目 if m == 1: # 如果被处决的报数为1，直接输出最后一个值 print(n) else: i = 0 a = list(range(n)) while len(a) > 1: i =(i+2)%len(a) del a[i] print(a[0] + 1)参考： 约瑟夫问题-维基百科 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |