第38套题：c语言出圈问题分析.doc

第38套题：设有n个人围坐一圈并按顺时针方向从1到n编号，从第s个人开始进行1到m的报数，报数到第个m人，此人出圈，再从他的下一个人重新开始1到m的报数，如此进行下去直到所有的人都出圈为止。现要求按出圈次序，每10人一组，给出这n个人的顺序表。请考生编制函数Josegh()实现此功能并调用函数WriteDat()把结果p输出到文件OUT.DAT中。设n=100,s=1,m=10.思路：(1)将1到n个人的序号存入一维数组p中；(2)若第i(注意这里的i是指出圈的次序，如：第一个出圈的人，而不是序号为i的人出圈，也就是说第一个出圈的人放在倒数第一的位置上，第二个出圈的放在倒数第二个位置上，依此类推)个人报数后出圈，则将pi置于数组的倒数第i个位置上，而原来第i+1个至倒数第i个元素依次向前移动一个位置；(3)重复第(2)步直至圈中只剩下p1为止。部分源程序已给出。请勿改动主函数main()和输出数据函数writeDat()的内容。-/重点，注意n个位置，每次出圈一个人，出去一个人就腾出一个位置，也就是说那个位置没用了，可以用来存放出圈的元素，而循环控制变量I(控制人的个数)每次减一，就相当于每次把圈的大小减一，踢出一个位置不用(实现是通过循环到人的个数时跳过最后几个存出圈元素的位置，进行下一次循环，而只不过被踢出圈的元素还在圈里，只不过到了那几个位置，就跳过，那几个位置由于没有用，所以可用来存放被踢出圈的元素) 注：题中第一个for()循环是先对数组p赋初值。在第二个for()中用i来控制没出圈的总人数，s1=(s1+m-1)%i的作用是找出报数后出圈人的下标，其中对i求余的作用是使报数按圈进行（即报到尾后又从头报），该算法在很多题目中都用到。由于求余的作用当报数正好到最后一个时s1为0，故而要进行if(s1=0)的判断。内嵌的for()循环是将出圈以后的人依次往前移。解题思路：题目中已经给出了算法过程，我们下面就看看怎么用代码实现：(1)将1到n个人的序号存入一维数组p中；这个我想大家应该都没有问题的了：很简单的一句循环赋值。for(i=1;i1;i-)接下来就是该怎么写循环体的内容了：我们可以发现，题目的算法过程2描述的很清楚，具体如下：s=(s+m-1)%i;首先，求出出圈人的位置，这里用一个求余是为了实现圈循环（也就是将队列头尾相连），这里i是圈中剩余的人数（除去出圈后的人）。 当然，我们稍微注意一下，那就是没有第0位的出圈人存在，所以这里如果s=0是不对的，其实这种情况是出圈人是队尾的那一个人，所以这里加上一个判断：if(s=0)s=i;好了，我们取到了出圈人的位置了，那我们就要：则将pi置于数组的倒数第i个位置上，而原来第i+1个至倒数第i个元素依次向前移动一个位置实现这一句的算法过程的代码，可以看出也是一个循环：w=ps-1; 首先，把出圈人的号码暂时放起来（因为此时倒数第i个位置还有人占据，不能替换掉）接着我们要把倒数第i个位置腾空出来，而这个算法的实现就是“第i+1个至倒数第i个元素依次向前移动一个位置”明白了这句话的意思后，马上可以写出下面的一个循环代码来实现for(j=s;ji;j+)pj-1=pj;出圈人的位置让给他的下一位，依次类推，最后腾出倒数第i个位置给出圈人。 最后出圈人占据倒数第i个位置：pi-1=w;（注意这里第i个位置在数组中下标是i-1,因为数组下标是0开始的，_） 到这里为止，循环体也写完了，整合起来，就可以得到下面的完整函数代码了： #include #define N 100;#define S 1;#define M 10;int n; /圈中人数int s; /第s个人开始报数int m; /报数到m出圈int p100;void josegh(void)int i;/圈中剩余的人int j;int tmp; / 初始化序号for(i=1;i1;i-)s = (s+m-1)%i; /找出圈的人if(s = 0) /没有0序号的人 0也就是最后位置s = i;tmp = ps-1;for(j=s;j=0; i-)printf(%4d,pi);fprintf(fp,%4d,pi);if(i%10 = 0)printf(n);fprintf(fp,n);OUT.DAT 10 20 30 40 50 60 70 80 90 100 11 22 33 44 55 66 77 88 99 12 24 36 48 61 73 85 97 9 25 38 52 65 79 93 6 21 37 53 68 83 98 15 31 47 64 82 1 17 35 56 74 92 13 32 54 75 95 18 42 63 87 8 39 62