Question

约瑟夫问题c语言

这是一道C语言的约瑟夫问题。

M个人围成一圈，从第一个人开始依次从1循环报数，每当报数为N时此人从圈中出

来，下一个人又从1开始报数，直到圈中只剩下一个人为止。请按退出次序输出出圈人员来

的编号以及留在圈中的最后一个人原来的编号。

提示：

1、声明两个数组，A数组存放人是否在圈中的标记，在为0，已出列为-1；B数组存放

编号，是顺序记录出圈人的顺序，最后一个即为留在圈中的人。组成圈的人数为M，报号

为N。

2、 A数组因为是表示一个圈，所以最后一个接着第一个，当编号大于最后一个编号

时，接到前面开始部分。当下标号为M时，让其再变为0，下标号为M以后相当于0开始的

又一圈开始。

小弟的C语言水平有限，不知道该怎么做，希望各位C语言高手指点迷津，小弟感激不

尽！
题目不是有说明了 要用数组
不要用链表

Answer 1

#include<stdio.h>
#define size 100 /* 输入人数的上限 */
void main()
{
int person[size];
int i, j; /* 循环修正变量 */
int arrayLen; /* 数组长度 */
int start, overNum; /* 开始位置各跨过位置 */
int deleNum; /* 出列人所在数组中的下标 */
int name, total; /* 输入时,人的信息以及人的总数 */
printf( "请输入圆桌上人的总数: " );
scanf( "%d", &arrayLen ); printf( "\n" );
if( ( arrayLen > size ) || ( arrayLen < 0 ) )
{
printf( "超出范围,请重新输入: " );
scanf( "%d", &arrayLen ); printf( "\n" );
};
printf( "请输入各个人的信息(整数): \n" );
for( i = 0; i < arrayLen; i++ )
{
scanf( "%d", &name );
person[i] = name;
}
printf( "你输入的数据的顺序为: \n" );
for( i = 0; i < arrayLen - 1; i++ )
printf( " %d ==>", person[i] );
printf( "%d \n", person[arrayLen - 1] );
printf( "你打算从第几个人开始? 请输入开始号: " );
scanf( "%d", &start );
printf( "\n" );
start = start - 1;
printf( "请输入相邻两出列人之间的间隔: " );
scanf( "%d", &overNum );
printf( "\n" );

total = arrayLen;
printf( "程序运行后,出列人的顺序为:\n\n" );
for( i = 0; i < total; i++ ) /* 要打印total个人的情况,故做total次 */
{
if ( arrayLen == 1 )
printf( "%d", person[0] ); /* 如果是数组只剩一个元素,直接出列 */
else
{
deleNum = ( start + overNum - 1 ) % arrayLen; /* 此取模保证循环 */
printf( "%d ==> ", person[deleNum] );
for ( j = deleNum; j < arrayLen; j++ ) /* 将出列元素后面的各元素前移 */
person[j] = person[j+1];
start = deleNum;
arrayLen = arrayLen - 1; /* 移动完毕后,数组长度减1 */
}
}
printf( "\n\n" );
}

从一本数据结构书上看到的用向量实现此问题：
void Josephus (Vector <int> &P, int n, int s, int m)
{
//将人员编号存入向量P；
int k = 1;
for(int i = 0; i<n, i++)
{P.Insert(k,i); k++;}
int s1 = s;
for(int j = n; j>=1; j--)
{
s1=(s1+m-1)%j;
if(s1== 0) s1 = j;
int w = P.Getnode(s1 - 1);
P.Remvoe(s1 - 1);
P.Insert(w,n-1);
}
}
以前学C语言的时侯写的，希望对你有用。

Answer 2

1、约瑟夫问题：Joseph问题的一种描述是：编号为1、2、……、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

2、例程：

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;int num;
struct LNode *next;
}LNode,*LinkList;
void CreateList_L(LinkList *L,int n)
{ int i=0;
ElemType e;
LinkList p,q;
*L=(LinkList)malloc(sizeof(LNode));
(*L)-> next=NULL;(*L)-> data=n;
q=*L;
while(i <n)
{ scanf("%d",&e);
p=(LinkList)malloc(sizeof(LNode));
p-> data=e;p-> num=i+1;
p-> next=NULL;
q-> next=p;
q=p;
i++;
}
p-> next=(*L)-> next;
}
void PrintList(LinkList L)
{ int i=0;
LinkList p;
p=L-> next;
while(i <L-> data)
{
printf("%5d",p-> data);
p=p-> next;
i++;
}
printf("\n");
}
void Put(LinkList *L)
{ int i,m;LinkList p,q;
printf("input a number:\n");
scanf("%d",&m);
q=(*L)-> next;
while((*L)-> data)
{for(i=0;i <m-1;i++)
{p=q;
q=q-> next;
}
printf("%5d",q-> num);
m=q-> data;
p-> next=q-> next;
free(q);
q=p-> next;
(*L)-> data=(*L)-> data-1;
}
}
void main()
{LinkList L;
int a;
printf("请输入人数:");
scanf("%d",&a);
printf("请输入密码:");
CreateList_L(&L,a);
printf("您输入的数字为:\n");
PrintList(L);
Put(&L);
}

Answer 3

约瑟夫问题：
#include<iostream.h>
struct
Node
{
int
data;
Node
*pNext;
};
void
main()
{
int
n,k,m,i;
Node
*p,*q,*head;
cout<<"输入n的值:";
cin>>n;
cout<<"输入起始报数人号码k的值:";
cin>>k;
cout<<"输入
数到m出列的m的值:";
cin>>m;
head=(Node*)new
Node;
//确定头结点
p=head;
for(i=1;i<=n-1;i++)
//赋初值
{
p->data=i;
p->pNext=(Node*)new
Node;
//为下一个新建内存
p=p->pNext;
}
p->data=n;
//最后一个单独处理
p->pNext=head;
//指向头，形成循环链表
p=head;
while(p->data!=(p->pNext)->data)
//p->data==(p->pNext)->data表示只剩下一个结点的
{
while(p->data
!=k)
//寻找编号为k的结点
p=p->pNext;
if(m==1)
{
for(i=1;i<=n;i++)
{
cout<<p->data<<'\\t'
;
p=p->pNext
;
}
cout<<'\
';
return;
}
else
for(i=1;i<m-1;i++)
//开始报数
{p=p->pNext;}
//找到报m-1的结点
q=p->pNext;
//q为报m的结点
cout<<q->data<<"\\t";
//输出报m的结点的值
k=(q->pNext)->data;
//k为下一个报数的起点
p->pNext=q->pNext;
//删除报m的结点
}
cout<<p->data<<'\
';
//输出最后一个结点的值
}

Answer 4

根据个人思维写的：已经在KEIL C中调试通过。
typedef unsigned char u8;

#define m 15
#define n 4

u8 a[m+1];

void main()
{
u8 i ,j ,k,ii,Rn,s,value;//itemp;
for(i=1;i<=m;i++)//给数组赋初值；
a[i]=i;
Rn=1;//i作为数组标识;
s=m;

while(s>1)
{
i=1;//i作为数组标识；

for(j=Rn;j<s+Rn;j++)//j循环；标出被整除为0的数组；
{
if(j%n==0)
{
a[i]=0;
}
i++;
}
if((s+Rn)<=n)
{
while(j%n!=0)
{
j++;
}
a[j-s]=0;
}
i=1;
for(j=1;j<=s;j++)//j循环；将数组中为0的数清除并重新排列数组；
{
if(a[i]==0)
{
if(i==(s-ii)){ii++;break;}//如果是数组中最后一位数为0已过来的，则；
else
{for(k=i;k<s-ii;k++)
a[k]=a[k+1];
ii++;
i--;
j--;}
}
i++;
}
Rn=s%n+Rn;
if(Rn==n )
{
Rn=0;

}
else if(Rn>n)
Rn=Rn%n;

if((Rn==0)&&(s<n))
{
Rn=1;
}

s-=ii;
ii=0;
}
value=a[1];
while(1);
}

Answer 5

我自己写的直接用一维数组解决
#include
#define N 9 //总人数
#define K 1 //开始数数的人
#define M 3 //间隔的人数

//给数组赋值
void setDate(int a[],int n)
{ int i;
for(i=0;i<n;i++)
a[i]=i+1;
}
//删除被选中的孩子
void deleted(int a[],int m,int len)
{
int i=m;
do
{
a[i]=a[i+1];
i++;
}while(i<len);
}

//开始play
void play(int a[],int k,int m)
{
int len =N;
int dm=k+m-2;//第一个被剔除的孩子
while(len!=1)
{printf("第%d个孩子被剔除。\n",a[dm]);
deleted(a,dm,len);//将被剔除的孩子从数组中删除
dm=dm+M-1;//下一个被剔除的孩子
len--;//数组的长度减1
if(dm>=len) dm=dm-len;
}
printf("最后一个孩子是%d.",a[0]);//最后一个孩子被放在a[0]中
}
main()
{
int a[N];
setDate(a,N);
play(a,K,M);

}