约瑟夫环/丢手绢问题（PTA例题：猴子选大王）

约瑟夫环/丢手绢问题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才能得到最初的序号.附上我的代码实现#includestdio.hintmain(){intarr[1000]{0};intN0;scanf(%d,N);//猴子总数为N, 那数组下标的有效范围为[0, N - 1], 数组下标表示猴子位置intindex0;intnum0;intout0;//每次循环, 找到对应位置的猴子, 如果猴子未退圈, 那么报1次数如果猴子已退圈, 那么不报数//注意循环只是让我们逐位置找到猴子, 找到的猴子可能已退圈, 退圈的猴子不能报数, 所以一定有循环次数报数次数//注意区分循环次数、报数次数、退圈猴子数. 有N -1只猴子退圈的时候结束循环.while(1)//循环内未通过特定条件触发break语句时, 就会一直循环下去{if(arr[index%N]1)//当前位置的猴子已退圈, 则不报数, 继续访问下一只猴子{index;continue;}else//当前位置的猴子尚未退圈, 则报数, 继续访问下一只猴子{num;if(num%30)//此时位置恰好报数为3, 该位置猴子需要退圈{arr[index%N]1;//该位置的猴子退圈out;}index;}if(outN-1)//退圈猴子达到N - 1只, 只剩1只猴子{break;}}inttarget0;for(inti0;iN;i){if(arr[i]0){targeti;break;}}printf(%d\n,target1);//目标猴子的最初下标为target, 转换为对应序号为target 1return0;}方法②——递推法本人数学不怎么样, 而且注意力不惊人, 所以采用形式最简单的找规律来找在某次报数前后, 两个猴子序列之间的关系.由于我是知道答案的递推公式后, 才知道这个规律怎么找会比较通俗易懂, 所以以下的分析其实是在根据答案补全过程.以6只猴子, 每轮报数的次数为4为例. 接下来表示一下完整的报数过程, 让该第1个报数的猴子的位置高亮, 用X表示某一位置的猴子已退圈. 为了方便, 我们不用环来表示猴子之间的位置关系, 而是如下所示12 3 4 5 61 2 3 X561 X3X 5 6X X3X 5 6X X X X56X X X X 5 X由以上报数过程可得最终仅剩的猴子, 其最初序号为5.为了便于发现涉及求余的递推公式根据答案补全过程, 则令最初的第1只猴子的新序号为0, 第2只猴子的新序号为1, 第3只猴子的新序号为2……以此类推, 则对所有猴子的原序号-1, 改成01 2 3 4 50 1 2 X450 X2X 4 5X X2X 4 5X X X X45X X X X 4 X由以上报数过程可得最终仅剩的猴子, 其最初序号为4 1 5.接下来, 我们在每一行, 都把该第1个报数的猴子编号为0, 第2个报数的猴子编号为1, 第3个报数的猴子编号为2……以此类推最后一行是最终态, 只剩1只猴子了不用报数了, 把仅剩的猴子编号为0即可01 2 3 4 5 ——行12 3 4 X01 ——行23 X0X 1 2 ——行3X X0X 1 2 ——行4X X X X01 ——行5X 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次.附上我的代码实现#includestdio.hintmain(){intN0;scanf(%d,N);intindex0;//在最后一行, 仅剩的猴子编号为0for(inti2;iN;i)//以第一次递推为例从倒数第一行推至倒数第二行. 倒数第二行共2项{index(index3)%i;}printf(%d,index1);//和上一个方法一样, 不要忘了最后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中存有N0个整数, 在不允许使用另外数组的前提下, 将每个整数循环右移M≥0个位置, 即将A中的数据由A0A1…AN-1变换为AN-M…AN-1A0A1…AN-M-1最后M个数循环移至最前面的M个位置. 如果需要考虑程序移动数据的次数尽量少, 要如何设计移动的方法输入格式每个输入包含一个测试用例, 第1行输入N1 ≤ N ≤ 100和M≥ 0第2行输入N个整数, 之间用空格分隔.输出格式在一行中输出循环右移M位以后的整数序列, 之间用空格分隔, 序列结尾不能有多余空格.输入样例6 21 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的元素.附上我的代码实现#includestdio.hintmain(){intarr[100]{0};intN0;intM0;scanf(%d %d,N,M);for(inti0;iN;i){scanf(%d,arri);}for(inti0;iN;i){if(i!0){printf( );}printf(%d,arr[(i(N-M))%N]);}return0;}