猴子选大王课程设计模块设计

F. 猴子选大王程序设计

这是一个约瑟夫环的问题，这里有一个写好的程序，功能能实现，但是如果你想把它写成函数就自己去改吧，应该很简单，这里我就不修改了。 #include<iostream> //定义结构体 typedef struct Joseph { int date; struct Joseph *next; struct Joseph *forie; }JOS; void main() { JOS *p,*head,*tail;//结构体指针，用来对结构体进行操作 int num,count,i; p = new JOS; head = p; tail = p; //约瑟夫环内有多少节点 cout<<"输入循环总数："; cin>>num; cout<<"输入循环跳转的个数："; cin>>count; //建立约瑟夫还 cout<<"请输入数据："; cin>>p->date; p->next = head; cout<<endl; for(i=1;i<num;i++) { p = new JOS; cout<<"请输入数据:"; cin>>p->date; p->next=head; p->forie = tail; tail->next = p; tail = p; cout<<endl; }//建立结束 //开始循环，数到count个数，就删除，然后继续数 head->forie=p; p=head; while(p->next!=p) { for(i=1;i<count;i++) p=p->next; cout<<"删除的数是："<<p->date<<endl; p->forie->next = p->next; p->next->forie = p->forie; p=p->next; } cout<<"最后剩余的数是："<<p->date; }

麻烦采纳，谢谢!

G. 数据结构课程设计——猴子选大王问题，我有程序，帮我解释下

#include <stdio.h>
#include <stdlib.h>
#define n 19
#define m 4

typedef struct monkey
{
int num;
struct monkey *next;
} Monkey,*LINK;

void main()
{
LINK p,head,p2;
int i;
head=p=p2=(LINK)malloc(sizeof(Monkey));//三个指针指向同一块内存

for(i=1;i<n;i++)
{
p=(LINK)malloc(sizeof(Monkey));
p2->next=p;
p2=p;
}

p2->next=head;//把链表的首尾相连
p=head;//p指向了第一个结点

printf("对猴子进行编号！\n");
for(i=1;i<=n;i++)
{
p->num=i;//从第一个结点到最后一个结点依次给猴子编号
printf("%d号猴子：%d\n",p->num,p->num);
p=p->next;
}//循环结束，p指向了最后一个结点

i=0;
p=head;//再把p指向第一个结点

while(1)
{
i++;
printf("%d号猴子报：%d\n",p->num,i);
if(p->next==p)
break;//此为while循环的出口

if(i==m)//if语句中是删除结点的过程
{
i=0;
printf("%d号猴被淘汰\n",p->num);
printf("\n");
p2->next=p->next;//在此删除结点p
p=p2->next;//p指向它的下一个结点
continue;
}
else
{
if(i==m-1)
p2=p;//保存将要退出结点的前一个结点（存到p2中）
p=p->next;
}
}

printf("胜出:%d",p->num);//最后剩下的结点就是获胜的结点

}

这个程序其实就是形成了一个有19个结点的循环链表，当碰到m的时候，用这两句话p2->next=head;p=head删除当前的结点，然后再继续判断。
还有不明白的地方可以问我！

H. 猴子选大王的课程实验报告

任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：
输入数据：输入m,n m,n 为整数，n<m
输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能

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

typedef struct monkey
{
int num;
struct monkey *next;
} Monkey,*LINK;

/*创建循环链表，容纳M个猴子。返回指向链表头结点的指针*/
LINK createList(int M)
{ LINK p,head1,p2;
int i;
head1=p=p2=(LINK)malloc(sizeof(Monkey));
for(i=1;i<M;i++)
{
p=(LINK)malloc(sizeof(Monkey));
p2->next=p;
p2=p;
}
p2->next=head1;
p=head1;
printf("对猴子进行编号！\n");
for(i=1;i<=M;i++)
{
p->num=i;
printf("%d号猴子：%d\n",p->num,p->num);
p=p->next;
}
return head1;
}

/*形成循环链表*/

/*从headP指向的循环链表中选大王，数到N的猴子淘汰，将依次淘汰出来的猴子插入到headPtr2指向的链表中*/
void selectKing(LINK head,int N,int M)/*N>=2*/
{
LINK p,p2,head2=NULL;
int i;
i=0;
p=head;//p指向第一个结点

while(1)
{
i++;
printf("%d号猴子报：%d\n",p->num,i);
if(p->next==p)
break;//此为while循环的出口

if(i==N)//if语句中是删除结点的过程
{
i=0;
printf("%d号猴被淘汰\n",p->num);
printf("\n");
p2->next=p->next;//在此删除结点p
p=p2->next;//p指向它的下一个结点
continue;
}
else
{
if(i==N-1)
p2=p;//保存将要退出结点的前一个结点（存到p2中）
p=p->next;

}

}
}

int main()
{
LINK head=NULL;
int M,N;

printf("输入猴子数量:");
scanf("%d",&M); /*猴子个数*/
printf("输入选定的一个小于猴子总数的数:");
scanf("%d",&N); /*count＝3，表示每次数到3的猴子出局*/

head=createList(M);/*创建循环链表*/

selectKing(head,N,M);/*选大王*/
return 0;
}

I. 数据结构课程设计题目：猴子选大王问题

我使用了另一种方法，不需要构建环形链表也可以，只需要用一个数组标记已离开的猴子即可，相对比较简单。这个程序输出猴子离开的顺序，最后输出的即为大王。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

int main()
{
int m,n;
int *not_in;
int pos;
int i;
int j;

printf("m n = ");
scanf("%d%d", &m, &n);
assert(m > 0);
assert(n > 0);
not_in = (int *)malloc(sizeof(int)*(m + 1));
memset(not_in, 0, sizeof(int)*(m + 1));

pos = m;
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
{
do
{
pos++;
if (pos == m + 1)
pos = 1;
}
while (not_in[pos]);
}
printf("%d ", pos);
not_in[pos] = 1;
}
printf("\n");

return 0;
}