数据结构中的约瑟夫环问题用C语言怎么编写出来啊?

Question

关键字:约瑟夫环问题,C语言

Answer 1

题目：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出
　　　圈子，问最后留下的是原来第几号的那位。
1. 程序分析：这是一个比较经典的算法--约瑟夫环问题.
2.个人分析: 算法比较经典,对于这样的问题本应该使用链表的形式会比较容易.约瑟夫环算法
则体现了使用数组来完成链表该完成的功能,虽然形式上完全不相同,但却求出了
相同的结果.有异曲同工之妙.总之我个人认为是数组中非常经典的算法了.希望本
人写的代码不会叫大家啐骂!

3.程序源代码：

#include <stdio.h>
#define N 50
#define S 3

void main()
{
int a[N];
int i,k;
int sum=N;

k=0;

for(i=0;i<N;i++)
a[i]=i+1;

for(i=0;i<N;i++)
printf("%-4d",a[i]);

printf("\n");

for(i=0;;i++)
{
if(sum==1)
break;

if(a[i%N]!=0)
{
k++;
}

if(k==S)
{
k=0;
//printf("%4d",a[i%N]);
a[i%N]=0;
sum--;
}
}

for(i=0;i<N;i++)
if(a[i]!=0)
printf("\n最后一个数为:%d\n",a[i]);
}

两年前念书的时候写的,献丑了!

Answer 2

#include <iostream>
using namespace std;
#define FALSE 0
#define TRUE 1
#define MODNUM 3
typedef int BOOL;

void main(void)
{
____BOOL bLoop;
____int iRotation=0,iCounteract=0,iLast;
____int iTotalNumber,iNTotalNumber=0;
____char *piInGameing;

____cout<<"请输入共有几人参加游戏\n";
____cin>>iTotalNumber;

____piInGameing=new char[iTotalNumber];
____for(int i=0;i<iTotalNumber;i++)
____ ___piInGameing[i]='1';

____do{
____ ____bLoop=FALSE;
____ ____for(int i=0;i<iTotalNumber;i++)
____ ____{
____ ____ ___if('0'!=piInGameing[i])
____ ____ ___{
____ ____ ____ ___bLoop=TRUE;
____ ____ ____ ___if(0==(iNTotalNumber+(i+1)-iCounteract)%MODNUM)
____ ____ ____ ____ ___piInGameing[iLast=i]='0';
____ ____ ___}
____ ____ ___else
____ ____ ____ ___iCounteract++;
____ ____}
____ ____iRotation++;
____ ____iNTotalNumber=iRotation*iTotalNumber%MODNUM;
____}while(bLoop);

____delete [] piInGameing;

____cout<<"最后一个是原来的第"<<iLast+1<<"号\n";
}

//注:各句开头的下画线'_'全都代表空格

Answer 3

#include<stdio.h>
#include<malloc.h>
#define Namelength 10
typedef struct CLNode{
char*name;
int ID;
int pastword;
struct CLNode *next;
}child,*ptrchild;
ptrchild CreateCList(int n)
{int i;
ptrchild p,head,rear;
printf("please input the children information:");
rear=head=(ptrchild)malloc(sizeof(child));
rear->next=head;

for(i=0;i<n;i++)
{getchar();
p=(ptrchild)malloc(sizeof(child));
p->ID=i+1;
p->name=(char*)malloc(Namelength*sizeof(char));
gets(p->name);
scanf("%d",&(p->pastword));
rear->next=p;
rear=p;
}
rear->next=head;
return head;
}

Joshpus(ptrchild head,int m)
{ptrchild p,q;int i=0;
p=head;
while(head->next!=head)
{while(i<m)
{q=p;
p=p->next;
if(p==head){q=head;p=p->next;}
i++;
}
printf("\nID:%d Name:%s",p->ID,p->name);
q->next=p->next;
m=p->pastword;
i=0;
free(p);
p=q;
}
printf("\n");
}

main()
{ptrchild CL;
int n,m;
printf("please input the number of children:");
scanf("%d",&n);
CL=CreateCList(n);
printf("please input the initial value of m:");
scanf("%d",&m);
Joshpus(CL,m);
}