[请教]猴子选大王 - 编程论坛

#2

herbert_19872007-06-23 15:18

又是约瑟夫环问题,用循环链表,然后逐个删除.

#3

冰天雪2007-06-23 15:34

算法还没弄懂

#4

herry2007-06-23 15:46

约瑟夫环是什么啊？好像还没有听说过哦？

#5

herry2007-06-23 15:52

去搜了一下，终于知道怎么回事了，谢谢了！！！

#6

herbert_19872007-06-23 15:53

我这里有一个程序(不过不是很完善D):
///////////////////////////头文件////////////////
typedef struct member
{
int ID;//某个人的序号
int cipher;//密码
member *next;//下一个

}Person;

typedef struct
{
Person *head;//链表头
Person *tail;//链表尾
int lenth;//链表长
}List;

///////////// 算法部分 ( .cpp 文件)////////////
//添加链表元素
void AddMember(List &list,int ID,int cipher)
{
Person *per = (Person *)malloc(sizeof(Person));
per->ID = ID;
per->cipher = cipher;

//当链表为空时
if(list.lenth == 0)
{
list.head = per;
list.tail = per;
per->next = list.head;
}
else //当链表不空时
{
per->next = list.head;
list.tail->next = per;
list.tail = per;
}
list.lenth++;
}

//用来记录输出结果的数组初始化
void InitArray(int lenth, int **array)
{
*array = (int *)malloc(lenth * sizeof(int));
}

//处理链表（排序）
void DoList(List list, int *array)
{
int N = list.lenth;//用于循环
int arrayCount = 0;//输出数组的下标
int cip;
Person *person = list.head;
cip = person->cipher;
while(N > 0)
{
for(int i = 1; i < cip; i++)//找出下一个出列的人
person = person->next;

Person *p = person->next;

cip = p->cipher;
array[arrayCount] = p->ID;
arrayCount++;

person->next = p->next;
free(p);
N--;
}

}

//////////////main 函数部分(.cpp 文件)/////////////
#include <iostream.h>
#include <malloc.h>
#include <stdlib.h>

#include "test2.h"
#include "algo2.cpp"

void main()
{
int max, n;
int cipher;

List list;
char loop;//循环的标志

do
{
cout<<"*************** 约瑟夫环问题 ****************"<<endl<<endl;

do
{
cout<<"输入密码的最大值: ";
cin>>max;
cout<<endl<<"输入人数: ";
cin>>n;

if(max <= 0 || n <= 0)
cout<<"你所输入的数不能小于 1，请重新输入"<<endl;
}
while(max <= 0 || n <= 0);
list.lenth = 0;

for(int i = 1; i <= n; i++)
{
cout<<"输入第 "<<i<<" 个人的密码（必须大于0）: ";
do
{
cin>>cipher;
if(cipher > max)
cout<<"你所输入的数大于密码的最大值，请从新输入："<<endl;
if(cipher <= 0)
cout<<"你所输入的数小于 1，请从新输入："<<endl;
}
while(cipher > max || cipher <= 0);

AddMember(list, i, cipher);//添加成员
}

int *array;
InitArray(n, &array);//数组初始化

DoList(list, array);//按顺序删除成员

cout<<endl<<"************* 出列顺序为 ***************"<<endl;
for(i = 1; i <= n; i++)//输出出列顺序
{
if(i%20 == 0)
cout<<endl;
cout<<array[i-1]<<" ";
}

cout<<endl<<"是否要继续？（Y / N)"<<endl;
cin>>loop;
system("cls");//清屏幕
}
while(loop == 'Y' || loop == 'y');
}

#7

zkkpkk2007-06-23 21:40

约瑟夫环，本来是说将异教徒丢下海的，后来变种为猫吃老鼠，小孩报数，现在连猴子也出来了

#8

herbert_19872007-06-23 21:48

以下是引用zkkpkk在2007-6-23 21:40:09的发言：
约瑟夫环，本来是说将异教徒丢下海的，后来变种为猫吃老鼠，小孩报数，现在连猴子也出来了

呵呵, 挺有趣的!^_^

#9

滨海2007-06-25 23:13

约瑟夫环问题,

你看看吧

#include <iostream>
using namespace std;
void main()
{
int A[9],s,m; //相关参数的定义和输入；
cin>>s>>m;
int f,k,t,count=0;
if(m==0)
{
cerr<<"输入的参数无效！"<<endl;
return;
}
for( int i=0;i<9;i++)A[i]=i+1; //初始化数组
f=s-1; //起始报数者；
for(k=9;k>=1;k--) //循环出局；
{
if(f==k-1)f=0;
f=(f+m-1)%k;
if(f!=k-1)
{
t=A[f];
for(int j=f;j<k-1;j++)A[j]=A[j+1]; //将淘汰者依次往后移；
A[k-1]=t;
}
count++; //统计出局的次序；
cout<<"第"<<count<<"个出局："<<A[k-1]<<endl;
}
cout<<"游戏结束！"<<endl;
}

#10

仇忍甫2010-11-26 10:58

#include <stdio.h>
#define MaxSize 50
void jose(int n,int m)
{
int mon[MaxSize];     /*存放n个猴子的编号*/
int i,d,count;
for(i=0;i<n;i++)      /*设置猴子的编号*/
mon[i]=i+1;
printf("出队前:");     /*输出出列前的编号*/
for(i=0;i<n;i++)
printf("%d",mon[i]);
printf("\n");
printf("出队后:");
count=0;            /*记录推出圈外的猴子个数*/
i=-1;               /*从0号位置的猴子开始计数*/
while(count<n)
{
d=0;
while(d<m)               /*累计m个猴子，相当于猴子报数*/
{
i=(i+1)%n;
if(mon[i]!=0)
d++;
}
printf("%d",mon[i]);    /*猴子出列*/
mon[i]=0;
count++;               /*出列数增1*/
}
printf("\n");
}
void main()
{
int m,n;
printf("输入猴子个数n,m:");
scanf("%d,%d",&n,&m);
jose(n,m);
}