约瑟夫环数学公式（约瑟夫环问题 经典求循环公式）

本文目录

• 约瑟夫环问题 经典求循环公式
• 什么是约瑟夫环它的作用是什么怎么用
• 约瑟夫环的算法原理
• 约瑟夫环（、循环链表三种方使用一维数组、一维结构体数组法完成
• 约瑟夫环问题
• 约瑟夫环问题的第推公式是怎么来的阿～～

约瑟夫环问题 经典求循环公式

提问时 应该把问题说清,不要只帖代码
要中说查错的话:
cout 《《“The winner is No.“《《index《《“.\n“;//少了个后引号
while(count《M)// 对成功的报数开始计数
{
index=(index+1)%N;//计算要报数的小孩编号 这步谁能帮我分析下？
if (in_circle[index])count++;
}
这个循环的作用就是让还在环中的小孩报数,考虑到报到队尾时必须回到头再重报,所以就有了
index=(index+1)%N;
举例来说:
从队尾index=19回队头index=0
第一圈报数时,第20个小孩(index==19)报count==5然后出圈了//if (in_circle[index])count++;
再持行index=(index+1)%N;时即从队头开始.
第二圈报数时,到第19(index==18)个小孩报数count==1后,
再持行index=(index+1)%N//index==19
if...//不计数
index=(index+1)%N//回到第一个小孩
if....//第一个小孩报count==2

什么是约瑟夫环它的作用是什么怎么用

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

约瑟夫环的算法原理

约瑟夫环运作如下：
1、一群人围在一起坐成 环状（如：N）
2、从某个编号开始报数（如：K）
3、数到某个数（如：M）的时候，此人出列，下一个人重新报数
4、一直循环，直到所有人出列 ，约瑟夫环结束

约瑟夫环（、循环链表三种方使用一维数组、一维结构体数组法完成

约瑟夫环：约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
***********************************************************************************************************************
一维数组：
#include 《stdio.h》 　　
#define M 10/*总人数*/ 　　
#define N 5 　　
#define START 0/*第一个报数的人*/ 　　
void main(void) 　　
{ 　　int a[M],i=0,k,count=0;
　　while(i++《M)/*给每个人编号*/
　　a[i-1]=i;
　　for(i=START;count《=M-1;count++)
　　{ 　　for(k=1;k《=N;a[i++]&&++k)/*根据&&运算的路短原理，若a[i]为0的话，++k的运算会被省略而++i的运算总会进行*/
　　 if(i》M-1) 　　i=0;
　　printf(“%d “,i?a[i-1]:a[M-1]);
　　a[(i?(i-1):(M-1))]=0;
　　}
　　getch();
　}
***********************************************************************************************************************
一维结构体数组方式：
#include《stdio.h》
#include《stdlib.h》
typedef struct node{
int value;
struct node *next;
}NODE;
NODE *createlink(int n){
NODE *head=NULL,*p=NULL,*q=NULL;
int i=1;
head=p=(struct node*)malloc(sizeof(struct node));
p-》value=i;
for(i=2;i《=n;i++){
q=(struct node*)malloc(sizeof(struct node));
if(q==0) return 0;
p-》next=q;
p=q;
p-》value=i;
}
p-》next=head;
return head;
}
void jose(NODE *p,int n,int m){
int i,j,g=0;
NODE *q=NULL;
for(i=1;i《=n;i++){
for(j=1;j《m;j++){
p=p-》next;}
q=p-》next;
p-》next=q-》next;
if(g%5==0)
{g++;printf(“\n“);}
else g++;

printf(“%3d:%3dout “,i,q-》value-1);
free(q);
}
printf(“\n“);
p-》next=NULL;
}
int main( ){
int m=0;
int n=0;
scanf(“%d“,&m);
scanf(“%d“,&n);
NODE *head=NULL;
head=createlink(n);
jose(head,n,m);
return 0;
}
***********************************************************************************************************************循环链表方式：
#include “stdio.h“
#include “stdlib.h“
#define S sizeof(struct node)

struct node
{
int num;
struct node *next;
};

typedef struct node NODE;

NODE *createlinklist(int n)
{
NODE *head,*p,*q;
int i=1;
head=p=(struct node*)malloc(sizeof(struct node));
p-》num=i;
for(i=2;i《=n;i++)
{
q=(struct node*)malloc(sizeof(struct node));
if(q==0) return(0);
p-》next=q;
p=q;
p-》num=i;
}
p-》next=head; /*使链表尾指向链表头 形成循环链表*/

return head;
}

void printlinklist(NODE *p,int n)
{
int i;
NODE *q = p;
if(NULL == q-》next){
printf(“the list is NULL!“);
return;
}
printf(“所有玩家的信息列表:\n“);
for(i=1;i《=n;i++)
{
if(NULL == q){
printf(“the list is NULL!“);
return;
}
printf(“%d “,p-》num);
p=p-》next;
}
printf(“\n“);
}

void joseph(NODE *p,int n,int m)
{
int i,j;
NODE *q;
for(i=1;i《n;i++)
{
for(j=1;j《=m-1;j++)
{
p=p-》next;
}
q=p-》next;
p-》next = q-》next;
printf(“%d “,q-》num);
free(q);
}
printf(“\n最后剩余的是第%d号.\n“,p-》num);
p-》next=NULL;
}

void main()
{
NODE *head;
int n,m;
printf(“请输入人数N:\n“);
scanf(“%d“,&n);
printf(“输入K:\n“);
scanf(“%d“,&m);
head=createlinklist(n);
printlinklist(head,n);
printf(“依次被选出的是:\n“);
joseph(head,n,m);
}

***********************************************************************************************************************
我想我知道你是谁了。。。

约瑟夫环问题

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m mod n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m mod 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) mod n
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式
f=0;
f=(f+m) mod i; (i》1)
有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1

约瑟夫环问题的第推公式是怎么来的阿～～

/*约瑟夫问题的数学方法

无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达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=0;
f[i]=(f[i-1]+m)%i; (i》1)

有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1

由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：*/

#include 《stdio.h》
main()
{
int n, m, i, s=0;
printf(“N=“); scanf(“%d“, &n);
printf(“M=“); scanf(“%d“, &m);
for(i=2; i《=n; i++) s=(s+m)%i;
printf(“The winner is %d\n“, s+1);
}

/*这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。*/