Question

数据结构顺序表写猴子选大王怎么写啊？

如果你想粘贴下面这个，那你就不用了，这种写法是错误的！
n只猴子要选大王，选举方法是：所有猴子按1，2，…，n编号围坐一圈，从第1号开始按1，2，…，m报数，凡报到m号的退出圈外，如此循环报数，直到圈内剩下一只猴子时，这只猴子就是大王。
请你理解这个提的意思，不是说踢出去一个人就又从最开始那一个来开始报数！而是从踢掉的人的下一个人开始从1报数！谢谢！
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100

typedef struct Node
{
int data;
struct Node *next;
}*List;

int SequenceList(int num_monkey,int number)
{
int monkey[MAXSIZE];
int out=1;
int num_now=num_monkey;
int i,j;
for(i=0;i<num_monkey+1;i++)
{
monkey[i]=1;
}
for(i=1;i<num_monkey;i++)
{
out=1;
for(j=0;j<number;j++)
{
if(out>num_monkey)
out-=num_monkey;
while(monkey[out]==0)
{
out++;
if(out>num_monkey)
out-=num_monkey;
}
out++;
}
out--;
monkey[out]=0;
printf("猴子%d淘汰\n",out);
}
while(monkey[out]==0)
{
out++;
if(out>num_monkey)
out-=num_monkey;
}
return out;
}

void main()
{
int m,n,king;
printf("请输入猴子的个数：");
scanf("%d",&n);
printf("请输入要报的数：");
scanf("%d",&m);
king=SequenceList(n,m);
printf("%d号猴子是大王\n",king);
}
你打算粘贴这个的话就不用了 谢谢。虽然我知道这个是错的，但是我还是不会写！希望大神帮忙！

Answer 1

#include "stdio.h"
#include "malloc.h"

int SelectKing(int n, int m) {
int i, current, count, *monkey, in = 1, out = 0;
monkey = (int*) malloc (sizeof(int) * (n + 1));
for(i = 1; i <= n; i++) monkey[i] = in;
for(i = 1, current = 1; i < n; i++) {
count = 0;
if(monkey[current] == in) count++;
while(count < m){
current = current % n + 1;
if(monkey[current] == in) count++;
}
monkey[current] = out;
}
for(current = 1; current <= n; current++)
if(monkey[current] == in) break;
return current;
}
void main( ){
int n, m king;
printf("请输入猴子的个数: ");
scanf("%d", &n);
printf("请输入要报的数: ");
scanf("%d", &m);
king = SelectKing(n, m);
printf("%d号猴子是大王\n", king);
}

追问

谢谢 。可以写一下输出每次踢出的猴子的位置的写法吗

追答

空白行不计为一行，单独占一行的 "{" 或 "}" 算一行，则将以上代码在某些地方添加一些行号则可如下表示，前面的数字表示行号，以便你索引。
1 #include "stdio.h"
5 monkey = (int*) malloc (sizeof(int) * (n + 1));
10 while(count < m){
15 }
20 void main( ){
25 scanf("%d", &m);
那么你对程序进行如下修改。
将第3行改为： int SelectKing(int n, int m, int OutList[ ])
在第14~15行之间插入：OutList[i] = current;
将第21行改为：int n, m king, *OutList;
将第26行修改为如下代码：
OutList = (int *) malloc (n * sizeof(int));
king = SelectKing(n, m, OutList);
printf("猴子出列依次为: ");
for(i = 1; i < n; i++) printf("%d\t", OutList[i]);
printf("\n");