声明：图片及内容基于https://www.bilibili.com/video/av78358478

题目概述

 

循环链表实现

#include
using namespace std;
typedef struct node{
int data;
struct node *next;
}Node,*Point; //typedef给链表起小名
int main(){
int n,m; //n只猴子数到m
int count=0; //answer的数组下标
int answer[301]; //储存答案
while(1){ //保持循环
cin>>n>>m;
if(n==0||m==0) break; //循环终止
else{
Point head,tail,p,q; //注意用小名声明结构体指针不要加 * （初始化头节点）
head=(Point)malloc(sizeof(Node)); //开辟哨兵节点
head->next=NULL;
tail=head; //尾指针指向哨兵节点
for(int i=0;i p=(Point)malloc(sizeof(Node)); //data是猴子的序号从1到n
p->data=i+1;
tail->next=p;
p->next=head->next; //循环链表
tail=p; //tail始终指向最后一个元素
}
p=head->next; //p指向第一个数据结点（非哨兵）
q=tail; //q是p的前驱
int i=1; //i记录数到几了
while(q!=p){ //只要前后指针没相遇即链表有两个以上节点
if(i==m){
q->next=p->next;
free(p); //释放空间
p=q->next;
i=1; //重新开始数
}else{
q=p;
p=p->next;
i++;
}
}
answer[count++]=p->data;
free(p); //别忘了把最后一个空间释放
head->next=NULL; //每次让头节点next为NULL是好习惯
}
}
for(int j=0;j cout< }
}

数组标志位实现

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
int main() {
int n, m;
int number; //number=n
int count=1; //报数
int i, pos; //pos是数组下标
int ans[301], answer = 0;
while (~scanf("%d%d", &n, &m)) {
if (n == 0 || m == 0) break;
number = n;
int monkey[301] = { 0 };
for ( i = 0; i monkey[i] = i + 1; //monkey数组存的是猴子标号
}
pos = 0;
while (number > 1) { //存活多余一只猴子
if (monkey[pos] > 0) { //如果猴子活着
if (count != m) { //报数未到
count++;
pos = (pos + 1) % n;
}
else {
monkey[pos] = 0; //杀死
count = 1; //重新报数
number--; //猴子存活数减一
pos = (pos + 1) % n;
}
}
else {
pos = (pos + 1) % n;
}
}
for ( i = 0; i if (monkey[i] > 0) {
//printf("%d
", monkey[i]);
ans[answer++] = monkey[i];
}
}
}
for (i = 0; i cout < }
return 0;
}

数组模拟链表

#include
using namespace std;
int main() {
int n, m;
int ans[301], answer = 0;
while (1) {
cin >> n >> m;
if (n == 0 || m == 0) break;
int count = 1; //报数
int pos = 0; //数组前置下标
int prior = n - 1; //数组后置下标
int monkey[301] = { 0 };
for (int i = 0; i monkey[i] = (i + 1) % n; //是最后一个数据下标为0，实现模拟
} //循环链表
int number = n;
while (number > 1) {
if (count != m) { //如果报数没到m，pos和prior都向后移动
prior = pos;
pos = monkey[pos];//monkey[pos]存有pos的下一个位置
count++; //报数加一
}
else {
number--; //杀死
count = 1; //重新报数
monkey[prior] = monkey[pos]; //prior的下一位置变为原来pos的下一位置，跳过pos
pos = monkey[pos]; //pos后移一位
}
}
ans[answer++] = monkey[pos]+1; //注意加一
}
for (int i = 0; i cout < }
return 0;
}