算法基本工具(Part2).ppt

【例2】游戏问题：12个小朋友手拉手站成一个圆圈，从某一个小朋友开始报数，报到7的那个小朋友退到圈外，然后他的下一位重新报“1”。这样继续下去，直到最后只剩下一个小朋友，求解这个小朋友原来站在什么位置上呢？  * 算法设计： 这个问题初看起来很复杂，又是手拉手，又是站成圈，报数到7时退出圈……似乎很难入手。 细细分析起来，首先是如何表示状态的问题。开辟12个元素的数组，记录12个小朋友的状态，开始时将12个元素的数组值均赋为1，表示大家都在圈内。这样小朋友报数就用累加数组元素的值来模拟，累加到7时，该元素所代表的小朋友退到圈外，将相应元素的值改赋为0，这样再累加到该元素时和不会改变，又模拟了已出圈外的状态。 为了算法的通用性，算法允许对游戏的总人数、报数的起点、退出圈外的报数点任意输入。其中n表示做游戏的总人数，k表示开始及状态数组的下标变量，m表示退出圈外的报数点，即报m的人出队，p表示已退出圈外的人数。。 算法如下： * main( ) {int a[100],i,k,p,m; print(“input numbers of game:”); input(n); print(“input serial number of game start:”); input(k); print(“input number of out_ring:”); input(m); for( i=1;i=n;i++) a[i]=1; p=0; while (pn-1) {x=0； while xm {k=k+1; if(kn) k=1; x=x+a[k];} print(k); a[k]=0; p=p+1; } for( i=1;i=n;i++) if ( a[i]=1) print( “i=”,i); } 算法说明： 1）? 算法中当变量k n时，赋k=1，表示n号报完数就该1号报数。模拟了将n个人连成了一个“圈”的情况。 2）? x为“报”出的数，x=m时输出退出圈外人的下标k，将a[k]赋值为0； 3）? p=n-1时游戏结束； 4）? 最后检测还在圈上a[i]=1的人，输出其下标值即编号（原来位置）。 思考：可选择顺时针或反时针方向报数。 *b 3.3.4大整数的存储及运算 * 1 编程求当N=100时，N！的准确值。 问题分析： 例如： 9！=362880 100！ = 　93 326215 443944 152681 699263 856266 700490 715968 264381 621468 592963 895217 599993 229915 608914 463976 156578 286253 697920 827223 758251 185210 916864 000000 000000 000000 000000  * 问题分析: 计算机存储数据是按类型分配空间的。在PC上： 整型：2个字节16位，则整型数据的范围为-32768—32767； 长整型：4个字节32位，则长整型数据的范围为 -2147483648—2147483647； 实型：4个字节32位，但非精确存储数据，只有六位精度，数据的范围±(3.4e-38~3.4e+38) ； 双精度型：8个字节64位的存储空间，数据的范围±(1.7e-308~1.7e+308)，其精确位数是17位。 这些类型无法存储100！这样的“大整数”。 需要使用更复杂、更有针对性的数据结构。 * 算法设计 每一位数，都是一个10以内数字。多个，相同属性的，… 数组是有头有尾的：a[1]~a[n]。高位、低位谁头谁尾？ 低位固定，而高位不定。最低位为a[1]，且在高端要为问题最大存储数据留够空位。 基于存储的考虑 int a[n] * 算法设计 100！=1*2*3*……*99*100。 按此方法计算，最困难的操作是： 大整数*乘数，其中乘数=100。 基于功能的考虑 原来一个元素存一位，现在是否要改变？改变是否有用？ 问题出在哪里？ 当低位元素计算后的值超过9时，需向高位元素进位。 如何进位？ * 算法设计 int a[n]中的数组元素可以存放更大的数。如，每个存3位。 基于性能的考虑 进位4次。 进位几次？ 进位需要特殊的处理；减少进位的处理，可以提高效率。 每个元素处理的位数越多，进位次数越少。 在前面提到的四种数据类型的基础上，粗略估计一下，本问题中，每个元素最多可以存储几位数据？ * 算法实现 main( ){