按要求用C语言写约瑟夫环

Question

C语言高手快来帮帮我啊～

用C语言按要求写约瑟夫环！

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

（2）基本要求：可以利用单项循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和密码。

（3）实现提示：用不带头结点的单循环链表表示一圈人的编号和密码，程序一开始，要求用户指定初始报数的上限，然后依次输入各人的密码。

（4）程序实现：用一个结构体表示每个人的编号和密码，将结构体连起来构成循环单链表。

相信百度里有高手啊～

Answer 1

这没啥高手的，人称入门题目，也就是说，会做这个基本就可以用C做一些东西了。这是我以前写的，从博客上面搞下来的，你试试看能不能运行，我当时似乎是运行过了的。不过这个不是用链表做的，用数组做的，你结合链表的语法把他改一下就行了，很简单的，就一个结构体而已么，反正基本思路这样就对了。另外对了，当时水平有限还不懂动态分配内存，你去查一下malloc函数的用法，觉得合适可以加进去，你用new命令也可以动态分配内存，具体的可以去看看MSDN，MSDN好东西啊。

#include<stdio.h>
#include<stdlib.h>
void main()
{
int a[100]; /*用来放环里的每个人的，人口上限（好像在打魔兽争霸）100，当然可以再改大*/
int n,r,ctor,u; /*n是用来循环赋值的，给r个人循环赋1~u，一共r个人，ctor计数器，到了u再重新归1*/
int call(int a[],int real,int u); /*报数函数*/

for(n=0;n<=99;n++)a[n]=0; /*给所有元素赋值为0，这样以后没赋值1~u的就都为0，可以当作不存在*/

printf("/约瑟夫环 JOSEPHUS/\n\n");
printf("输入参与报数的人数\n");
scanf("%d",&r);
printf("输入报数上限\n");
scanf("%d",&u);
ctor=1;

for(n=0;n<r;n++) /*这个循环里给输入的人数都赋值，从1到u，相当于报的数*/
{
*(a+n)=ctor;
ctor++;
if(ctor>u)ctor=1;
}
call(a,r,u);system("pause"); /*调用点名函数*/
}

int call(int a[],int real,int u)
{
int n1,i;
int *p;
p=(a+u-1);
n1=0;i=u;

for(;n1<real-1;p++)
{
if(p>(a+real-1))p=a; /*如果点名点过了，就接着队伍没有出列的第一个人继续*/
if(*(p)!=0) /*如果扫描的数字不为零，说明这个人还在队列中，那么看下面*/
{
if(i>u)i=1; /*由于是剩下的人继续报数，所以当报到u这个上限时，还是要从新归1*/
if(i==u) /*当到达上限，说明这个人该出列啦，它的位置就填充为0*/
{
*(p)=0;n1++; /*n1计算着一共多少人出列，通过n1<real-1,可以留下最后一个人，这是最终目的*/
}
i++;
}
}

for(i=0;i<real;i++) /*从新扫描数组，发现不是0的就输出，到这时候肯定只剩一个数不是0了*/
if(*(a+i)!=0)printf("所剩最后一位原来的呼号是%d\n\n",i+1);
}

写完了

Answer 2

刚刚也有人问了，真是巧。我昨天自己还在做数据结构时候也碰到了。所以两个都给你吧
#include<stdio.h>
#define N 13

struct person
{
int number;
int nextp;
}link[N+1];

void main()
{
int i,count,h;
for(i=0;i<=N;i++)
{
if(i==N)
link[i].nextp=1;
else
link[i].nextp=i+1;
link[i].number=i;
}
printf("\n");
count=0;
h=N;
printf("sequence that persons leave the circle:\n");
while (count<N-1)
{
i=0;
while(i!=3)
{
h=link[h].nextp;
if(link[h].number)
i++;
}
printf("%4d",link[h].number);
link[h].number=0;
count++;
}
printf("\nThe last one is");
for(i=1;i<=N;i++)
if(link[i].number)
printf("%3d",link[i].number);
printf("\n");
}

数据结构的思路：
void Josephus(int n,int m,int s)
//使用带表头附加节点的循环单链表为空
{
//生成表头附加结点，此时循环单链表为空
LNode* HL=new LNode;
HL->next=HL;
int i;
//生成含n个结点的，结点值依次为1-n的带表头附加结点的循环表
for(i=n;i>=1;i--)
//生成新结点
LNode* newptr=new LNode;
newptr->data=i;
//新结点插入到表头
newptr->next=HL->next;
HL->next=newptr;
}
//从表头开始顺序查找出第s个结点，对应第1个开始报数的人
LNode *ap=HL,*cp=HL->next;
for(i=1;i<s;i++){
//ap和cp指针后移一个位置
ap=cp;
cp=cp->nextl
//若cp指向了表头附加的结点，则仍需后移指针，使之指向表头结点
if(cp==HL){ap=HL;cp=HL->next;}
}
//依次使n-1个人出列
for(i=1;i<n;i++)
//顺序查找出待出列的人，即为循环结束后cp所指向的结点
for(int j=1;j<m;j++)
{
ap=cp;
cp=cp->next;
if(cp==HL){ap=HL;cp=HL->next;}
}
//输出cp结点的值，即出列的人
cout<<cp->data<<" ";
//从单链表中删除结点的后继结点
cp=ap->next;
//若cp指向了表头附加结点，则后移ap和cp指针
if(cp==HL){ap=HL;cp=HL->next;}
}
//使最后一个人出列
cout<<HL->next->data<<endl;
//删除表头结点和表头附加结点
delete HL->next;
delete HL;
}

Answer 3

/*计算机071 冯**编写的约瑟夫环
单项循环链表实现 原创程序
在结构体中定义了一个序号，使得空间变大，但是程序简单易懂
*/

#include <stdio.h>
#include <malloc.h>
struct node
{
int num;//为方便表达，每个节点拥有一个序号
int password;//密码
struct node *next;
};
node * creatlist(int people)//构造链表
{
int i=1;//序号
int _password;
node *r,*s;
node *L=(node *)malloc(sizeof(node));//创造头结点
r=L;
while(i<=people)
{
printf("请输入第%d个人的密码：",i);
scanf("%d",&_password);
s=(node *)malloc(sizeof(node));
s->num=i;
s->password=_password;
r->next=s;
r=s;
i++;
}
r->next=L;//循环链表
return L;
}

void getoutseq(node *L,int firstp)//计算出列顺序并输出的函数
{
int _password=firstp;
node *p=L;
node *r=L;//r为p的前驱节点
int i=1;
while(L->next!=L)//当L为非空表时一直循环，空表表示所有人已经出列，则退出循环
{
while (i<=_password)//根据密码移动指针
{
if (p->next!=L)//当p的下一个节点非头结点，直接向下移
{
r=p;//p移动前先备份
p=p->next;
}
else//当p的下一个节点是头节点，则令p指向一号节点
{
r=L;
p=L->next;
}
i++;
}
printf("%d号出列\n",p->num);
_password=p->password;//获取节点中的密码
r->next=p->next;//删除并释放p
free(p);
i=1;
p=r;
}
printf("结束!\n");
}
/*
void print(node *L)//该函数用于打印每个节点的信息，方便测试
{
node *p=L->next;
while(p!=L)
{
printf("序号%d密码%d\n",p->num,p->password);
p=p->next;
}

}
*/
int main()
{
node *list;
int people;
int firstp;
printf("请输入人数：");
scanf("%d",&people);
putchar('\n');
printf("请输入初始密码：");
scanf("%d",&firstp);
putchar('\n');
list=creatlist(people);
/* print(list); //该语句用于测试
*/
getoutseq(list,firstp);
printf("按确定键退出。。。");
getchar();
getchar();
return 0;
}

Answer 4

我刚做啊!!!!!!!!!!

#include<stdio.h>
#include<malloc.h>
typedef struct node
{
int date;
int number;
struct node *next;
}ListNode;
ListNode *createlist(int n,int a[])
{
int j;
ListNode *head=(ListNode *)malloc(sizeof(ListNode));
ListNode *s,*r=head;
for(j=1;j<=n;j++)
{
s=(ListNode *)malloc(sizeof(ListNode));
s->date=a[j];
s->number=j;
r->next=s;
r=s;
}
r->next=head->next;
free(head);
return r;
}
void getnode(ListNode *head)
{
int m,k,i;
ListNode *p,*r;
p=head;
printf("输入上限值的初值 ：");
scanf("%d",&m);
printf("出列顺序 ：");
if(m>0)
{
while(p->next!=p)
{
for(k=1;k<m;k++)
p=p->next;
printf("%d ",p->next->number);
m=p->next->date;
r=p->next;
p->next=r->next;
free(r);
}
printf("%d",p->number);
free(p);
printf("\n");
}
}
void main()
{
ListNode *ha;
int a[100],n,i;
printf("输入人数 ：");
scanf("%d",&n);
printf("输入密码 ：");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
ha=createlist(n,a);
getnode(ha);
printf("\n");
}

Answer 5

我用的双向循环链表写的 因为这样比较容易解决一些特殊情况
随机数的上线我设置的是小于起始时的人数 大了也没有什么意义 无非多转几圈 反而不好验证
以前就打算写这个程序 一直没时间
这段时间正好复习一下数据结构
顺便写一些这方面的程序

#include"stdio.h"
#include"windows.h"
#include"malloc.h"
#include"time.h"
#define N 10
typedef struct node
{
int num ;
int sec ;
struct node *pre;
struct node *next;
}body;

void Initiate(body *x);
void Delect(int x,body *head);

void main()
{
int m;
body *first;
first=(body *)malloc(sizeof(body));
first->next=first;
first->pre=first;
Initiate(first);
m=rand()%(N-1);
m=m+1;
printf("\n任意数m=%d\n",m);
Delect(m,first);
}

void Initiate(body *head)
{
int xx[N],yy[N];
int i;
body *p,*q;
for(i=0;i<N;i++) yy[i]=i+1;
srand( time(NULL) );
for(i=0;i<N;i++) xx[i]=yy[rand()%N];
head->num=yy[0];
head->sec=xx[0];
for(i=1;i<N;i++)
{
p=head;
q=(body *)malloc(sizeof(body));
q->num=yy[i];
q->sec=xx[i];
while(p->next!=head) p=p->next;
p->next=q;
q->pre=p;
q->next=head;
head->pre=q;
}
printf("序号:");
for(i=0;i<N;i++) printf("%2d ",i+1);
printf("\n密码:");
for(i=0;i<N;i++) printf("%2d ",xx[i]);
}

void Delect(int x,body *head)
{
body *p;
p=head;
int i=1,sec;
while(i<x && p->next!=p) {p=p->next;i++;}
if(p->next!=p)
{
sec=p->sec;
printf("序号: %2d 密码: %2d \n",p->num,p->sec);
p=p->pre;
p->next=p->next->next;
p->next->pre=p;
head=p->next;
Delect(sec,head);
}
else
{
printf("序号: %2d 密码: %2d \n",p->num,p->sec);
printf("\n问题结束!\n");
}
}