约瑟夫环问题,求约瑟夫环问题的解法

本文目录一览：

• 1、有N个人围成一环形圈，第一个人从1开始报数，报道M的人出列，直到最后一个同学，请写出算法。
• 2、约瑟夫环的介绍
• 3、求解约瑟夫环的思路分析
• 4、约瑟夫环问题的数学解
• 5、约瑟夫环问题
• 6、什么是约瑟夫问题
• 7、求约瑟夫环问题的解法
• 8、约瑟夫问题的一般形式
• 9、关于约瑟夫环问题的实验报告书中详细设计
• 10、数学上的约瑟夫问题怎么解

有N个人围成一环形圈，第一个人从1开始报数，报道M的人出列，直到最后一个同学，请写出算法。

建一个单循环链表类，结点类
将n个人连成单循环链表circle,每个结点信息为人名 例如：char name
for(int i=1;i<=n;i++)
circle.InsertBefore(i,name);
调用约瑟夫求解函数
Joseph(CirList &circle,int n,int m)
{
ListNode *p,*current;
current=circle.NextElem(); //指向下一结点
for(int i=1;i<=n-1;i++) //删除过程循环n-1次
{
for(int j=1;j<=m-1;j++) //将current往后移m-1次
current=circle.NextElem(current);
p=circle.Delete(current);//删除当前节点并返回地址
cout<<"出列顺序:"<GetNodeData()< delete p;
}
current=circle.NextElem();
p=circle.NextElem(current);
cout<<"出列顺序:"<GetNodeData()<}
经典的约瑟夫环问题
设n个人围成一圈，标号为0..n-1，从第一个人开始依次从1到k循环报数，当报到k的
时候此人出圈。设J(n, k, i)表示第i个出圈的人的标号。
定理一:
J(n, k, 1) = (k-1) MOD n, (n>=1, k>=1) ………… (1)
证明：由定义直接得证。
定理二：
J(n+1, k, i+1) = (k + J(n, k, i)) MOD (n+1), (n>=1, k>=1, 1<=i<=n) ………
… (2)
证明：
设g = J(n, k, i)，因此如果有n个人，从0开始报号，第i个出圈的标号为g。现在考
虑J(n+1, k, i+1)，因为J(n+1, k, 1) = (k-1) MOD (n+1)，即第一步的时候删除数
字(k-1) MOD (n+1)，第二步的时候从数字k开始数起。因而问题变为了找到剩下的n
个数字中从k开始数起被删除的第i个数字(注意这时(k-1) MOD (n+1)已经被删除了)
，而这恰好就是(g+k) MOD (n+1)，(2)成立。
根据(2)，很容易求得n个数里面第i个出圈的数。
就根据这个定理递推计算吧！
我的一个已测试程序：不妨一看。
http://hi.baidu.com/shy2850/blog/item/0ca9293c43aef50abaa16788.html
建一个单向循环链表
经典的约瑟夫环问题
设n个人围成一圈，标号为0..n-1，从第一个人开始依次从1到k循环报数，当报到k的
时候此人出圈。设J(n,
k,
i)表示第i个出圈的人的标号。
定理一:
J(n,
k,
1)
=
(k-1)
MOD
n,
(n>=1,
k>=1)
…………
(1)
证明：由定义直接得证。
定理二：
J(n+1,
k,
i+1)
=
(k
+
J(n,
k,
i))
MOD
(n+1),
(n>=1,
k>=1,
1<=i<=n)
………
…
(2)
证明：
设g
=
J(n,
k,
i)，因此如果有n个人，从0开始报号，第i个出圈的标号为g。现在考
虑J(n+1,
k,
i+1)，因为J(n+1,
k,
1)
=
(k-1)
MOD
(n+1)，即第一步的时候删除数
字(k-1)
MOD
(n+1)，第二步的时候从数字k开始数起。因而问题变为了找到剩下的n
个数字中从k开始数起被删除的第i个数字(注意这时(k-1)
MOD
(n+1)已经被删除了)
，而这恰好就是(g+k)
MOD
(n+1)，(2)成立。
根据(2)，很容易求得n个数里面第i个出圈的数。
就根据这个定理递推计算吧！

约瑟夫环的介绍

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后1结果+1即为原问题的解。

求解约瑟夫环的思路分析

约瑟夫环
是一个数学的应用问题：
已知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 {
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 {
r=p；
p=p->link;
}
/*循环地删除队列结点*/
while(p->link!=p)
{
for(i=0;i {
r=p;
p=p->link;
}
r->link=p->link;
printf("被删除的元素：%4d ",p->data);
free(p);
p=r->link;
}
printf("\n最后被删除的元素是：％4d",P->data);
}

约瑟夫环问题的数学解

下午和朋友聊天的时候，有朋友提到了约瑟夫环问题。你和另外 n-1 个人围成一个圈，按 1，2，...，n 依次编号。第一个人从 1 开始报数，数到 k 的人会被杀掉，然后下一个人重新从 1 开始报数。如此往复，直到最后只剩下一个人。问题是，你应该如何选择自己的初始位置，才能保证最后不被杀掉呢？
速度越快的算法当然越好，毕竟这是一个生死攸关的问题。下面你将会看到，我们如何通过一些基本的数学推导最终得到这个问题的递推解。
考虑这样一种相对简单的情况：总共有 5 个人，数到 3 的人被杀掉。那么，死亡过程如下图所示：
经过一番模拟之后，我们已经对约瑟夫环问题有了一个大概的直观理解。下面，尝试使用数学语言来描述这个问题。
哦对了，假如圆圈里只有你自己，那么你肯定就是最后的幸存者，这是一个极其有用的特殊情况。
这些是我们的 已知条件 ：
这个是我们的 未知数 ：
现在考虑一种泛化情形：总共有 n 个人，数到 k 的人被杀掉，其中 n >= k。幸存者的位置为 p n 。
显而易见，初始位置为 k 的人将会第一个被杀掉。此时，经过重新排序之后，问题变成了 n-1 个人的情形。幸存者的位置为 p n-1 。如果能够找到从 p n-1 到 p n 的递推关系，那么问题就解决了。
重新排序之后，每个人的位置发生了下面这些变化：
很容易我们能得到这样一个关系式：p n = (p n-1 + k) % n 。再加上刚才讨论的特例，只有一个人的情况时，p 1 = 1 。递推式就已经很明显了。
当然上文只讨论了 n>=k 的情形，实际上对于 n 既然递推式这么简洁明确，那么编码实现就不用写了吧？

约瑟夫环问题

约瑟夫环有好多种解法，
但是大体的可以分为两类：
1. 将符合出圈要求的人进行标注，但是不出圈，只是下次再轮到此人时，直接跳过，不参加报数
2. 将符合出圈要求的人直接出圈(从环中删除），剩下的人继续报数
这里列的是第二种方法
出圈的处理在这里： p[i-1]=i;
由于已经有人出圈，所以编号也就得-1了：（s1+m-1）%i
for(j=s1;j<=i-1;j++)
p[j-1]=p[j];
看到了么,这段代码已经把原来的第11号人移到现在的10号位置了

什么是约瑟夫问题

来源是智取奖品问题：
许多人围成一个圈报数，报到一个特定的数的人退出，一支循环下去。
约瑟夫就是猴子选大王，猴子报数，最后选出大王。
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。
假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。

求约瑟夫环问题的解法

#include
using namespace std;
struct Josephus{
int a;
int num;
struct Josephus *next;
};
struct Josephus *head;
void InitList( int n ){
struct Josephus *p;
int i;
p = (struct Josephus *)malloc( sizeof(struct Josephus) );
head = p;
for( i = 0; i < n; i++ ){
struct Josephus *p2;
scanf( "%d", & p->a );
p->num = i + 1;
if( i != 6){
p2 = (struct Josephus *)malloc( sizeof(struct Josephus) );
p->next = p2;
p = p->next;
}
}
p->next = head;
}
void Exclude(){
struct Josephus *p,*prev;
int m = 20, i = 1;
p = head;
while (1){
prev = p;
p = p->next;
i++;
if( i == m ){
cout << p->num << ' ';
m = p->a;
prev->next = p->next;
i = 0;
if( p->next == p ){
free( p );
return;
}
free( p );
p = prev;
}
}
}
int main(){
int n = 7;
InitList(n);
Exclude();
}
是约瑟夫森环吗？
自己写的 C++程序
希望对你有帮助
/*约瑟夫环 Joseph
是一个数学的应用问题：
已知n个人（以编号1，2，3...n分别表示）
围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；
依此规律重复下去，直到圆桌周围的人全部出列。
例如：n = 9, m = 5
【解答】 出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。*/
#include
using namespace std;
struct list
{
struct list *last;
int data;
int xh;
struct list *next;
};
int main()
{
int n, m;
cin>>n>>m;
int i;
list *h=NULL,*q=NULL,*d=NULL;
for(i=1;i<=n;i++)
{
list *p=new list;
p->last=NULL;
p->data=0;
p->xh=i;
p->next=NULL;
if(h==NULL)
{
h=p;
q=h;
}
else
{
q->next=p;
p->last=q;
q=p;
}
}
q->next=h;
h->last=q;
q=h;
i=1;
while(q->last!=q)
{
if(i>m)
i=i%m;
q->data=i;
if(q->data==m)
{
cout<xh<<' ';
q->last->next=q->next;
q->next->last=q->last;
d=q;
q=q->next;
delete d;
}
else
q=q->next;
i++;
}
cout<xh<<' ';
system("pause");
return 0;
}

约瑟夫问题的一般形式

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。分析：（1）由于对于每个人只有死和活两种状态，因此可以用布朗型数组标记每个人的状态，可用true表示死，false表示活。（2）开始时每个人都是活的，所以数组初值全部赋为false。（3）模拟杀人过程，直到所有人都被杀死为止。pascal代码var a:array [1..20] of integer;n,m,i,j,k,n1,m1:integer;beginreadln(m,n);for i:=1 to m doa[i]:=i;m1:=m;n1:=1;while m1>0 dobeginj:=(n+n1-1-1) mod m1 +1;n1:=j;m1:=m1-1;writeln(a[j]);for k:=j to m1 doa[k]:=a[k+1];end;end.C++代码： #includeusingnamespacestd;main(){bool a[101]={0};intn,m,i,f=0,t=0,s=0;cin>>n>>m;do{++t;//逐个枚举圈中的所有位置if(t>n)t=1;//数组模拟环状，最后一个与第一个相连if(!a[t])s++;//第t个位置上有人则报数if(s==m)//当前报的数是m{s=0;//计数器清零cout< 0k+1 --> 1k+2 --> 2......k-2 --> n-2变换后就完完全全成为了（n-1）个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k) mod n如何知道（n-1）个人报数的问题的解？对，只要知道（n-2）个人的解就行了。（n-2）个人的解呢？当然是先求（n-3）的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]递推公式f[1]=0;f=(f+m) mod i; (i>1）有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1由于是逐级递推，不需要保存每个f，程序也是异常简单：c++ #include using namespace std;const int m = 3;int main(){ int n, f = 0; cin >> n; for (int i = 1; i <= n; i++) f = (f + m) % i; cout << f + 1 << endl;}pascal var n,m,i,s:integer;beginwrite('N M =');read(n,m);for i:=2 to n dos:=(s+m) mod i;writeln('The winner is ',s+1）;end.这个算法的时间复杂度为O(n），相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。约瑟夫问题10e100版（from vijios)描述 Descriptionn个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人最开始的编号。输入格式 Input Format一个正整数n，表示人的个数。输入数据保证数字n不超过100位。输出格式 Output Format一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。样例输入 Sample Input9样例输出 Sample Output3时间限制 Time Limitation各个测试点1s注释 Hint样例说明当n=9时，退出圈子的人的编号依次为：2 4 6 8 1 5 9 7最后剩下的人编号为3初见这道题，可能会想到模拟。可是数据实在太大啦！！我们先拿手来算，可知n分别为1，2，3，4，5，6，7，8...时的结果是1，1，3，1，3，5，7，1...有如下规律：从1到下一个1为一组，每一组中都是从1开始递增的奇数，且每组元素的个数分别为1，2，4...这样就好弄了！！大体思路如下：①read(a)②b:=1,c:=1{b为某一组的元素个数，c为累计所加到的数}③while c9thenbeginc:=c+cdiv10;c:=cmod10;end;end;functioncxiaoa:boolean;vari:integer;begincxiaoa:=false;fori:=105downto1doifcathenbreak;end;proceduredoubleb;vari:integer;beginfori:=1to105dob:=b*2;fori:=1to104doifb>9thenbeginb:=b+bdiv10;b:=bmod10;end;end;proceduredecc;vari,j:integer;beginfori:=1to104doifc>=bthenc:=c-belsebeginj:=i+1;whilec[j]=0doinc(j);whilej>idobeginc[j]:=c[j]-1;c[j-1]:=c[j-1]+10;dec(j);end;c:=c-b;end;end;procedurefua;vari:integer;beginfori:=1to104doifa>cthena:=a-celsebegina:=a-1;a:=a+10;a:=a-c;end;end;procedureoutit;vari,j:integer;beginfori:=1to105doa:=a*2;fori:=1to104doifa>9thenbegina:=a+adiv10;a:=amod10;end;ifa[1]>0thena[1]:=a[1]-1elsebeginj:=2;whilea[j]=0doinc(j);whilej>1dobegina[j]:=a[j]-1;a[j-1]:=a[j-1]+10;dec(j);end;a[1]:=a[1]-1;end;fori:=105downto1doifa>0thenbeginj:=i;break;end;fori:=jdownto1dowrite(a);end;beginreadln(s);la:=length(s);fori:=ladownto1doa:=ord(s[la+1-i])-ord('0');b[1]:=1;c[1]:=1;whilecxiaoadobegindoubleb;incc;end;decc;fua;outit;end.

关于约瑟夫环问题的实验报告书中详细设计