关于浙大版《C语言程序设计（第3版）》习题8-4

[zjl0317]

您好，研究了好久8-4的迭代，一直看不明白，想请教您一下，您在写这个问题的迭代思路是什么？或者说，您是怎么考虑这个问题的？谢谢

[nialin]

循环报数的模型是一种离散的锯齿函数。表达形式为y = (kx + a) % T + b。其中k是斜率，T是周期，a，b是函数相对源点在x，y轴的平移。分析过程中反复用到它。
本题的求解思想是，已知离开圈子的轮次，反向推导出它在初始圈子中的序号。get_origin_num的定义为“在还剩下i个人的条件下，求离开圈子的人在人数规模为n的圈子中的序号”。
不难得知，当人数规模为n时，离开圈子的序号是(m - 1) % n + 1。
由于我们需要反向推理，即需要知道当圈子规模为origin_size的序号用圈子规模为origin_size - 1的序号关系表达。
直观地，举个例子：
当m = 3，origin_size = 5时，序号顺序为：
1 2 3 4 5
3离开圈子，origin_size = 4，序号顺序变化为：
3 4 X 1 2

出圈人的序号 = (m - 1) % 出圈前的规模 + 1;
出圈前的序号 = (出圈后的序号 + 出圈人的序号) % 出圈前的规模 + 1
= (出圈后的序号 + (m - 1) % 出圈前的规模) % 出圈前的规模 + 1
= (出圈后的序号 + m - 1) % 出圈前的规模 + 1

综上，递归方程建立起来了。