本文目录
- 约瑟夫环问题
- 什么是约瑟夫环它的作用是什么怎么用
- 约瑟夫环的算法原理
- 约瑟夫环问题 经典求循环公式
- 约瑟夫环问题的第推公式是怎么来的阿～～
- 约瑟夫环（c语言）
- 约瑟夫环（、循环链表三种方使用一维数组、一维结构体数组法完成
约瑟夫环问题
问题描述：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
什么是约瑟夫环它的作用是什么怎么用
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
约瑟夫环的算法原理
约瑟夫环运作如下：
1、一群人围在一起坐成 环状（如：N）
2、从某个编号开始报数（如：K）
3、数到某个数（如：M）的时候，此人出列，下一个人重新报数
4、一直循环，直到所有人出列 ，约瑟夫环结束
约瑟夫环问题 经典求循环公式
提问时 应该把问题说清,不要只帖代码
要中说查错的话:
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
约瑟夫环问题的第推公式是怎么来的阿～～
/*约瑟夫问题的数学方法
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达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等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。*/
约瑟夫环（c语言）
怎么了，代码看不懂？
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。
首先我们列出一些有关约瑟夫环的结果：
1 1 2 2 3 2 4 1 5 4 6 1 7 4 8 7 9 1 10 4
11 7 12 10 13 13 14 2 15 5 16 8 17 11 18 14 19 17 20 2021 2 22 5 23 8 24 11 25 14 26 17 27 20 28 23 29 26 30 29
31 1 32 4 33 7 34 10 35 13 36 16 37 19 38 22 39 25 40 28
41 31 42 34 43 37 44 40 45 43 46 46 47 2 48 5 49 8 50 11
51 14 52 17 53 20 54 23 55 26 56 29 57 32 58 35 59 38 60 41
61 44 62 47 63 50 64 53 65 56 66 59 67 62 68 65 69 68 70 171 4 72 7 73 10 74 13 75 16 76 19 77 22 78 25 79 28 80 31
81 34 82 37 83 40 84 43 85 46 86 49 87 52 88 55 89 58 90 61
91 64 92 67 93 70 94 73 95 76 96 79 97 82 98 85 99 88 100 91
意思是，前一个数为约瑟夫环的人数，后一个数为最后出去的人的号码。
从上面的表中我们可以归纳出以下两个规则：
规则1:若上一组数字中最后保留号比人数少一，则下一数从1开始记。
例如第三组（3,2）为上一组，最后保留好为2，比3少1，下一组的数字（4,1），最后保留号为1
规则2:若上一组数字为最后保留号与人数相等，则下一数从2开始记。
约瑟夫环（、循环链表三种方使用一维数组、一维结构体数组法完成
约瑟夫环：约瑟夫环是一个数学的应用问题：已知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);
}
***********************************************************************************************************************
我想我知道你是谁了。。。
