用户注册和登录网站怎么做的,学做投资网站,wordpress用户组,百度广告开户我们来玩丢手绢
昨天我们打扑克#xff0c;今天我们丢手绢丢手绢我们都知道这个游戏#xff0c;他的由来由约瑟夫 #xff08;Josephus#xff09;提出来的
据说著名犹太历史学家Josephus有过以下的故事#xff1a;在罗马人占领乔塔帕特后#xff0c;39 个犹太人与Jose…我们来玩丢手绢
昨天我们打扑克今天我们丢手绢丢手绢我们都知道这个游戏他的由来由约瑟夫 Josephus提出来的
据说著名犹太历史学家Josephus有过以下的故事在罗马人占领乔塔帕特后39 个犹太人与Josephus及他的朋友躲到一个洞中
39个犹太人决定宁愿死也不要被敌人抓到于是决定了一个自杀方式41个人排成一个圆圈由第1个人开始报数每报数到第3人
该人就必须自杀然后再由下一个重新报数直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始
越过k-2个人因为第一个人已经被越过并杀掉第k个人。接着再越过k-1个人并杀掉第k个人。这个过程沿着圆圈一直进行
直到最终只剩下一个人留下这个人就可以继续活着。问题是给定了和一开始要站在什么地方才能避免被处决。
Josephus要他的朋友先假装遵从他将朋友与自己安排在第16个与第31个位置于是逃过了这场死亡游戏。问题来了我们就不杀呀杀了还是丢手绢吧让n个人围成一个环编号从1 ~n从1 开始数当数到第m个人时候他从圈中离开接着从m1 个人数继续m个在出局依次复制这个过程求最后一个出局的人是几号
方案一环形链表
题目明显提到了数字的圆圈自然我们可以构造一个这样类似的数据结构去模拟这种过程。在常用数据结构中n个阶段的环形链表很好的重现了这种模式 我们先构建n个节点的链表每次删除第m个元素当环形链表中元素只剩下一个时候得到解算法分析 链表头开始指定位置position链表尾指定位置before循环m次分别将position与before都前移m-1次得到指定位置删除psition位置节点让position指向position.next统计个数count n-1继续以上步骤 以上步骤中循环次数 n-1*m次因此时间复杂度应该是O(nm)当m特别大40000 时间复杂度会异常的大非常慢优化可以通过取余操作直接计算出m次循环在 链表中实际的步骤将 m % count -1得到实际步骤当m是大数时候优化效果明显如上分析有如下代码
/*** 约瑟夫环问题 将0,1,2,3,4.....n 这n个数字排列成一个圈圈从数字0 开始数m个数删掉他* 接着从m1 个开始数在来m个继续删除一次类推求出剩下的最后一个数据* author liaojiamin* Date:Created in 14:30 2021/7/7*/
public class JosephusForList {public static void main(String[] args) {System.out.println(delNodeForJosephus(40000,997));}/*** 环形链表方法* */public static Integer delNodeForJosephus(Integer n, Integer m){if(n 0|| m0){return null;}//构造环形队列ListNode head new ListNode(0);ListNode last null;ListNode position head;for (Integer i 1; i n; i) {last new ListNode(i);position.setNext(last);position position.getNext();}last.setNext(head);ListNode before position;position position.getNext();//当需要移动的位置小于当前数据个数直接移动指针Integer count n;while (m count){for (Integer i 0; i m-1; i) {before position;position position.getNext();}before.setNext(position.getNext());position position.getNext();count--;}//当m 大于当前需要移动位置个数取余计算最小移动值while (m count count 1){int move Math.abs(m%count - 1);for (Integer i 0; i move;i){before position;position position.getNext();}before.setNext(position.getNext());position position.getNext();count--;}position.setNext(null);return position.getValue();}}
以上算法时间复杂度O(nm) 空间复杂度O(n)
约瑟夫环问题 约瑟夫环问题最终还是一个数学问题数学能救命我们大概来推导一下 首先定义一个关于n 和 m的方法记为f(n, m)表示每次在n个数字0~n-1中每次删除第m个数字最后剩下的数字 第一个删除的数字用nm表示m-1% n , 当且仅当 m0 n1的时候我们记为k m-1% n 如下图 接着下一次遍历是从k1 开始的现有数字总共 n-2个k1排第一也就有如下图所示的顺序 我们记录第一个删除后的值是 d(n-1, m)与之前的 f(n, m)是同一个规则删除那么他们最终的结果肯定是一样的那么就有 d(n-1, m) f(n, m) 也就是我们将k1当成是当前的第0 位置k-1是当前最后的位置也就是 n-2那么我们依次推导出各个的位置k2是第一个位置 n-2之后有n-1在加上k个数 (n-2)-(k2)1n-k-3n-2 之后有k1个数(n-2)-(k1)1 n-k2同理 0 则是 n-k11 是 n-kk-1则是n-2用下图对应关系展示 如上图上部分是数据值下部分是对应的位置我们可以定义两个集合 A集合是上部分数据值B集合是下部分位置值A,B为非空集, 若存在对应法则f(), 使得对每个 x∈y 都有唯一确 y∈B与之对应, 则称对应法则f()为A到B的映射 如果我们找到了数据值与 位置值的映射关系函数是不是可以直接通过计算得到下一步中需要删除的数据 此处我们定义映射为p推导出p(x) (x-k-1)%n,映射的逆映射就是p(x) (xk1)%n 根据以上映射规则映射之前的写中最后剩下的数字 d(n-1, m) p[f(n-1)m] [f(n-1,m) k 1]%n将km-1%n 得到f(n,m) d(n-1,m) [f(n-1,m) k 1]%n 那么我们得到一个递推公式 n 1 f(n, m) 0n1 f(n, m) [f(n-1, m)m ]%n 有了如上公式我们很自然直接递归就能得到第n次的结果 如上分析有如下代码
/*** 约瑟夫环问题 将0,1,2,3,4.....n 这n个数字排列成一个圈圈从数字0 开始数m个数删掉他* 接着从m1 个开始数在来m个继续删除一次类推求出剩下的最后一个数据* author liaojiamin* Date:Created in 14:30 2021/7/7*/
public class JosephusForList {public static void main(String[] args) {System.out.println(fixJosephusForMath(40000, 997));}/*** 数学方案通过计算得出发f(n,m)* n0 f(n,m) 1* n1 f(n,m) [f(n-1,m)m]%n** */public static Integer fixJosephusForMath(Integer n, Integer m){if(n 0|| m0){return null;}if(n 1){return 0;}if(n 1){return (fixJosephusForMath(n-1, m)m)%n;}return null;}
}以上递归实现当n m值非常大时候几乎不可用情况通之前文章斐波那契数量原因一样
优化方案三
动态规划解法在以上推导基础上用一个循环解决
package com.ljm.resource.math.myList;/*** 约瑟夫环问题 将0,1,2,3,4.....n 这n个数字排列成一个圈圈从数字0 开始数m个数删掉他* 接着从m1 个开始数在来m个继续删除一次类推求出剩下的最后一个数据* author liaojiamin* Date:Created in 14:30 2021/7/7*/
public class JosephusForList {public static void main(String[] args) {System.out.println(fixJosephusForMath2(40000,997));}/*** 动态规划实现* 数学方案通过计算得出发f(n,m)* n0 f(n,m) 1* n1 f(n,m) [f(n-1,m)m]%n** */public static Integer fixJosephusForMath2(Integer n, Integer m){if(n 0|| m0){return null;}int last 0;for(int i2;in;i){last (lastm)%i;}return last;}}
可以看出以上实现思路分析非常复杂但是代码简单时间复杂度O(n)空间复杂度O(1)远优于第一第二解法
上一篇数据结构与算法–判断扑克牌是否顺子 下一篇数据结构与算法–这个需求很简单怎么实现我不管发散思维
