标题:[请教]猴子选大王
只看楼主
herry
Rank: 1
等 级:新手上路
帖 子:43
专家分:0
注 册:2007-5-26
 问题点数:0 回复次数:9 
[请教]猴子选大王
猴子选大王
  一群猴子都有编号,编号是1,2,3 ...m ,这群猴子(m个)按照1——m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,然后继续从1开始,这样依次下来,直到圈中只剩下一只猴子,则该猴子为大王。
搜索更多相关主题的帖子: 大王 猴子 
2007-06-23 15:13
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
得分:0 
又是约瑟夫环问题,用循环链表,然后逐个删除.

人生重要的不是所站的位置,而是所朝的方向
2007-06-23 15:18
冰天雪
Rank: 1
等 级:新手上路
威 望:1
帖 子:331
专家分:0
注 册:2007-2-27
得分:0 
算法还没弄懂
2007-06-23 15:34
herry
Rank: 1
等 级:新手上路
帖 子:43
专家分:0
注 册:2007-5-26
得分:0 
约瑟夫环是什么啊?好像还没有听说过哦?
2007-06-23 15:46
herry
Rank: 1
等 级:新手上路
帖 子:43
专家分:0
注 册:2007-5-26
得分:0 
去搜了一下,终于知道怎么回事了,谢谢了!!!
2007-06-23 15:52
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
得分:0 

我这里有一个程序(不过不是很完善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');
}


人生重要的不是所站的位置,而是所朝的方向
2007-06-23 15:53
zkkpkk
Rank: 2
等 级:论坛游民
威 望:5
帖 子:489
专家分:28
注 册:2006-6-17
得分:0 
约瑟夫环,本来是说将异教徒丢下海的,后来变种为猫吃老鼠,小孩报数,现在连猴子也出来了

Viva,espana!
2007-06-23 21:40
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
得分:0 
以下是引用zkkpkk在2007-6-23 21:40:09的发言:
约瑟夫环,本来是说将异教徒丢下海的,后来变种为猫吃老鼠,小孩报数,现在连猴子也出来了

呵呵, 挺有趣的!^_^


人生重要的不是所站的位置,而是所朝的方向
2007-06-23 21:48
滨海
Rank: 1
等 级:新手上路
帖 子:38
专家分:0
注 册:2007-6-3
得分:0 
约瑟夫环问题,

你看看吧

#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;
}

让暴风雨来的更猛烈些吧!!
2007-06-25 23:13
仇忍甫
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2010-11-19
得分:0 
#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);
}
2010-11-26 10:58



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-149724-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.419825 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved