python超简单解决约瑟夫环问题

前言 传说在公元1 世纪的犹太战争中,犹太历史学家弗拉维奥·约瑟夫斯和他的40 个同胞被罗马士兵包围.犹太士兵决定宁可自杀也不做俘虏,于是商量出了一个自杀方案.他们围成一个圈,从一个人开始,数到第三个人时将第三个人杀死,然后再数,直到杀光所有人.约瑟夫和另外一个人决定不参加这个疯狂的游戏,他们快速地计算出了两个位置,站在那里得以幸存.写一段程序将n 个人围成一圈,并且第m个人会被杀掉,计算一圈人中哪两个人最后会存活.使用循环链表解决该问题. 看到这个问题首先想到的是要用到循环链表,还有就是要计算

约瑟夫环问题 N个人围成一圈顺序编号,从1号开始按1.2.3......顺序报数,报p者退出圈外,其余的人再从1.2.3开始报数,报p的人再退出圈外,以此类推.   请按退出顺序输出每个退出人的原序号 算法思想 用数学归纳法递推. 无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达O(nm),若nm非常大,无法在短时间内计算出结果.我们注意到原问题仅仅是要求出最后的胜利者的序号,而不是要读者模拟整个过程.因此如果要追求效率,就要打破常规,实

问题说明这个问题是以弗拉维奥·约瑟夫斯命名的,它是1世纪的一名犹太历史学家.他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中.他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁.约瑟夫斯和另外一个人是最后两个留下的人.约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀.约瑟夫斯把他的存活归因于运气或天意,他不知道是哪一个机智的约瑟夫! 有N个编号为1~N的人围成一圈,现在每隔两个人(比如:1.4 之间隔了2.3)就将一个人淘汰出去,问最后剩下的是编号为几的人? 算法代

题目: 有二十九个女生(分别用1-29号来称呼)围成一圈玩报数游戏,规则是这样的:从1开始数数,当数到3的这个人就退出游戏,而她后面的人接着从1数...如此一直到最后剩下一个人,现在知道最初是从13号女生开始的游戏,问最后剩下的会是第几号女生? 要求: 1 用批处理解答 2 代码简洁高效 3 代码通用且不生成临时文件 加分原则: 以思路为重(如思路独特,请简要说明) 完全符合要求的加10分 已有两套解决方案,见3楼more和6楼ieutk版主的代码,但个人认为这两套方案均不完美(见本人的跟贴评述

约瑟夫问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题.在计算机编程的算法中,类似问题又称为约瑟夫环.又称"丢手绢问题".) 猴子一群,都带着号码的,站好了一圈,数到m的枪毙,剩下的接着数.如此往复,死剩下的一个就疯了 复制代码 代码如下: <?phpfunction killMonkeys($monkeys, $m){    $k = $m;    while (count($monkeys)){        $k = $k - 1;        $mon

来看看这个问题的详细描述: view sourceprint?一群猴子排成一圈,按 1,2,...,n 依次编号.然后从第 1 只开始数,数到第 m 只,把它踢出圈,从它后面再开始数, 再数到第 m 只,在把它踢出去...,如此不停的进行下去, 直到最后只剩下一只猴子为止,那只猴子就叫做大王.要求编程模拟此过程,输入 m.n, 输出最后那个大王的编号. 刚开始构思的时候想使用 PHP 数组来实现(当然最后还是使用的数组),然后模拟一个数组的内部指针,结果发现想模拟一个"数组指针"不是那

本文实例形式展示了C++实现循环链表中约瑟夫环的方法,分享给大家供大家参考之用.具体方法如下: 主要功能代码如下: #include <iostream> using namespace std; typedef struct student { int data; struct student* next; }node,*LinkList; //约瑟夫环 void printfList(LinkList head){ LinkList p=head; if (head!=NULL) { do

首先,约瑟夫环的数学优化方法为: 为了讨论方便,先把问题稍微改变一下,并不影响原意:问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数.求胜利者的编号.我们知道第一个人(编号一定是(m-1)%n) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m%n的人开始):    k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2 并且从k开始报0.现在我们把他们的编号做一下转换:k --> 0 k+1 -->

这个也算是老题目了,园子里边也曾针对此题有过激烈的讨论,那时候追求用oo来解决.如今既然又有人提了出来,我便抽了点时间写了写自己的想法: 复制代码 代码如下: <script type="text/javascript"> var a_game = function(pNum){ var players = []; for(var i=1;i<=pNum;i++){ players.push(i); } var flag=0; while(players.length

复制代码 代码如下: import java.io.BufferedInputStream;import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Josephus {    private static class Node{        int No;        Node next;        public Node(int No){            this