题目:有n人围成一圈,顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来的第几号的那位。
解题思路(或者说过程):不妨找到特殊的n值,使得1号选手留到最后,显而易见的是,当n为1时,1号选手必然留到最后,做出假设,存在正整数k,当n=k时,1号选手存活到最后(存在性可证),然后,于所有的非负整数s,n=k+s时,(1+3*s)或者(1+3*s-n)号选手可以活到最后,后者是为了保证结果不超出n。我们可以从排人的角度理解这个假设,首先,一开始我们指向的会是一号选手,此时报数必为1,然后接着,排出一个人之后,我们指向了4号选手,这是4号选手报数也为1,接着,我们指到的号数依次会为7,11,14.....不难看出,每次排除一个人,我们指到的号数便会增加3,所以,首先我们能知道的则是,排出了s号人之后,我们指到的位置号数是(1+3*s)或者(1+3*s-n),其次,我们控制n=k时,1号选手都会留到最后,那么我们可以将排除了s号人之后的指到的那个人,视作n=k时的1号选手,则这个人便能活到最后(等效替代),因此,我们可以通过推理得知这个假设是正确的,合理的,从另一个角度来看,这个假设亦可以用归纳假设的方式去做证明,这里本文便不对此处的归纳做过多展开,请读者自己证明。
在知道上面的规律之后,我们便要将其变换成程序可以做的形态。假设我们只知道n=1时1号选手留到最后(知道1个特殊解就足够),将n从一开始递增,每次增加的时候,对应的结果a【n】都要加3,顺便检测是否超出n的范围,超出范围的时候要及时对结果进行处理(-n)。这样的话,我们便可以通过这个循环,得出一个数组,该数组上面对应的则是对应项数的留到最后的选手号数。
代码展示:
#include
int main()
{
int n;scanf("%d",&n);//输入
int a[n];a[0]=1;//需要补充的是,这里0对应的是总人数为1的情况,k对应的是总人数为k+1的情况。
int i;for(i=0;i<n-1;i++){
a[i+1]=a[i]=3;if(a[i+1]>i+1)a[i+1]-=(i+1);//写出循环,一定要补充if的条件。
}
printf("%d",a[n-1]);return(0);//得出结果,返回0。
}
题外话:该题属于约瑟夫问题的延展,约瑟夫的问题就相当于报数报道2就要排人的情况,这种情况下,2的方幂次数的总人数总会是第一个人就留到最后,因此,我们可以率先得出无数个特殊解,便能避免了上面要减去总人数的那种情况,假设x为存活选手号数,y为总人数,a<2^n,a和n都是非负整数,在n最大化的情况下,y=a+2^n,则x=2*a+1,不难证出,这种情况下的x<=2^(n+1)-1=y,因此算出来的结果都是控制在范围之内的,就不需要对其作减法(减去总人数)处理。如果,增添了数到m才停止且m也要手动输入的要求,则把上面代码中的3改为m且增加m的输入语句即可。
最后,希望大家多多指教,本人为第一次撰写文章,很多地方用词可能不太舒服,还望各位多多谅解。谢谢阅读!
0.0分
4 人评分
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:667 |
C语言程序设计教程(第三版)课后习题1.6 (C++代码)浏览:907 |
简单的a+b (C语言代码)浏览:734 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:655 |
1024题解浏览:867 |
1035 题解浏览:866 |
勾股数 (C语言代码)浏览:819 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:587 |
数列排序 (C语言代码)浏览:667 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:617 |