约瑟夫算法

‘壹’ 约瑟夫环问题的算法设计是什么样子的

来自网络
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head
解决问题的核心步骤：（程序的基本算法）
1.建立一个具有n个链结点，无头结点的循环链表；
2.确定第1个报数人的位置；
3.不断地从链表中删除链结点，直到链表为空。
void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数
{
/* p为当前结点 r为辅助结点，指向p的前驱结点 list为头节点*/
LinkList p,r,list; /*建立循环链表*/
for(int i=0；i<n；i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i;
if(list==NULL)
list=p;
else
r->link=p;
r=p;
}
p->link=list; /*使链表循环起来*/
p=list;/*使p指向头节点*/
/*把当前指针移动到第一个报数的人*/
for(i=0;i<k;i++)
{
r=p；
p=p->link;
}
/*循环地删除队列结点*/
while(p->link!=p)
{
for(i=0;i<m-1;i++)
{
r=p;
p=p->link;
}
r->link=p->link;
printf("被删除的元素：%4d ",p->data);
free(p);
p=r->link;
}
printf("\n最后被删除的元素是：%4d",P->data);
}

‘贰’ 怎样用vb实现约瑟夫环算法

用面向过程的编程方式（C），对某个给定的n=8与m=3，给出被淘汰出列的旅客编号，以及最终的幸存者。
用面向对象的编程风格（C++），重新处理该约瑟夫问题。
谈谈这两种编程风格的优点。
二、用C语言解约瑟夫问题
1、单链表的创建与输出
#include<stdio.h>
#include<malloc.h>
#define NULL 0
struct node{ /*定义结构体*/
int data;
struct node *next;
};
typedef struct node NODE;/*将该结构体设置成自定义类型*/
NODE *head;/*定义一个指向该结构体的头指针*/
NODE *create(int n)/*创建具有n个结点的单链表*/
{
NODE *p;
int i=1;
head=(NODE *)malloc(sizeof(NODE));
head->next=NULL;
while(i<=n)
{
p=(NODE *)malloc(sizeof(NODE));
p->data=n+1-i;
p->next=head->next;
head->next=p;
i++;
}
return(head);
}
void output(NODE *point)/*输出该链表数据域内的值*/
{
NODE *p;
p=point->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
如果我们写一段main()函数
void main()
{
head=create(8);
output(head);
}
便可以完成创建和输出单链表的工作。
如果将上述创建单链表与输出单链表的工作保存为头文件link1.h,那么在今后需要创建输出类似的单链表时，只需写以下主函数即可。
#inlucde “link1.h”
void main()
{
head=create(8);
output(head);
}
2、循环单向链表的创建与输出
明白了带头指针的单向链表的创建与输出，只需作简单修改便可处理循环单向链表的相关问题。这里我们建立一个新的头文件link2.h，它包含以下几段代码。
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
struct node *next;
};
typedef struct node NODE;
NODE *head;
NODE *create(int n)
{
NODE *p;
int i=1;
p=head=(NODE *)malloc(sizeof(NODE));
head->next=head;/*造循环链表时头指针的指针域设置*/
while(i<=n)
{
p->data=n+1-i;
p->next=head->next;
head->next=p;
i++;
p=(NODE *)malloc(sizeof(NODE));
}
return(head);
}
void output(NODE *point,int n) /*n表示欲输出多少个结点，由于该链表是循环的，可输出无穷项*/
{
NODE *p;
int i=1;
p=point->next;
while(i<=n)
{
printf("%d ",p->data);
p=p->next;
i++;
}
printf("\n");
}
3、在循环链表中删除结点并输出被删结点的相关信息
在头文件link2.h中增添新函数del(int n,int m),这里的形参n代表起始结点，m代表报数值。
void del(int n,int m)
{
int i;
NODE *p,*q;
p=head;
/*将指针移到起始结点，即第n个结点*/
i=0;
while(i<n)
{
p=p->next;
i++;
}
/*删除满足报数值的结点*/
while(p->next!=p)
{
i=1;
while(i<m)/*找到符合报数值结点的前一个结点,即第m-1个结点*/
{
p=p->next;
i++;
}
/*先输出，后删除*/
q=p->next;
printf("%d ",q->data);
p->next=q->next;
free(q);
}
printf("\nonly one %d",p->data);/*输出仅剩的结点*/
}
4、解决约瑟夫问题的主函数
#include <link2.h>
void main()
{
/*number结点个数,item输出结点的个数,location报数的起始位置,callnum报数值*/
int number,item,location,callnum;
printf("\ninput nose number=");
scanf("%d",&number);
printf("\noutput item=");
scanf("%d",&item);
head=create(number);
output(head,item);
printf("\ninput location=");
scanf("%d",&location);
printf("\ninput callnum=");
scanf("%d",&callnum);
del(location,callnum);
}
三、以类作为结点来处理约瑟夫问题（准C++编程风格）
1、以类作结点的链表建立
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head=NULL,*p,*q;
for(int i=1;i<9;i++)
{
p=new Node;
p->SetData(i);
if(head==NULL)
head=p;
else
q->SetNext(p);
q=p;
}
q=head;
do
{
cout<<"该游客编号为:"<<q->GetData()<<endl;
q=q->GetNext();
}while(q!=NULL);
q=head;
do
{
q=q->GetNext();
delete head;
head=q;
}while(q!=NULL);
}
2、以类作结点的循环链表的建立
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=8;i++)
{
p->SetData(i);
p->SetNext(head);
q->SetNext(p);
q=p;
p=new Node;
}
q=head;
i=1;
do
{
cout<<"该游客编号为:"<<q->GetData()<<endl;
q=q->GetNext();
i++;
}while(i<=10);
}
3、解决约瑟夫问题
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=8;i++)
{
p->SetData(i);
p->SetNext(head);
q->SetNext(p);
q=p;
p=new Node;
}//
p=head;
i=1;
while(i<=8)
{
cout<<p->GetData()<<" "<<endl;
p=p->GetNext();
i++;
}//输出
cout<<endl;
p=head;
while(p->GetNext()!=p)
{
i=1;
while(i<2)
{
p=p->GetNext();//将欲删除点的前一个结点
i++;
}
q=p->GetNext();
cout<<q->GetData()<<endl;//删除循环链表上的结点
p->SetNext(q->GetNext());//将q指针域所指结点的地址赋给p的指针域
p=p->GetNext();
delete q;
}//做循环数数出局游戏
cout<<"\nLast One "<<p->GetData()<<endl;
}
四、用标准的面向对象编程风格处理约瑟夫问题（C++编程风格）
//#include "stdafx.h"
#include "iostream.h"
//#define NULL 0
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
Node *Create(int n);//创建含n个结点的循环链表
void Output(Node *p,int n);//输出循环链表头结点为p的后n个结点的信息
Node *Move(Node *p,int n);//将头结点指针前移到n
//从头结点为p的循环链开始，所用的计数为n进行约瑟夫实验
void Josephus(Node *p,int n);
};
Node *Node::Create(int n)
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=n;i++)
{
p->data=i;
p->next=head;
q->next=p;
q=p;
p=new Node;
}
return head;
};
void Node::Output(Node *p,int n)
{
int i=1;
while(i<=n)
{
cout<<p->data<<" ";
p=p->next;
i++;
}
};
Node *Node::Move(Node *p,int n)
{
if(n>1)
{
int i=1;
while(i<n)
{
p=p->next;
i++;
}
}
return p;
};
void Node::Josephus(Node *p,int n)
{
Node *q;
while(p->next!=p)
{
p=Move(p,n-1);
q=p->next;
cout<<q->data<<" ";
p->next=q->next;
p=p->next;
delete q;
}
cout<<"\nLast One "<<p->data<<endl;
};
void main()
{ Node A,*head;
head=A.Create(8);
cout<<"\nCirclist is ";
A.Output(head,10);
head=A.Move(head,1);
cout<<"\nJosephus result is "<<endl;
A.Josephus(head,3);
}
五、对两种编程风格的评述
在进行面向过程的程序设计时，一般首先考虑程序所要实现的功能，然后设计为实现这些功能所必须采取的步骤，这些步骤就是过程。如果一个过程比较复杂而不能直接使用已有的抽象进行实现，则对这个过程进行分解，使分解之后的每一步（更低级的过程）能够直接对应着一条语句。通过将分解之后的一系列过程封装在一个函数抽象中，程序员在特定的时刻只关心有限的细节，这个新的函数抽象比其较低级的抽象更接近问题求解的过程，因而，能够很好地映射问题求解中的过程。如果这个过程出现在许多问题求解中，那么，这个函数抽象就可能被重复利用。
函数是面向过程程序设计的基础，按照结构化程序设计的思想，又可将完成某一复杂工作的函数放在一个头文件，便于我们多次复用。
面向过程的程序设计方法与面向对象的程序设计方法的根本区别在于对待数据和函数的关系上。
在面向过程的程序设计中，数据只被看作是一种静态的结构，它只有等待调用函数来对它进行处理。
在面向对象的程序设计中，将数据和对该数据进行合法操作的函数封装在一起作为一个类的定义。另外，封装还提供了一种对数据访问严格控制的机制。因此，数据将被隐藏在封装体中，该封装体通过操作接口与外界交换信息。
面向对象的思想需要在实践中不断摸索和体会，在以后的程序设计中，可主动运用这种思想去实践。

‘叁’ 关于约瑟夫问题，求一段C语言算法

学会网络嘛骚年
网络知道上面就有人提供啊
http://..com/link?url=_0yG2pbWSKpFL5nvgJNWLOUnuW-b8fkPn2rc-roZlK
我测试过，devc上面可以运行

‘肆’ 数学上的约瑟夫问题怎么解

在M比较小的时候 ，可以用笔算的方法求解，
M=2
即N个人围成一圈，1，2，1，2的报数，报到2就去死，直到只剩下一个人为止。
当N=2^k的时候，第一个报数的人就是最后一个死的，
对于任意的自然数N 都可以表示为N=2^k+t，其中t<n/2
于是当有t个人去死的时候，就只剩下2^k个人 ，这2^k个人中第一个报数的就是最后去死的。这2^k个人中第一个报数的人就是2t+1
于是就求出了当M=2时约瑟夫问题的解：
求出不大于N的最大的2的整数次幂，记为2^k，最后一个去死的人是2(N-2^k)+1
M=3
即N个人围成一圈，1，2，3，1，2，3的报数，报到3就去死，直到只剩下一个人为止。
此时要比M=2时要复杂的多
我们以N=2009为例计算
N=2009，M=3时最后被杀死的人记为F（2009,3），或者可以简单的记为F（2009）
假设现在还剩下n个人，则下一轮将杀死[n/3]个人，[]表示取整，还剩下n-[n/3]个人
设这n个人为a1,a2,...,a(n-1）,an
从a1开始报数，一圈之后，剩下的人为a1,a2,a4,a5,...a(n-n mod 3-1）,a(n-n mod 3+1）,..,an
于是可得：
1、这一轮中最后一个死的是a(n-n mod 3），下一轮第一个报数的是a(n-n mod 3+1）
2、若3|n，则最后死的人为新一轮的第F(n-[n/3]）个人
若n mod 3≠0 且f(n-[n/3])<=n mod 3则最后死的人为新一轮的第n-[n/3]+F(n-[n/3])-（n mod 3）人
若n mod 3≠0 且f(n-[n/3])>n mod 3则最后死的人为新一轮的第F(n-[n/3])-（n mod 3）人
3、新一轮第k个人对应原来的第 3*[(k-1）/2]+(k-1）mod 2+1个人
综合1，2，3可得：
F（1）=1,F（2）=2,F（3）=2,F（4）=1,F（5）=4，F（6）=1，
当f(n-[n/3])<=n mod 3时 k=n-[n/3]+F(n-[n/3])-（n mod 3），F(n)=3*[(k-1）/2]+(k-1）mod 2+1
当f(n-[n/3])>n mod 3时 k=F(n-[n/3])-（n mod 3） ，F(n)=3*[(k-1）/2]+(k-1）mod 2+1
这种算法需要计算 [log（3/2）2009]次 这个数不大于22，可以用笔算了
于是：
第一圈，将杀死669个人，这一圈最后一个被杀死的人是2007，还剩下1340个人，
第二圈，杀死446人，还剩下894人
第三圈，杀死298人，还剩下596人
第四圈，杀死198人，还剩下398人
第五圈，杀死132人，还剩下266人
第六圈，杀死88人，还剩下178人
第七圈，杀死59人，还剩下119人
第八圈，杀死39人，还剩下80人
第九圈，杀死26人，还剩下54人
第十圈，杀死18人，还剩36人
十一圈，杀死12人，还剩24人
十二圈，杀死8人，还剩16人
十三圈，杀死5人，还剩11人
十四圈，杀死3人，还剩8人
十五圈，杀死2人，还剩6人
F（1）=1,F（2）=2,F（3）=2,F（4）=1,F（5）=4，F（6）=1，
然后逆推回去
F（8）=7 F（11）=7 F（16）=8 f（24）=11 f（36）=16 f（54）=23 f（80）=31 f（119）=43 f（178）=62 f（266）=89 f（398）=130
F（596）=191 F（894）=286 F（1340）=425 F（2009）=634
-----来自网络

‘伍’ 什么是约瑟夫法则

约瑟夫算法：n个人围成一圈，每人有一个各不相同的编号，选择一

个人作为起点，然后顺时针从1到k数数，每数到k的人退出圈子，圈

子缩小，然后从下一个人继续从1到k数数，重复上面过程。求最后推

出圈子的那个人原来的编号。

约瑟夫算法可以用循环链表和数组来解(这两个我会)，下面2个程序

都是用来解决该算法的，其中第（2）直接给出答案，每个程序都有

证明和讲解，

程序1(递归法):
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
int n;
int m;
int i = 0;
int p;

scanf("%d%d", &n, &m);

while (++i <= n )
{
p = i * m;
while (p>n)
{
p = p - n + (p-n-1) / (m-1);
}

printf("%d\n", p);
}

return 0;
}

程序2(递推法):
#include <stdio.h>

int main(void)
{
int i;
int s = 0;
int n;
int m;

scanf("%d%d", &n, &m);

for (i = 2; i <= n; i++)
{
s = (s + m) % i;
}

printf("最后的获胜者是: %d\n", s + 1);

return 0;
}

程序1证明：
假设数到第p个数时遇到的数,和数到第x个数到遇到的数一样,且p -

n < x < p,而且x % m != 0, 否则会被跳过和第个p数遇到的数肯定

不一样,那么说明数了x个数之后再数一圈就数到了第p个数,而数一圈

数过的数应该是n减去要跳过的数,因为已经数过了x个数,所以要跳过

[x / m]个数( []表示取整数部分 ),所以x + n - [x / m] = p
问题转化为: p - n = x - [x / m]...(1),且 x % m != 0, p - n <

x < p, 求解x
因为x % m != 0 => x / m - 1 < [x / m] < x / m
=> x - x / m + 1 > x - [x / m] > x - x / m
=> [x - x / m + 1] >= x - [x / m] > [x - x / m]
=> [x - x / m] + 1 >= x - [x / m] > [x - x / m]
=> [x - x / m] + 1 >= x - [x / m] >= [x - x /

m] + 1
=> [x - x / m] + 1 = x - [x / m]
( 代入(1)式 )=> p - n - 1 = [x - x / m] = [x * ( m - 1 ) /

m] ... (2)
因为x % m !=0 且 ( m - 1 ) % m != 0 => ( x * ( m - 1 ) ) %

m != 0
由(2)式 => 0 < x * ( m - 1 ) - m * ( p - n - 1 ) <= m - 1
由左边: => m * ( p - n - 1 ) < x * ( m - 1 )
=> m * ( p - n - 1 ) / ( m - 1 ) < x
=> [m * ( p - n - 1 ) / ( m - 1 )] < x
=> [m * ( p - n - 1 ) / ( m - 1 )] + 1 <= x ...(3)
由右边: => x * ( m - 1 ) - ( m - 1 ) <= m * ( p - n - 1 )
=> ( x - 1 ) * ( m - 1 ) <= m * ( p - n - 1 )
=> x - 1 <= m * ( p - n - 1 ) / ( m - 1 )
=> x - 1 <= [m * ( p - n - 1 ) / ( m - 1 )]
=> x <= m * ( p - n - 1 ) / ( m - 1 ) + 1 ...(4)
由(3),(4) => x = [m * ( p - n - 1 ) / ( m - 1 )] + 1
= [ p - n - 1 + ( p - n - 1 ) / ( m - 1 )] +

1
= p - n - 1 + [( p - n - 1 ) / ( m - 1 )] + 1
= p - n + [( p - n - 1 ) / ( m - 1 )]
由于计算机算整数除法直接就取整了,所以递归时就写成
p = p - n + ( p - n - 1 ) / ( m - 1 )

程序2证明：
Josephus(约瑟夫)问题的数学方法(转)约瑟夫 （转）

无论是用链表实现还是用数组实现都有一个共同点：要模拟整个

游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n

，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间

内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，

而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，

实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出

，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的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 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这

个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x

变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相

信大家都可以推出来：x‘=(x+k)%n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就

行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是

一个倒推问题！好了，思路出来了，下面写递推公式：

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然

是f[n]

递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)

‘陆’ Java约瑟夫经典循环算法

下面是我用c#写的，其实原理都一样，楼主自己研究下吧

Console.WriteLine("请输入参与游戏的人数：");
int numPerson = int.Parse(Console.ReadLine());

Console.WriteLine("请输入游戏退出的规则数：");
int ruleNum = int.Parse(Console.ReadLine());

bool[] person = new bool[numPerson]; //定义每个人是否退出开关，默认为否
int callNum = 0; //报数
int total = 0; //记录已经退出的人数
int index = -1; //报数的循环游标

while (true) {

index++; //从第一个人开始
index %= numPerson; //确保数组不越界，当游标指向最后一个数组元素以后，从头开始

if (!person[index]) { //第index个人没有退出时，则进行报数

callNum++;
}
if (callNum == ruleNum) { //当第index个人报数的数字与规则数相同时，则开关打开，退出报数

person[index] = true;
total++; //退出的总人数更新
callNum = 0; //为下一个人报数更新数据
Console.WriteLine("玩家{0}退出",index+1);
}
if ((numPerson - total) == 1) { //当游戏玩家只剩下一个的时候结束游戏

for (int i = 0; i < person.Length; i++) {

if (person[i] == false) { // 判断退出开关依然是否的玩家

Console.WriteLine("最后剩下的玩家是第：{0}位",i + 1); //输出实际的玩家号
break;
}
}
break;
}
}

‘柒’ 约瑟夫环的算法例子

递归法： #include<stdio.h>#include<stdlib.h>struct_Node{intdata;struct_Node*next;};typedefstruct_Nodenode_t;typedefstruct_Linklist{node_t*phead;node_t*ptail;intlen;}Linklist;staticnode_t*GetNode(inti)//新建并初始化节点{node_t*pNode;pNode=(node_t*)malloc(sizeof(node_t));if(!pNode){printf(Error,thememoryisnotenough! );exit(-1);}pNode->data=i;pNode->next=NULL;returnpNode;}voidinit_list(Linklist*plist)//用第一个节点初始化循环单链表{node_t*p;p=GetNode(1);//printf(TheNewNodeis:%d ,p->data);//****TEST****plist->phead=p;plist->ptail=p;p->next=plist->phead;plist->len=1;}staticvoidCreate_List(Linklist*plist,intn)//把其余数据添加到循环单链表中{inti=0;node_t*pNew;for(i=2;i<=n;i++){pNew=GetNode(i);/********TEST********printf(TheNewNodeis:%d ,pNew->data);********TEST********/plist->ptail->next=pNew;plist->ptail=pNew;pNew->next=plist->phead;plist->len++;}printf(Completesthee-! );}voidPrint_List(Linklist*plist)//输出链表内容{node_t*pCur=plist->phead;do{printf(The%dperson. ,pCur->data);pCur=pCur->next;}while(pCur!=plist->phead);printf(ThelengthoftheList:%d ,plist->len);}约瑟夫回环函数实现voidjoseph(Linklist*plist,intm)//约瑟夫回环函数实现{node_t*pPre=plist->ptail;node_t*pCur=plist->phead;inti;while(plist->len!=1){i=0;while(i<m-1){pPre=pPre->next;i++;}pCur=pPre->next;pPre->next=pCur->next;free(pCur);plist->len--;}printf(Thelastoneis:%d ,pPre->data);}intmain(){intn=0;printf(:);scanf(%d,&n);intm=0;printf(PleaseinputtheStoppoint:);scanf(%d,&m);LinklistpList;init_list(&pList);Create_List(&pList,n);Print_List(&pList);joseph(&pList,m);return0;}

非递归法： #include<stdio.h>#defineM200intmaininttemp=0;intb=1,k=0;for(inti=1;i<=M;i++)temp=b+3*k;if(i==temp)//规则2：若上一组数字为最后保留号与人数相等，则下一数从2开始记。b=2;k=0;continue;elseif(i-temp==1）//规则1：若上一组数字为最后保留号比人数少一，则下一数从1开始记。{b=1;k=0;continue;}k++;printf(%d%d,M,temp);return0;【php模拟】php有非常完善的数据结构模拟方案,可以非常简洁的解决这样的问题.当然数量级太大那还是使用数学方法吧!$m>$n的情况也能行,想优化效率不知道该怎么写了.请大神补充吧!functionking($n,$m){$monkey=range(1,$n);//模拟建立一个连续数组$i=0;while(count($monkey)>1){$i+=1;//开始查数$head=array_shift($monkey);//直接一个一个出列最前面的猴子if($i%$m!=0){array_push($monkey,$head);//如果没数到m或m的倍数,则把该猴放回尾部去.}//否则就抛弃掉了}return$monkey[0];}echo'剩余',king(3,4),'号猴子'; （defun josephus-main )
（let (lt (make-array 20 :fill-pointer 0)
（dotimes (var 20）
（vector-push var lt)
（josephus-loop lt)
（defun josephus-loop(lt)
（if (= (length lt) 1）
（progn
（format t ~a~% lt)
（return-from josephus-loop)
（if (>= (length lt) 5）
（progn
（let (setv (remove (elt lt 4）lt)
（josephus-loop setv)
（progn
（let (setv (remove (elt lt (if (= (length lt) (- 4 (length lt) (- 4 (length lt) 1） (- 4 (length lt) lt)
（josephus-loop setv) program Josephus(input,output);
type pointer=^nodetype;
nodetype=record
data:integer;
link:pointer
end;
var head,next,last:pointer;
i,n,s,j,m,k:integer;
begin
writeln('请输入组成约瑟夫环的人数：');
read(n);
new(head);
head^.data :=1;
last:=head;
for i:=2 to n do
begin
new(next);
next^.data :=i;
last^.link :=next;
last:=next
end;
last^.link :=head;
next:=head;
repeat
begin
writeln(next^.data);
next:=next^.link
end;
until next=head;
readln;
next:=head;
writeln('请输入第一个报数人的位置：');
read(s);
j:=1;
if s<=n
then
while j<s do
begin
next:=next^.link ;
j:=j+1
end
else writeln('你的输入有误');
writeln('请输入出列人的位置：');
read(m);
while next^.link <>next do
begin
k:=1;
while k<m do
begin
last:=next;
next:=next^.link ;
k:=k+1
end;
writeln(next^.data);
last^.link :=next.link ;
next:=next^.link
end;
writeln(next^.data);
readln;
readln
end. define('N',1000);//总数define('P',rand(1,N));//开始报数的位置define('M',rand(1,N/2));//报数的间距/***方法一：通过循环遍历得到结果*如果N,M比较大的话，此方法不建议使用，因为实在太LOW了*/functiongetSucessUserNum(){$data=range(0,N);unset($data[0]);if(empty($data))returnfalse;//第一个开始报数的位置$p=P;while(count($data)>1){for($i=1;$i<M;$i++){$p=(isset($data[$p]))?$p:getExistNumPosition($data,$p);$p++;$p=($p==N)?$p:$p%N;}$p=(isset($data[$p]))?$p:getExistNumPosition($data,$p);unset($data[$p]);$p=($p==N)?1:$p+1;}$data=array_values($data);echo<br>successfulnum:.$data[0].<br><br>;}/***获取下一个报数存在的下标*$data当前存在的数据*$p上一个报名数的下标*/functiongetExistNumPosition($data,$p){if(isset($data[$p]))return$p;$p++;$p=($p==N)?$p:$p%N;returngetExistNumPosition($data,$p);}/***方法二：通过算法得到结果*此方法比方法一快多了，不行自己试一下*/functiongetSucessUserNum(){$data=range(1,N);if(empty($data))returnfalse;//第一个报数的位置$start_p=(P-1);while(count($data)>1){//报到数出列的位置$del_p=($start_p+M-1)%count($data);if(isset($data[$del_p])){unset($data[$del_p]);}else{break;}//数组从新排序$data=array_values($data);$new_count=count($data);//计算出在新的$data中，开始报数的位置$start_p=($del_p>=$new_count)?($del_p%$new_count):$del_p;}echo<br>successfulnum:.$data[0].<br><br>;}

‘捌’ 约瑟夫环（c语言版数据结构） 下面是约瑟夫环的代码，跪求大神帮忙写出代码对应的算法！越详细越好！

#include <stdlib.h>
#include <stdio.h>
#include <Math.h>
typedef struct node
{int number;
int password;
struct node* next;
}Node,*Linklist;
Linklist CreateLinklist(int amount)
{int i;
Node *s=NULL,*r=NULL;
Linklist L=NULL,R=NULL;
for(i=0;i<amount;i++)
{
s=(Node*)malloc(sizeof(Node));
if(s==NULL)
{printf("空间申请失败!");
exit(0);
}
s->number=i+1;
s->password=rand()%10+1;
printf("%4d的密码%4d\n",s->number,s->password);
if(i==0)
{L=s;r=s;}
else {r->next=s;
r=s;
}
}
R=r;
r->next=L;
return(R);
}
void DeleteLinklist(Linklist R,int start,int amount,int num)
{Node *position=NULL,*p=NULL,*q=NULL;
int i,k,secret;
position=R;
secret=start;
for(i=num;i<=amount;i++)
{p=position;
for(k=1;k<secret;k++)
{p=p->next;}
q=p->next;
p->next=q->next;
secret=q->password;
printf("%5d",q->number);
if(i%10==0)
{printf("\n");}
position=p;
free(q);
}
}
int main()
{int amount,start,num;
Linklist R=NULL;
printf("\n请输入总人数：");
scanf("%d",&amount);
R=CreateLinklist(amount);
printf("\n请输入开始位置：");
scanf("%d",&start);
printf("\n请输入开始密码：");
scanf("%d",&num);
DeleteLinklist(R,start,amount,num);
return(1);
}

‘玖’ 约瑟夫算法：n个人围成一圈，每人有一个各不相同的编号，选择一个人作一个

自已找到了，在钱能的书里的！￣

//***************************
//** Josephus问题解法1 **
//** jose1.cpp **
//***************************

#include <iostream.h>

void main()
{
//建立小孩数组
const int num=10; //小孩数
int interval; //每次数interval个小孩，便让该小孩离开
int a[num]; //小孩数组
//给小孩编号
for(int i=0; i<num; i++) //小孩的编号只与小孩数有关
a[i]=i+1;
//输入数小孩间隔
cout <<"please input the interval: "; //输入一个数小孩个数
cin >>interval;
//将全体参加的小孩输出
for(int i=0; i<num; i++) //顺序输出开始时的小孩编号
cout <<a[i] <<",";
cout <<endl;

int k=1; //标识处理第k个离开的小孩
int i=-1; //数组下标(下一个值0就是第一个小孩的下标)
//处理获胜前的小孩
while(1){
//在圈中数interval个小孩
for(int j=0; j<interval; ){
i=(i+1)%num; //对下标加1求模
if(a[i]!=0) //如果该元素的小孩在圈中，则承认数数有效
j++;
}
if(k==num) break; //该小孩是最后一个(胜利者)吗？
cout <<a[i] <<","; //输出离开的小孩之编号
a[i]=0; //标识该小孩已离开
k++; //准备处理下一个圈中小孩
}
//break语句跳转到此
cout <<"\nNo." <<a[i] <<" boy've won.\n"; //输出胜利者
}

‘拾’ 循环单链表解决约瑟夫问题算法

用一组地址任意的存储单元存放线性表中的数据元素。 以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的映象) 以“结点的序列”表示线性表 称作线性链表（单链表） 单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 单链表 1、链接存储方法 链接方式存储的线性表简称为链表（Linked List）。 链表的具体存储表示为： ① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)） 注意： 链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。 2、链表的结点结构 ┌──┬──┐ │data│next│ └──┴──┘ data域--存放结点值的数据域 next域--存放结点的直接后继的地址（位置）的指针域（链域） 注意： ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 ②每个结点只有一个链域的链表称为单链表（Single Linked List）。 【例】线性表（bat，cat，eat，fat，hat，jat，lat，mat）的单链表示如示意图 3、头指针head和终端结点指针域的表示 单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。 注意： 链表由头指针唯一确定，单链表可以用头指针的名字来命名。 【例】头指针名是head的链表可称为表head。 终端结点无后继，故终端结点的指针域为空，即NULL。 4、单链表的一般图示法 由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表（bat，cat，fat，hat，jat，lat，mat）的单链表就可以表示为下图形式。 5、单链表类型描述 typedef char DataType; //假设结点的数据域类型为字符 typedef struct node{ //结点类型定义 DataType data; //结点的数据域 struct node *next;//结点的指针域 }ListNode typedef ListNode *LinkList; ListNode *p; LinkList head; 注意： ①*LinkList和ListNode是不同名字的同一个指针类型（命名的不同是为了概念上更明确） ②*LinkList类型的指针变量head表示它是单链表的头指针 ③ListNode类型的指针变量p表示它是指向某一结点的指针 6、指针变量和结点变量 ┌────┬────────────┬─────────────┐ ││ 指针变量 │ 结点变量 │ ├────┼────────────┼─────────────┤ │ 定义 │在变量说明部分显式定义 │在程序执行时，通过标准 │ ││ │函数malloc生成 │ ├────┼────────────┼─────────────┤ │ 取值 │ 非空时，存放某类型结点 │实际存放结点各域内容 │ │ │的地址 ││ ├────┼────────────┼─────────────┤ │操作方式│ 通过指针变量名访问 │ 通过指针生成、访问和释放 │ └────┴────────────┴─────────────┘ ①生成结点变量的标准函数 p=( ListNode *)malloc(sizeof(ListNode))； //函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中 ②释放结点变量空间的标准函数 free(p)；//释放p所指的结点变量空间 ③结点分量的访问 利用结点变量的名字*p访问结点分量 方法一：(*p).data和(*p).next 方法二：p-﹥data和p-﹥next ④指针变量p和结点变量*p的关系 指针变量p的值——结点地址 结点变量*p的值——结点内容 (*p).data的值——p指针所指结点的data域的值 (*p).next的值——*p后继结点的地址 *((*p).next)——*p后继结点 注意： ① 若指针变量p的值为空（NULL），则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。 ② 有关指针类型的意义和说明方式的详细解释 可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。 因此，在单链表中第 i 个结点之前进行插入的基本操作为: 找到线性表中第i-1个结点，然后修改其指向后继的指针。