约瑟夫环/丢手绢问题（PTA例题：猴子选大王）
最近在做学校课后作业的时候遇到了这类问题, 感觉对数组初学者是有一些困难的.
在写这篇题解之前, 我在网上找到的对这个问题的解析, 个人感觉要么太过浅显, 要么太过深刻.
个人鄙见, 对于某些问题, 初学者的了解（注意是初学者）控制到不浅不深是最好的——了解太浅则难以留下印象, 了解太深则花费大量时间精力.
而不浅不深可以让我们先对这些问题留下一定的印象, 随着时间推移, 我们变得更加机智, 原先的知识得到了消化, 并且拥有更大的知识储备. 此时可能神不知鬼不觉的, 我们对原来的知识了解已经更深入了. 就算没有这种奇妙感觉, 我们此时再温习原先的知识, 想加深理解往往也比初学时容易得多.
那么, 废话不多讲, 今天让我们通过一道典型题目“猴子选大王”, 一起了解一下“约瑟夫环”（也被称为“丢手绢问题”）.
（由于“猴子选大王”这道题目涉及了一些取余运算符%的知识, 所以为了趁热打铁, 在最后还会介绍并分析一下“数组元素循环右移”这道PTA上的练习题）
猴子选大王（PTA）
题目描述：
一群猴子要选新猴王. 新猴王的选择方法是：让N只候选猴子围成一圈, 从某位置起顺序编号为1~N号. 从第1号开始报数, 每轮从1报到3, 凡报到3的猴子即退出圈子, 接着又从紧邻的下一只猴子开始同样的报数. 如此不断循环, 最后剩下的一只猴子就选为猴王. 请问是原来第几号猴子当选猴王？输入格式：
输入在一行中, 一个正整数N（≤1000）.输出格式：
在一行中输出当选猴王的编号.输入样例：
11输出样例：
7
题目解析
在正式开始解决这道题目之前, 需要复习并明确一些重要的知识：
- 取余运算符
%, 双目运算符, 有两个运算对象, 要求两个运算对象均为整数！表达式A % B的求值, 其实就是求A ÷ B, 再把所得余数作为表达式的结果.
那么现在若有表达式x % N（现在只考虑x为非负整数,N为正整数）, 让N为一个确定的值, 此时这个表达式的取值范围是什么呢？
当N的值为5时, 我们直接列出x的各种取值：
0、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15……
对应地, 表达式x % N的值：
0、1、2、3、4、0、1、2、3、4、0、1、2、3、4、5……
由上述示例, 不难发现,x % N的取值范围：0、1、2、3、4……N - 2、N - 1, 并且在x的值取0、1、2、3、4……N - 2、N - 1时, 表达式的值就是x的值. - 应用一下取余符号
%的知识.
如果现在有5个号码：
3、4、5、6、7
那么如果让每个号码加上号码总数, 也就是5, 那么结果是：
8、9、10、11、12
再让所得结果分别%号码总数, 也就是5, 新结果是：
3、4、0、1、2
毕竟我们已经知道了一个非负整数% 5的结果只能是0、1、2、3、4, 所以这并不出乎意料. 令人不禁想到, 要是能让操作后的最终结果和原先的号码完全相同那该多好呀.
那么要是把原先的5个号码调整成：0、1、2、3、4, 现在以号码i代替原先的号码i + 3, 比如现在的0就是原先的3, 现在的1就是原先的4.
现在有5个号码：
0、1、2、3、4
那么如果让每个号码加上号码总数, 也就是5, 那么结果是：
5、6、7、8、9
再让所得结果分别%号码总数, 也就是5, 新结果是：
0、1、2、3、4
现在操作后的最终结果和原先的号码完全相同了.
同样不难发现, 现在如果让每个号码加上号码总数的倍数, 也就是5、10、15、20……再让所得结果分别%号码总数, 也就是5, 最终结果：
0、1、2、3、4
最终结果总是和原先号码完全相同.
从0开始的非负整数的连续序列0、1、2、3、4……总是作为数组的下标, 那么上述发现都可以应用到对数组下标的操作中. 由于数组下标又总是和某段序列对应, 所以往往可以先将这段序列转换为数组下标, 从而简化问题.
回归题目：
方法①——数组打标记
题目中猴子围成一圈, 猴子最多是1000只, 那么就先定义一个总共有1000个元素的整型数组, 由于数组下标是从0开始的, 所以下标代表所有猴子最初的序号 - 1. 所有元素先初始化为0, 对应语句：int arr[1000] = {0};
下标对应的值为0, 代表这个位置的猴子尚未退圈, 如果这个位置的猴子退圈了, 那就让下标对应的值为1. 这样根据数组下标反映顺序或对应位置, 根据下标对应的元素值反映状态, 是用数组解决问题的常见思想.
接着猴子开始报数, 可以考虑先设计一个死循环, 每次循环找到一只猴子, 如果猴子没退圈就报数并且需要找到下一只猴子, 如果猴子退圈了就需要直接找到下一只猴子. 所谓找猴子是按位置找, 也就是找数组下标, 这个过程其实是在遍历数组, 那么在循环时我们需要对数组下标计数, 所以在第一次循环前有对应语句：int index = 0;
然后增加一个跳出条件：退圈的猴子达到了N - 1只, 所以在循环时我们要对退圈的猴子进行计数, 所以在第一循环前有对应语句：int out = 0;
另外, 每报3下数就会有猴子退圈, 那么在循环时还应对报数总数进行计数, 所以在第一次循环前有对应语句：int num = 0;
值得注意的是, 数组下标的计数器index初值为0, 在值每增加N后, 让index作为数组下标要回归初值, 可以采用index % N：
比如位置为0、1、2的3只猴子, 猴子数量N为3, index的初值为0, 代表从位置为0的猴子开始报数. 再以两个具有代表性的报数情况为例：
①3只猴子按顺序报数后, index的值变成了3, 但并没有位置为3的猴子, 实际上此时是要访问位置为0的猴子, index % 3的值正好为0.
②2只猴子按顺序报数后, index的值变为了2, 有位置为2的猴子, 此时就是访问这个猴子, index % 3的值也正好为2.
循环结束后, 此时代表着原先的N只猴子只剩1只猴子了, 那么现在只有这只猴子最初的位置对应的数组下标对应的值为0, 直接借助最简单的遍历数组找到这个下标即可.找到下标后别忘了还要+1才能得到最初的序号.
附上我的代码实现：
#include<stdio.h>intmain(){intarr[1000]={0};intN=0;scanf("%d",&N);//猴子总数为N, 那数组下标的有效范围为[0, N - 1], 数组下标表示猴子位置intindex=0;intnum=0;intout=0;//每次循环, 找到对应位置的猴子, 如果猴子未退圈, 那么报1次数；如果猴子已退圈, 那么不报数//注意循环只是让我们逐位置找到猴子, 找到的猴子可能已退圈, 退圈的猴子不能报数, 所以一定有循环次数＞报数次数//注意区分循环次数、报数次数、退圈猴子数. 有N -1只猴子退圈的时候结束循环.while(1)//循环内未通过特定条件触发break语句时, 就会一直循环下去{if(arr[index%N]==1)//当前位置的猴子已退圈, 则不报数, 继续访问下一只猴子{index++;continue;}else//当前位置的猴子尚未退圈, 则报数, 继续访问下一只猴子{num++;if(num%3==0)//此时位置恰好报数为3, 该位置猴子需要退圈{arr[index%N]=1;//该位置的猴子退圈out++;}index++;}if(out==N-1)//退圈猴子达到N - 1只, 只剩1只猴子{break;}}inttarget=0;for(inti=0;i<N;i++){if(arr[i]==0){target=i;break;}}printf("%d\n",target+1);//目标猴子的最初下标为target, 转换为对应序号为target + 1return0;}方法②——递推法
本人数学不怎么样, 而且注意力不惊人, 所以采用形式最简单的找规律来找在某次报数前后, 两个猴子序列之间的关系.
由于我是知道答案的递推公式后, 才知道这个规律怎么找会比较通俗易懂, 所以以下的分析其实是在根据答案补全过程.
以6只猴子, 每轮报数的次数为4为例. 接下来表示一下完整的报数过程, 让该第1个报数的猴子的位置高亮, 用X表示某一位置的猴子已退圈. 为了方便, 我们不用环来表示猴子之间的位置关系, 而是如下所示：
12 3 4 5 6
1 2 3 X56
1 X3X 5 6
X X3X 5 6
X X X X56
X X X X 5 X
由以上报数过程可得：最终仅剩的猴子, 其最初序号为5.
为了便于发现涉及求余的递推公式（根据答案补全过程）, 则令最初的第1只猴子的新序号为0, 第2只猴子的新序号为1, 第3只猴子的新序号为2……以此类推, 则对所有猴子的原序号-1, 改成
01 2 3 4 5
0 1 2 X45
0 X2X 4 5
X X2X 4 5
X X X X45
X X X X 4 X
由以上报数过程可得：最终仅剩的猴子, 其最初序号为4 + 1 = 5.
接下来, 我们在每一行, 都把该第1个报数的猴子编号为0, 第2个报数的猴子编号为1, 第3个报数的猴子编号为2……以此类推（最后一行是最终态, 只剩1只猴子了不用报数了, 把仅剩的猴子编号为0即可）：
01 2 3 4 5 ——行1
2 3 4 X01 ——行2
3 X0X 1 2 ——行3
X X0X 1 2 ——行4
X X X X01 ——行5
X X X X 0 X ——行6
综上可得：除了现在的示例, 无论最开始总共有多少只猴子, 无论每一轮报数是报几次, 最后都得只剩一只猴子, 要是其他情况都像这个示例一样来表示全过程——写成许多行, 并且采取现在的编号规则, 首先不难发现, 仅剩的这只猴子在最后一行编号为0.
并且, 如果能根据最后一行的编号0推出对应位置在上一行的编号, 再根据上一行的编号推出对应位置在上上一行的编号, 再根据上上一行的编号推出对应位置在上上上一行的编号……最后推出对应位置在第一行的编号, 再+1就找到了最终仅剩的猴子在最初的序号.
对于某一行的编号i, 现在想要推出其所在位置在上一行的对应编号, 我们开始逐行找规律.
①行2推回行1的递推公式：从行2的0、1先往行1对照, 很轻松就发现了(i + 4) % 6
②行3推回行2的递推公式：
先从行3的0入手, (0 + 4) % 6的值为4, 再从行3的2入手, (2 + 4) % 6的值为0而不是1, 不过又发现(2 + 4) % 5的值倒是1, 再回看(0 + 4) % 5的值也为4. 逐个对照, 发现了(i + 4) % 5
③行4推回行3的递推公式：(i + 4) % 4
……
如果是从行n推回行n - 1, 如果报数次数是M次, 行n有k - 1项, 则行n - 1有k项（每次报数都要退圈1只猴子）,
行n推回行n - 1的递推公式：(i + M) % k
行n推回行n - 1的规律已经明确.
如果猴子总数为N, 在第一行为初状态的情况下, 需要N - 1个猴子退圈, 那就还需要N - 1行, 故总共有N行.
那么从最后一行推回第一行, 就需要应用N - 1次递推公式, 比较简单的考虑就是设计一个for循环, 总共循环N - 1次来递推N - 1次.
附上我的代码实现：
#include<stdio.h>intmain(){intN=0;scanf("%d",&N);intindex=0;//在最后一行, 仅剩的猴子编号为0for(inti=2;i<=N;i++)//以第一次递推为例：从倒数第一行推至倒数第二行. 倒数第二行共2项{index=(index+3)%i;}printf("%d",index+1);//和上一个方法一样, 不要忘了最后+1return0;}约瑟夫环/丢手绢问题
以下是从百度百科复制粘贴过来的问题背景. 了解与问题相关的故事有助于加深对问题的印象.
据说著名犹太历史学家Josephus（弗拉维奥·约瑟夫斯）有过以下的故事：在罗马人占领乔塔帕特后, 39个犹太人与Josephus及他的朋友躲到一个洞中, 39个犹太人决定宁愿死也不要被敌人抓到, 于是决定了一个自杀方式, 41个人排成一个圆圈, 由第1个人开始报数, 每报数到第3人该人就必须自杀, 然后再由下一个重新报数, 直到所有人都自杀身亡为止, 然而Josephus 和他的朋友并不想遵从. 首先从一个人开始, 越过k - 2个人（因为第一个人已经被越过）, 并杀掉第k个人. 接着, 再越过k - 1个人, 并杀掉第k个人. 这个过程沿着圆圈一直进行, 直到最终只剩下一个人留下, 这个人就可以继续活着. 问题是, 给定了和, 一开始要站在什么地方才能避免被处决. Josephus要他的朋友先假装遵从, 他将朋友与自己安排在第16个与第31个位置, 于是逃过了这场死亡游戏.
和上面“猴子选大王”的思路完全相同, 只是把退圈调整成了退出生物圈, 并且总人数更多了.
现在用之前递推法的代码, 输出结果是31, 所以第31个位置无疑是安全的.
那么为什么这个时候第16个位置也是安全的？当然是因为最后剩朋友和自己两个人的时候就安全了.
“第16个位置是安全位置”可以这样得出：
先根据递推公式, 简单口算得出最后一行编号为0的位置在倒数第二行的编号为1, 而倒数第二行总共就两项, 所以另一项的编号为0, 那么之前递推法的代码中的index的值仍为0, 无需更改, 只需把for循环条件里的i的初值改为3, 即第一次递推时, 变为从倒数第二行推至倒数第三行. 运行后输出结果即为16.
数组元素循环右移问题（PTA）
题目描述：
一个数组A中存有N（>0）个整数, 在不允许使用另外数组的前提下, 将每个整数循环右移M（≥0）个位置, 即将A中的数据由（A0A1…AN-1）变换为（AN-M…AN-1A0A1…AN-M-1）（最后M个数循环移至最前面的M个位置）. 如果需要考虑程序移动数据的次数尽量少, 要如何设计移动的方法？输入格式：
每个输入包含一个测试用例, 第1行输入N（1 ≤ N ≤ 100）和M（≥ 0）；第2行输入N个整数, 之间用空格分隔.输出格式：
在一行中输出循环右移M位以后的整数序列, 之间用空格分隔, 序列结尾不能有多余空格.输入样例：
6 2
1 2 3 4 5 6输出样例：
5 6 1 2 3 4
题目解析
首先, 认真审题, 有3个值得注意的点：
①不允许使用另外数组, 这提醒我们不能额外创造数组, 所以首先考虑找到一种简单方法, 能在不改变原有数组的情况下, 把原数组元素右移后的结果打印输出.
②需要考虑程序移动数据的次数尽量少, 那代码设计得越简单越好.
③最终结果打印时, 每个数字之间用空格分隔, 并且最后一个数的后面不可以有空格, 这需要我们注意控制输出格式, 要不然就会出现格式错误.
然后, 观察一下输入样例：1 2 3 4 5 6和输出样例：5 6 1 2 3 4, 后者由前者对应的数组其所有元素循环右移2位得到.
优先考虑用for循环, 条件设计为for (int i = 0; i < n; i++), 通过在0到n - 1之间改变i的值, 来打印输出右移后所得的新数组其下标为0到n - 1的所有元素. 同时由于我们打印输出时是需要借助原有的数组的, 那么现在其实要考虑如何把新数组还原为原数组.
可能大家会先想到把新得的元素全都循环左移2位, 不过这里提供一种我觉得更好想且不会数组越界的思路：把新得的元素全都循环右移4位.
这个4是根据数组元素总数6和之前右移的位数2共同得到的, 对于原先总共有6个元素的数组, 将所有元素先循环右移2位, 再循环右移4位, 则总共右移6位, 最终又得到了原数组.
综上所述：在打印输出时, 每次循环应该打印输出原数组下标为(i + 4) % 6的元素.
脱离输入样例和输出样例, 一般化后：在打印输出时, 每次循环应该打印输出原数组下标为(i + (N - M)) % N的元素.
附上我的代码实现：
#include<stdio.h>intmain(){intarr[100]={0};intN=0;intM=0;scanf("%d %d",&N,&M);for(inti=0;i<N;i++){scanf("%d",arr+i);}for(inti=0;i<N;i++){if(i!=0){printf(" ");}printf("%d",arr[(i+(N-M))%N]);}return0;}