PTA基础编程题目集 7-28 猴子选大王（C语言实现）

摘要：本文是经典的约瑟夫环问题（猴子选大王）的 C 语言实现。N 只猴子围成一圈，从 1 号开始依次报数，每轮报到 3 的猴子退出，最后剩下的猴子当选猴王。文章包含题目描述、输入输出格式、样例及完整的 C 代码实现。

题目描述

一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N 号。从第 1 号开始报数，每轮从 1 报到 3，凡报到 3 的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

#mermaid-svg-uYw8BgoVyj5VdmLj{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-uYw8BgoVyj5VdmLj .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-uYw8BgoVyj5VdmLj .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-uYw8BgoVyj5VdmLj .error-icon{fill:#552222;}#mermaid-svg-uYw8BgoVyj5VdmLj .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-uYw8BgoVyj5VdmLj .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-uYw8BgoVyj5VdmLj .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-uYw8BgoVyj5VdmLj .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-uYw8BgoVyj5VdmLj .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-uYw8BgoVyj5VdmLj .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-uYw8BgoVyj5VdmLj .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-uYw8BgoVyj5VdmLj .marker{fill:#333333;stroke:#333333;}#mermaid-svg-uYw8BgoVyj5VdmLj .marker.cross{stroke:#333333;}#mermaid-svg-uYw8BgoVyj5VdmLj svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-uYw8BgoVyj5VdmLj p{margin:0;}#mermaid-svg-uYw8BgoVyj5VdmLj .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-uYw8BgoVyj5VdmLj .cluster-label text{fill:#333;}#mermaid-svg-uYw8BgoVyj5VdmLj .cluster-label span{color:#333;}#mermaid-svg-uYw8BgoVyj5VdmLj .cluster-label span p{background-color:transparent;}#mermaid-svg-uYw8BgoVyj5VdmLj .label text,#mermaid-svg-uYw8BgoVyj5VdmLj span{fill:#333;color:#333;}#mermaid-svg-uYw8BgoVyj5VdmLj .node rect,#mermaid-svg-uYw8BgoVyj5VdmLj .node circle,#mermaid-svg-uYw8BgoVyj5VdmLj .node ellipse,#mermaid-svg-uYw8BgoVyj5VdmLj .node polygon,#mermaid-svg-uYw8BgoVyj5VdmLj .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-uYw8BgoVyj5VdmLj .rough-node .label text,#mermaid-svg-uYw8BgoVyj5VdmLj .node .label text,#mermaid-svg-uYw8BgoVyj5VdmLj .image-shape .label,#mermaid-svg-uYw8BgoVyj5VdmLj .icon-shape .label{text-anchor:middle;}#mermaid-svg-uYw8BgoVyj5VdmLj .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-uYw8BgoVyj5VdmLj .rough-node .label,#mermaid-svg-uYw8BgoVyj5VdmLj .node .label,#mermaid-svg-uYw8BgoVyj5VdmLj .image-shape .label,#mermaid-svg-uYw8BgoVyj5VdmLj .icon-shape .label{text-align:center;}#mermaid-svg-uYw8BgoVyj5VdmLj .node.clickable{cursor:pointer;}#mermaid-svg-uYw8BgoVyj5VdmLj .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-uYw8BgoVyj5VdmLj .arrowheadPath{fill:#333333;}#mermaid-svg-uYw8BgoVyj5VdmLj .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-uYw8BgoVyj5VdmLj .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-uYw8BgoVyj5VdmLj .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-uYw8BgoVyj5VdmLj .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-uYw8BgoVyj5VdmLj .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-uYw8BgoVyj5VdmLj .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-uYw8BgoVyj5VdmLj .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-uYw8BgoVyj5VdmLj .cluster text{fill:#333;}#mermaid-svg-uYw8BgoVyj5VdmLj .cluster span{color:#333;}#mermaid-svg-uYw8BgoVyj5VdmLj div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-uYw8BgoVyj5VdmLj .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-uYw8BgoVyj5VdmLj rect.text{fill:none;stroke-width:0;}#mermaid-svg-uYw8BgoVyj5VdmLj .icon-shape,#mermaid-svg-uYw8BgoVyj5VdmLj .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-uYw8BgoVyj5VdmLj .icon-shape p,#mermaid-svg-uYw8BgoVyj5VdmLj .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-uYw8BgoVyj5VdmLj .icon-shape .label rect,#mermaid-svg-uYw8BgoVyj5VdmLj .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-uYw8BgoVyj5VdmLj .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-uYw8BgoVyj5VdmLj .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-uYw8BgoVyj5VdmLj :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

是

是

否

否

否

输入 N 只猴子

初始化数组编号 1~N

设置 count=N, pos=0, num=0

count > 1?

monkeys[pos] != 0?

num = num + 1

num == 3?

monkeys[pos] = 0, count–, num=0

pos = (pos+1) % N

遍历数组找到剩余猴子编号并输出

输入格式：

输入在一行中给一个正整数 N（≤ 1000）。

输出格式：

在一行中输出当选猴王的编号。

输入样例：

11

输出样例：

7

代码部分实现

#include <stdio.h> // 引入标准输入输出头文件

int main() {
int n; // 猴子的总数
scanf("%d", &n); // 读入猴子总数

int monkeys[1001]; // 定义数组存储猴子编号，0表示已退出
// 初始化猴子编号为1~n
for (int i = 0; i < n; i++) {
monkeys[i] = i + 1;
}

int count = n; // 剩余未退出的猴子数量
int pos = 0; // 当前遍历到的位置
int num = 0; // 当前报数

// 当剩余猴子数量大于1时，继续淘汰
while (count > 1) {
if (monkeys[pos] != 0) { // 如果当前位置的猴子未被淘汰
num++; // 报数加1
if (num == 3) { // 报到3时，该猴子退出
monkeys[pos] = 0; // 将该位置标记为0（已退出）
count—; // 剩余猴子数量减1
num = 0; // 重置报数，重新开始
}
}
pos = (pos + 1) % n; // 移动到下一个位置，形成循环
}

// 找到最后剩下的那只猴子并输出其编号
for (int i = 0; i < n; i++) {
if (monkeys[i] != 0) {
printf("%d\\n", monkeys[i]);
break;
}
}

return 0; // 程序正常退出
}