数论中的程序设计-New.ppt

输入与输出样例 输入样例： 10 8 10 2 输出样例： 1 5 分析 方法一：模拟法 实际模拟数小孩出列的过程。用一个数组表示小孩围成圈。对每个小孩赋以一个序号值作为小孩的标志。 采用 “加1求模”，当数到数组尾的时候，下一个数组下标值可以算得为0，从而回到数组首以继续整个过程。 设：Max=10000;小孩最大个数 num为小孩个数，a[Max]; 小孩数组 每次数m个小孩，便让该小孩离开；下标加1求模，使下标到达尾部后能返回到数组头。 参考代码一：见下页 #includeiosteam using namespace std; int main(){ const int Max=10000; int num,m, a[Max]; while(cinnumm){ for(int i=0;inum;i++) a[i]=i+1; //小孩编号 int k=1; //标识处理第k个小孩的离开 int i=-1; //初值 while(1){//圈中数m个小孩 for(int j=0;jm;){ i=(i+1)%num; if(a[i]!=0) j++; } if(k==num) break; //该小孩是最后一个吗？ //是，则为胜利者 a[i]=0;//标识该小孩离开 k++;//准备处理圈中的 //下一个小孩 } coutendl; cout a[i]endl; //第a[i]个小孩获胜 } return 0; } 分析 方法二：数学方法 更改一下报数的基准，从0开始数，那么这num个小孩一字排开，就是：0，1，2，3，…，num-1。 算法思想是，从唯一的小孩开始（起始他的标号为0），倒推到num次这个小孩的标号，最终得到起始状态时共有num个小孩时最终的标号，即为题目所求。 以下的推导类似于数学归纳法证明过程： 如果只有一个小孩，他的标号是0，那么这个小孩的标号就是结果，此时r=0。 考虑目前有k-1个小孩的情况： 0，1，2，…，r-1，r，r+1，…，k-2，k-1 这里标号r就是当小孩总数为k-1个的时候最终的结果。 当小孩总数为k时 按照新定义的计数方式，从0开始数，数到m-1出列，那么上个数列在这个孩子没出列时的编号是多少呢？如下： m，m+1，m+2，…，m+r-1，m+r，m+r+1，…，m+k-2，m+k-1 两个问题需考虑： 出列的那个小孩没有考虑进去，由于所有小孩是围成一个圈的，所以，可把标号为m-1的这个出列的小孩放在首尾皆可，比如放在前面： m-1，m，m+1，m+2，…，m+r-1，m+r，m+r+1，…，m+k-2，m+k-1 小孩围成个圈，那么这个编号应该是从0开始，到k-1结束。只要把所有的这些编号对k取模即可。新的r值就按照这个变换方法变换即可，于是得到r=(r+m)%k。 参考代码二 #include iostream using namespace std; int main() { int num,m,r while(cinnumm) { r=0; for(int k=1;k=num;++k) r=(r+m)%k; coutr+1endl; } return 0; } 5 负数进制转换 问题描述（大意）： 设计一个程序，读入一个十进制数和一个负进制的基数，并将此十进制数转换成为此负进制下的数： -R∈{-2,-3,-4,......-20} 例如，十进制数-15，相当于-2进制数110001：因110001=1*(-2)5+1*(-2)4+0*(-2)3+0*(-2)2+0*(-2)1+1*(-2)0 输入 输入的每行有两个数据N、-R。 N是十进制数，（-32768≤N≤32767），-R是负进制数的基数。 输出 相对于每组输入，应输出此负进制数及其基数，若此基数超过10，则参照十六进制的方式处理。 输入与输出样例 输入样例 输出样例 30000 –2 -20000 –2 28800 –16 -25000 –16 30000=11011010101110000 (base -2) -20000=1111011000100000 (base -2) 28800=19180 (base -16) -25000=7FB8 (base -16) 分析 采用与正数进制的转换相类似的方法。 对负数进制，每次取的余数保证在0~R-1之间，就可以直接输出。 例如-R=-