主题：请教哪位高手一个关于约瑟夫环问题
liubo19720
[专家分：70] 发布于 2005-04-13 16:57:00
各位高手:
小弟遇到这样一个难题,有点措手不及!!在这里恳请各位好手能帮小弟用C解决一下!
小弟不甚感激!!
Josephus环问题
设编号为1、2、…n的n个人围坐一圈，约定编号为k（1≤k≤n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示：
（1）、由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动。
可以采用数据类型定义：
typedef struct node
{
int number; //每个人的编号
struct node *next; //指向表示下一个人的结点的指针
}lnode
（2）、为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如：int quit[n];n为一个根据实际问题定义的一个足够大的整数。
回复列表 （共9个回复）
沙发
020204063 [专家分：200] 发布于 2005-04-14 19:48:00
兄弟,我来给你做:
#define NULL 0
#define n 100
typedef struct node
{int number;
struct node *next;
}lnode;
lnode *creatlistx()/*创建单链表*/
{int i;
lnode *head,*p,*q;
head=NULL;
p=NULL;
for(i=1;i<=n;i++)
{q=(lnode*)malloc(sizeof(lnode));
q->number=i;
if(head==NULL)head=q;
else p->next=q;
p=q;
}
p->next=head;
return p;
}
void print(lnode *head)/*输出单链表*/
{lnode *p;
p=head;
if(head!=NULL)
do
{printf("%d,%d ",p->number,p->next);
p=p->next;
}while(p!=head);
else printf("This is an empty list!\n");
}
main()/*主函数*/
{lnode *head,*p,*q;
int k,m,i,j,quit[n];
printf("Input k,m:");
scanf("%d,%d\n",&k,&m);/*约定从第k个人数数(1--m)*/
p=creatlistx();
head=p->next;
print(head);
q=p;
p=head;
while(p->number!=k)
p=p->next;
for(i=0;i<n;i++)
{for(j=1;j<m;j++)
{q=p;p=p->next;}
quit[i]=p->number;
q->next=p->next;
free(p);
p=q->next;
}
for(i=0;i<n;i++)
printf("%d ",quit[i]);
}
板凳
liubo19720 [专家分：70] 发布于 2005-04-14 19:51:00
谢谢了!!
十分的感谢!!!
3 楼
奴隶 [专家分：40] 发布于 2005-04-22 23:37:00
这个题目见的也太多了。
4 楼
flyyee [专家分：30] 发布于 2005-05-09 19:21:00
#include <stdio.h>
#include <malloc.h>
#define OK 1
#define ERROR -1
#define OVERFLOW -2
typedef int Status;
typedef struct LNode{//定义结点
int num;
int key;
struct LNode *next;
}LNode,Joseph;
Status Input_Num(Joseph *p,int i){//输入各结点编号
p->num=i;
return OK;
}//Input_Num
Status Input_Key(Joseph *p){//输入各结点密码
printf("请输入第%d个人的密码:",p->num);
scanf("%d",&p->key);
while(!p->num){
printf("输入有误，请重新输入:");
scanf("%d",p->key);
}//while
return OK;
}//Input_Key
Status Print_Num(Joseph *h){//输出号码
printf("%d ",h->num);
return OK;
}//Get_Num
Status Get_Key(Joseph *h,int &Key){//为Key赋值
Key=h->key;
return OK;
}//Get_Key
Joseph *Create_Node(void){//创建新结点
Joseph *p;
do{
p=(Joseph *)malloc(sizeof(Joseph));
}while(!p);
return p;
}//Create_Node
Status Search_Node(Joseph *&p,Joseph *&h,int Key){//查找结点
if(Key==1)
return OK;
else{
int i;
for(i=2;i<=Key;i++){
p=h;//p指向待查结点的前继
h=h->next;
}//for
return OK;
}//else
}//Search_Node
Status Delete_Node(Joseph *p,Joseph *&h){//删除结点
Joseph *q=h;
if(h!=h->next){
h=h->next;
p->next=h;
}
else
p=h=NULL;
free(q);
return OK;
}//Delete_Node
Joseph *CreateList_CL(void){//构造循环链表
Joseph *p,*q,*h;
int i=1,n;
printf("请输入人数：");
scanf("%d",&n);
while(n<=0){//若输入不是正数
printf("输入有误，请重新输入:");
scanf("%d",&n);
}//while
h=q=p=Create_Node();
Input_Num(p,i);Input_Key(p);//创建第一个结点
for(i=2;i<=n;i++){
p=Create_Node();
Input_Num(p,i);
Input_Key(p);
q->next=p;//q指向p的前继
q=p;
}//for
q->next=h;//连接成循环链表
return h;
}//CreateList_CL
Status Joseph_Circle(Joseph *h){
int Key;
Joseph *p=h;
printf("请输入初始密码：");
scanf("%d",&Key);//为Key赋初值
if(Key==1)
while(p->next!=h)
p=p->next;
while(h->next!=h){ //(1)
//当未出列人数多于一人时
//h指向要查找的结点
Search_Node(p,h,Key);//p指向待查结点的前继
Print_Num(h);//打印出列人的编号
Get_Key(h,Key);//换用出列人的密码
Delete_Node(p,h);
}//(1)
Print_Num(h);//打印最后未出列人的编号
Delete_Node(p,h);
return OK;
}//Joseph
void main(){
Joseph_Circle(CreateList_CL());
}//main[color=800080][/color]
5 楼
snapshot [专家分：30] 发布于 2005-05-12 13:24:00
我也补一个:
#include<stdio.h>
#include<malloc.h>
#define SIZE 8
#define LEN sizeof(struct jonse)
struct jonse
{
int code;
struct jonse *next;
};
void main()
{
struct jonse *head,*p,*q;
int num,val,beg,i,k; /*define total num,interval num,begin num*/
q=(struct jonse*)malloc(LEN);/*creat list,as in c++ 'new'*/
head=q;
p=head;
for(i=1;i<=SIZE;i++)
{
q->code=i; /*make mark for every node*/
p->next=q;
p=p->next;
q=(struct jonse*)malloc(LEN);
}
p->next=head; /*creat circle list*/
q=p; /*avoid unoperate some node*/
printf("The circle list is:\n");
for(p=head;p->next!=head;p=p->next)
printf("%d\t",p->code);
printf("%d\n",p->code); /*output the last node*/
printf("please input the begin of count:");
scanf("%d",&beg);
printf("please input the interval of number:");
scanf("%d",&val);
printf("the new list is:\n");
p=head;
for(k=1;k<beg;k++)
{
q=p;
p=p->next;
} /*find the begin num*/
while(p!=p->next) /*deal with list until one node*/
{
for(k=1;k<val;k++)
{
q=p;
p=p->next;
} /*bao shu*/
printf("%d\t",p->code);
q->next=p->next;
free(p);
p=q->next;
}
printf("%d\n",p->code);
free(head);
}
6 楼
misha201 [专家分：0] 发布于 2005-05-13 21:12:00
有没有人会用C＋＋写一个啊
7 楼
zflwy [专家分：0] 发布于 2005-11-18 17:10:00
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct ManNode
{
int Number;
struct ManNode * Next;
int Password;
};
void main()
{
int m;
int NumMan;
struct ManNode * Head;
void DeleteNode(int ManNumber,int number,struct ManNode * head);
struct ManNode * CreateList(int NumOfMan);
printf("请输入参加的人数:\n");
scanf("%d",&NumMan);
Head=CreateList(NumMan);
printf("请输入刚开始任选的人数m:\n");
scanf("%d",&m);
DeleteNode(NumMan,m,Head);
free(Head);
}
struct ManNode *CreateList (int NumOfMan)
{
struct ManNode * head,*ManNode1,*ManNode2;
int Num=1;
head=NULL;
ManNode2=(struct ManNode *)malloc(sizeof(struct ManNode));
printf("请输入用户所持有的密码:");
scanf("%d",&ManNodeP2->Password);
ManNode2->Number=Num;
head=ManNodeP2;
while(Num!=NumOfMan)
{
Num++;
ManNodeP1=(struct ManNode *)malloc(sizeof(struct ManNode));
printf("请输入用户所持有的密码:");
scanf("%d",&ManNodePtr1->Password);
ManNodeP1->Number =Num;
ManNodeP2->Next =ManNodeP1;
ManNodeP2=ManNodeP1;
}
ManNodeP2->Next =head;
printf("输入结束!\n");
return head;
}
void DeleteNode (int ManNumber,int number,struct ManNode * head)
{
int num=1;
struct ManNode *ManNodeP1;
struct ManNode *ManNodeP2;
ManNodeP1=ManNodeP2=head;
while(ManNumber>0)
{
while(num!=number)
{
ManNodeP2=ManNodeP1;
ManNodeP1=ManNodeP1->Next ;
number--;
}
number=ManNodeP1->Password;
printf("出列人的编号:%d\n",ManNodeP1->Number) ;
ManNodeP2->Next =ManNodeP1->Next ;
ManNodeP1=ManNodeP1->Next ;
ManNumber--;
}
printf("\n运行结束!!!\n");
}
8 楼
makilimchen [专家分：0] 发布于 2005-11-30 19:33:00
每个人写的程序运行都有错误啊~5楼错的最少，只有3个。
9 楼
zlkevin [专家分：0] 发布于 2006-11-15 02:46:00
class Demo6 {
final static int pi=5;//有几个数字
final static int D=2;//间隔几个
final static int S=3;//从第几个开始
static int n=1;
public static void main(String[] args)
{
int a[]=new int[pi];
int y=5;
// 检测几个数值是否正确
if(S>(pi-1))
{
System.out.println("你的选择出错了！");
return;
}
// 给数组的几个数赋值
for(int i=0;i<pi;i++)
{
a[i]=i+1;
}
// 定值去除数组中的数字
while(y!=1)
{
if(y==5)
{
for(int i=S;i<pi;i++)
{
if(a[i]!=0)
{
if(n!=D)
{
n++;
}
else
{
a[i]=0;
n=1;
}
}
}
}
for(int i=0;i<pi;i++)
{
if(a[i]!=0)
{
if(n!=D)
{
n++;
}
else
{
a[i]=0;
n=1;
}
}
}
// 检测有数组中的数值是多少
// for(int i=0;i<pi;i++)
// {
// System.out.println("a["+i+"]="+a[i]);
// }
y=0;
for(int i=0;i<pi;i++)
{
if(a[i]!=0)
{
y++;
}
}
// 检测y的值是多少
// System.out.println("y的值是"+y);
// System.out.println("");
}
// 显示结果
for(int i=0;i<pi;i++)
{
if(a[i]!=0)
{
System.out.println("最后剩下的一个数是"+a[i]);
}
}
}
}
我来回复
您所在位置：