当前位置：首页 > news >正文

GESP2023年12月认证C++三级( 第三部分编程题（1、小猫分鱼））

news 2026/4/19 5:37:06

🐱《小猫分鱼大冒险》

一、🏝️ 故事开始：海滩上的鱼山

在阳光灿烂的海边，有刚刚捕获的一大堆鱼 🐟🐟🐟。

突然，来了很多只小猫！🐱🐱🐱

它们决定按规则分鱼：

1、📜 分鱼规则

假设有n只小猫。

每一只小猫轮到时，都要这样做：

第一步：先看鱼堆
把鱼平均分成n份。
第二步：如果多出i条鱼
把多出的i条扔回大海 🌊
第三步：拿走其中一份
剩下的鱼留给下一只小猫。

2、🎯 任务目标

输入：

小猫数量n
每次扔掉的鱼数i

输出：

最少一开始需要多少条鱼，才能让所有小猫都成功分鱼！

3、📘 题目样例

输入：

2 1

表示：

一共有2只小猫
每次都是，多1条鱼扔掉

输出：

4、🧠 为什么答案是 7？

（1）🐱 第一只小猫来啦！

鱼有 7 条：

🐟🐟🐟🐟🐟🐟🐟

分给 2 只猫：

7 ÷ 2 = 3份，还多1条

把1条扔海里 🌊

剩下6条：

3条 + 3条

第一只猫拿走3条。

剩下：

3条

（2）🐱 第二只小猫来了！

3 条鱼分2份：

3 ÷ 2 = 1份，多1条

扔掉1条，再拿走1条。

成功！🎉

（3）所以答案是：

🧩 这道题目应该怎么做？

二、🌟 思路：使用枚举+模拟检查法：

从最小数字开始试：

1,2,3,4,5,6,7...

谁第一次成功，谁就是答案！

1、🎯 判断一次是否成功的方法

假设当前有fish条鱼。

每只猫都检查：

条件1：能多出 i 条

也就是：

fish % n == i

条件2：扔掉后还能平均分

剩下：

fish - i

必须能被 n 整除。

条件3：猫拿走一份后更新鱼数

每份是：

(fish - i) / n

猫拿走一份后还剩：

fish = fish - i - 每份

2、✨ 举个例子（7条鱼）

fish = 7 n = 2 i = 1

第一只猫：

7 % 2 = 1 ✔

扔1条后剩6

每份3条

拿走3条

剩3条

第二只猫：

3 % 2 = 1 ✔

成功！

3、💻 参考程序

#include <iostream> using namespace std; int main() { long long n, i; cin >> n >> i; long long fish = 1; // 从1开始试 while(true) { long long temp = fish; // 临时鱼堆 bool ok = true; // 每只猫都来试一次 for(int cat = 1; cat <= n; cat++) { // 条件不满足 if(temp % n != i || temp <= i) { ok = false; break; } long long one = (temp - i) / n; // 一份鱼 temp = temp - i - one; // 剩余鱼 } if(ok) { cout << fish; break; } fish++; } return 0; }

4、🪄 程序一步一步解释

第1步读入数据

cin >> n >> i;

输入：

2 1

第2步从1开始尝试

fish = 1

如果失败：

fish++

继续试！

第3步每只猫来分鱼

for(...)

让每只猫依次登场 🐱

第4步找到答案就输出

cout << fish;

5⏱️ 时间复杂度

假设答案是 X，小猫数是 n：

O(X × n)

意思：

试很多数字
每个数字让 n 只猫检查

三、🌟 思路：逆推模拟法：

前面写的是：从小到大试答案→ 这是枚举 + 模拟检查
我们现在：根据最后一轮反推上一轮鱼数，逐层构造答案→逆推模拟法

1、🐱 这个方法更像“模拟法”：

因为它不是盲目试：

1,2,3,4,5...

而是先假设最后一只猫分鱼时的状态，然后一步一步推回到第一只猫开始前的鱼数。

这相当于按规则“搭积木”。🧱

2、🧠 核心公式讲解

（1）🌟 最后一轮剩下的鱼

设最后一只猫分鱼前有：

fish = k * n + i

意思：

能分成n份
多出i条鱼
k表示每份有多少条

（2）🐱 这一轮分完后会剩多少？

扔掉i条后剩：

k*n

每只猫拿走一份：

剩下：

k*n - k = k(n-1)

这就是“下一轮看到的鱼”。

（3）🌟 反推上一轮公式

如果当前这一轮开始前鱼数是fish

那么上一轮开始前鱼数应满足：

prev - i

分成n份，拿走一份后剩下当前fish

整理后可得：

prev = fish * n / (n - 1) + i

前提是：

fish % (n - 1) == 0

否则不能整除，不合法。

3、💻 参考程序

#include <iostream> using namespace std; int main() { long long n, i; cin >> n >> i; long long k = 1; while (true) { bool ok = true; // 最后一只猫分鱼前的鱼数 long long fish = k * n + i; // 反推前面 n-1 只猫 for (int round = 1; round < n; round++) { if (fish % (n - 1) != 0) //检查下是否整除，判断合理性。 { ok = false; break; } fish = fish * n / (n - 1) + i; } if (ok) { cout << fish << endl; break; } k++; } return 0; }