河海大学 · 2026秋季 · 计算思维导论 · 独立必做题
作业题2:五个海盗分金币
用穷举法寻找最小初始数量,通过五轮分配记录验证算法。
授课教师:谢在鹏(河海大学计算机系) · 使用C或Python完成
这是一道新的独立必做题。它不属于“活动安排与算法选择”的变种。两项作业均须完成,分别提交;活动安排页的100分评分标准仅适用于该项作业。
题目与要求
这道题练习穷举、循环与状态更新。你需要让程序尝试不同的初始数量,并检查它能否连续满足五轮分配规则。
题目背景与规则
海滩上有一堆金币,五个海盗依次来取。每个海盗都对自己面前剩余的金币进行相同的操作:
- 把当前金币平均分成五份,发现恰好多出一枚。
- 把多出的一枚扔进海里。
- 从五份中拿走一份,将其余四份留在海滩上。
五个海盗都成功完成了上述操作。海滩上最初至少有多少枚金币?
请注意:金币不能拆分,每一份至少包含一枚金币。下一位海盗处理的是上一位留下的金币。第五个海盗操作完成后,不再要求剩余金币额外平均分一次。
编程任务
使用C或Python编写程序,用穷举法寻找满足条件的最小初始数量。本题没有输入,五个海盗和上述规则均为固定条件。
程序应输出:
- 满足条件的最小初始金币数量。
- 五轮操作记录,每轮列出海盗序号、操作前数量、扔掉一枚后的数量、拿走的一份数量,以及最终剩余数量。
各列含义如下,具体排版可自行决定:
海盗序号 操作前 扔掉一枚后 拿走一份 剩余算法说明与自查
- 怎样保证找到最小值?说明从什么数量开始尝试,按什么顺序尝试,以及为什么首次通过检查的候选就是最小值。
- 怎样检查一个候选?说明每一轮需要满足什么条件。若中途不满足,程序应怎样处理?
- 怎样更新记录?区分“这次尝试的初始数量”和“当前剩余数量”,说明尝试下一个候选时哪些记录需要重新设置。
- 怎样表达算法?画流程图或写伪代码,明确外层的“尝试初始数量”和内层的“模拟五个海盗”两种重复过程。
- 怎样验证结果?根据输出的五轮记录逐轮核对规则,再说明程序如何排除所有更小的正整数候选。只展示一个分配成功的数量,还不能说明它最小。
提交内容
提交源代码、五轮运行记录,以及一份简短算法说明和流程图或伪代码。这是一道独立的必做题,与活动安排作业分开完成和提交,两项作业均须完成。截止时间与提交方式以教师通知为准。