可用分押宝游戏火热进行中...	专题改版：Java Web 专题

约瑟夫环问题如果写源程序太麻烦的话给个大到思路就行了

楼主rockpirate（海雷丁）2003-08-03 01:28:30 在 C/C++ / C语言提问

约瑟夫环问题
描述：编号为1、2……、n的n个人按顺时针防线围坐一圈，每个人持有密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向的下一个人开始重新从1报数，直至所有的人全部出列为止。试设计一个程序求出出列的顺序。
基本要求：按照出列的顺序打印出各人的编号。

测试数据： m的初值为20；共7人密码各为：3，1，7，2，4，8，4 （正确结果为 6，1，4，7，2，3，5）

实现提示：运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。设n<＝30

问题点数：100、回复次数：11Top

1 楼soyan（埋伏十年）回复于 2003-08-03 02:01:49 得分 0

帮你upTop

2 楼chengsion（）回复于 2003-08-03 08:15:18 得分 0

使用一数组保存各人的密码，数组的下标+1为各人的序号，初始读入报数密码n,报数时循环计数(取数组长度的模)，到一个人out时，打印序号，并读出保存在数组元素里的密码，重新计数，再out...,直至只剩一人。Top

3 楼oneonone（）回复于 2003-08-03 09:01:50 得分 40

#include <iostream>
using namespace std;

bool main()
{
int num;
int *password, *people;
int m;//初始值
int l;
cout<<"输入总人数:";
cin>>num;
if(!(password = new int[num])) return false;
if(!(people = new int[num])) return false;
for(int i = 0;i<num;i++)
{
cout<<endl<<"输入"<<i+1<<"号人物的密码:";
cin>>password[i];
people[i] = i+1;
}
cout<<"输入初值:";
cin>>m; cout<<endl;

for(i = 0; ;i++)//计算第一个出队的人
{
m--;
if (m == 0) break;
if(i == num-1) i = -1;
}
int temp = password[i];
cout<<endl << people[i]<<"出队"<<endl;
for(l = i;l<=num;l++)//移动剩下的元素
{
people[l]=people[l+1];
password[l] = password[l+1];
}
num--;
for(;num;)//找下一个出队的人
{
//从下一个人开始数
//if (i == num) i = 0;
for(m = temp; ; i++)
{
m--;
if (m == 0) break;//数到此人,出队
if(i == num-1) i = -1;//转了一圈,从队头开始

}
temp = password[i];
cout<< people[i] <<"出队" <<endl;
num--;
for(l = i;l<=num;l++)
{
people[l]=people[l+1];
password[l] = password[l+1];
}
if(i == num) i = 0;//转了一圈,从队头开始

}
return true;

}
Top

4 楼oneonone（）回复于 2003-08-03 09:02:15 得分 0

累死了,你这不是作业题吧?Top

5 楼stkane（左手无名指）回复于 2003-08-03 10:14:04 得分 0

用环来实现比较好
出队的便从环中去掉Top

6 楼oneonone（）回复于 2003-08-03 10:32:49 得分 0

//上面的程序太复杂了而且忘了释放内存
//应该在最后加上两句
//delete []password;delete []number;
//下面这个程序更好一些当初写上面那个程序的时候忘了你这个问题本来就是用链表实现的
//下面这个用了链表，清晰多了，大体意思就是这个，我没时间调了你自己看看吧。
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct person
{
int password;
int number;
person *next;
};
int main(int argc, char *argv[])
{
int num,m;
person *p,*q,*head;
int i,j,temp;
cout<<"人数：";
cin>> num;
cout << endl << "初值：";
cin >> m;
for(i = 1;i<=num;i++)
{
cout<<"第"<<i<<"个人的密码:";
q = new person;
if(i==1){ p = head = q; q->next = q;}
cin>>q->password;
q->next = head;
p->next = q;
p = q;
}
p = head;i= num-1;
for(j= m;j>1;j--) p= p->next;
q= p; temp = q->password;p = p->next;cout<< q->number<<"出队"<<endl;delete q;
do
{
for(j = temp;j>1;j--) p= p->next;
q=p;p=p->next;temp= q->password;cout<<q->number<<"出队"<<endl;delete q;
i--;

}while(i>0);

system("PAUSE");
return 0;
}
Top

7 楼Dragon132（飞龙在天）回复于 2003-08-03 15:58:32 得分 20

我也做出来啦，我认为链表比较好用

#include <stdio.h>
#include <stdlib.h>

struct person
{
int num;
int secret;
struct person *next;
}

main()
{
struct person *head,*p,*q;
int a[8]={0,3,1,7,2,4,8,4 };
int i,j=0,m=13;
head=(struct person *)malloc(sizeof(struct person));
p=head;
for(i=1;i<8;i++)
{
q=(struct person *)malloc(sizeof(struct person));
q->num=i;
q->secret=a[i];
p->next=q;
p=q;
}
p->next=head->next;
head->next=NULL;
q=head;
i=0;
while(j<7)
{
if(i==m-1)
{
q->next=p->next;
p->next=p->next->next;
q=q->next;
q->next=NULL;
i=0;
m=q->secret;
j++;
}
else
{
i++;
p=p->next;
}
}
q->next=NULL;
q=head->next;
for(i=1;i<=7;i++)
{
printf("%3d",q->num);
q=q->next;
}
q=head;
while(q)
{
p=q;
q=p->next;
free(p);
}
printf("\nOK\n");
}Top

8 楼crcr（游侠）回复于 2003-08-03 17:00:20 得分 20

#include<iostream.h>
void main()
{
const int num=10;　　　　　　　　// 总人数
int interval; //表示第几个人出圈
int a[num];
for(int i=0;i<num;i++) //人数的编号
a[i]=i+1;
cout<<"Please input the interval:";
cin>>interval; //输入间隔数
for(int ii=0;ii<num;ii++) //显示人数
cout<<a[ii]<<",";
cout<<endl;
int k=1;
int i2=-1;
while(1)
{
for(int j=0;j<interval;)
{
i2=(i2+1)%num;
if(a[i2]!=0)
j++;
}
if(k==num) break;
cout<<a[i2]<<",";
a[i2]=0; //标记已出圈人数为0
k++;
}
cout<<"\nNO."<<a[i2]<<"boy's won.\n";
}Top

9 楼Riemann（）回复于 2003-08-03 17:36:39 得分 20

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

//链表定义
struct cl_node
{
int elem;
int key;
struct cl_node *next;
};

//CreateList 函数用来建立一个长度为n的循环链表,返回的是头节点的前驱节点
struct cl_node *CreateList(int n)
{
int i;
struct cl_node *L,*p,*q;
//创建第一个节点
L = (struct cl_node *)malloc(sizeof(struct cl_node));
if(L == NULL)
{
printf("Fail to alloc memory!\n");
exit(0);
}
L->next = L;
L->elem = 1;
scanf("%d",&(L->key));
p = L;
for(i = 1; i < n; i++)
{
//逐个加入后继节点
q = (struct cl_node *)malloc(sizeof(struct cl_node));
if(q == NULL)
{
printf("Fail to alloc memory!\n");
exit(0);
}
q->next = p->next;
q->elem = p->elem + 1;
scanf("%d",&(q->key));
p->next = q;
p = q;
}
return p;
}

void main()
{
int count,n,m,i;
struct cl_node *p,*q;
printf("Please input the people's number:");
scanf("%d",&n);
//如果n = 1,直接输出,这样可简化程序
if(n == 1)
{
printf("%d\n",n);
exit(1);
}
//否则,输入个人所持密码,建立链表
printf("Please input everyone's password:");
p = CreateList(n);
q = p->next;
//初始化计数器m,开始进行报数操作
printf("The upper limits m is:");
scanf("%d",&m);
count = n;
while(p != q)
{
for(i = 1; i <= m; i++)
{
if(i == m)
{
//输出q->elem以及其出队的顺序,将m值更新为q->key
printf("%3d------%d\n",n-(--count),q->elem);
m = q->key;
//删除出队节点
p->next = q->next;
free(q);
q = p->next;
if(p != q)
i = 0;
else
break;
}
else
{
//否则，指针后移
p = p->next;
q = q->next;
}
}
}
printf("%3d------%d\n",n,p->elem);
getch();
}

Top

10 楼Riemann（）回复于 2003-08-03 17:38:28 得分 0

或者去http://expert.csdn.net/Expert/topic/2059/2059607.xml?temp=.125622看看Top

11 楼rockpirate（海雷丁）回复于 2003-08-03 23:42:05 得分 0

在网上看到的问题

谢谢了Top