计算机常用算法与程序设计第9章-模拟.ppt

1、 教学要求教学要求掌握竖式乘除模拟掌握竖式乘除模拟设计设计要领并应用解决多位整数要领并应用解决多位整数与指定精度的无理数高精度计算案例与指定精度的无理数高精度计算案例掌握应用随机函数模拟设计求解自然界的随机现掌握应用随机函数模拟设计求解自然界的随机现象象 本章重点本章重点根据案例的实际选择与确定模拟量，设计程序实根据案例的实际选择与确定模拟量，设计程序实现模拟。现模拟。n 设竖式除过程中被除数为设竖式除过程中被除数为a a，除数为，除数为p p，试商所得的商，试商所得的商为为b=a/pb=a/p，所得余数为，所得余数为c=a%pc=a%p。n 实施模拟，可根据问题的具体实际确定终止运算的循实施

2、模拟，可根据问题的具体实际确定终止运算的循环条件。竖式除模拟框架描述：环条件。竖式除模拟框架描述：n 输入输入 ；确定；确定 ；n while(while()n a=c a=c*t+m;/t+m;/构造被除数构造被除数a a n b=a/p;b=a/p;/实施除运算实施除运算,计算商计算商b b n printf(b);printf(b);n c=a%p;c=a%p;/试商得余数试商得余数c c n n 通常设通常设w w数组表示乘运算的一个乘数，也表示该数乘数组表示乘运算的一个乘数，也表示该数乘以以p p（另一个乘数）的积：（另一个乘数）的积：w(1)w(1)表示个位数，表示个位数，w(2)

3、w(2)为十位为十位数，数，。n 实施竖式乘模拟必须考虑进位。设进位数为实施竖式乘模拟必须考虑进位。设进位数为m m并赋初并赋初值，显然，乘数的第值，显然，乘数的第k k位数位数w(k)w(k)乘以另一个乘数乘以另一个乘数p p的结果的结果为为a=w(k)a=w(k)*p+mp+m，然后把所得到的乘积，然后把所得到的乘积a a的个位数存储为积的个位数存储为积的第的第k k位数：位数：w(k)=a%10w(k)=a%10；而；而a a的十位及以上的值做为下轮的十位及以上的值做为下轮运算的进位数：运算的进位数：m=a/10m=a/10。n w w数组（一个乘数）与进位数数组（一个乘数）与进位数m

4、m的初值、乘运算的结束的初值、乘运算的结束条件由所求问题的具体实际确定，通常使乘运算达到某条件由所求问题的具体实际确定，通常使乘运算达到某一特定值或达到某一规定位数后结束。一特定值或达到某一规定位数后结束。n 输入输入 n 确定确定 n while(while()n k=k+1;k=k+1;n a=w(k)a=w(k)*p+m;p+m;/计算乘积计算乘积a a，m m为为 n w(k)=a%10;w(k)=a%10;/乘积乘积a a的个位存储到的个位存储到w(k)w(k)n m=a/10;m=a/10;/乘积乘积a a的十位以上作为下轮的进位数的十位以上作为下轮的进位数 n n 输出输出(w(

5、d(w(d：1);1);/从高位到低位输出乘积从高位到低位输出乘积 n两位计算机爱好者两位计算机爱好者A、B在老师在老师C的指导下进行乘数探求的指导下进行乘数探求游戏：游戏：nA A：请你任给定一个正整数请你任给定一个正整数p（约整数（约整数p为个位数字不是为个位数字不是5的奇数），我可寻求正整数的奇数），我可寻求正整数q，使得，使得p与与q之积为全是之积为全是“1”组成的整数。组成的整数。nB B：也请你任给定一个正整数也请你任给定一个正整数p（同样约定整数（同样约定整数p为个位为个位数字不是数字不是5的奇数），我可寻求正整数的奇数），我可寻求正整数q，使得，使得p与与q之积为之积为全是由指

6、定的全是由指定的“23”组成的整数。组成的整数。n请完成以上两例乘数探求设计。请完成以上两例乘数探求设计。)9()8()7()6()5()4()3()2()1(aaaaaaaaa)9()8()7()6()5()4()3()2()1(aaaaaaaaan给定正整数给定正整数p（约定整数（约定整数p为个位数字不是为个位数字不是5的奇数），的奇数），寻求最小正整数寻求最小正整数q，使得，使得p与与q之积为全是之积为全是“1”组成的整数。组成的整数。n1.1.竖式除模拟设计要点竖式除模拟设计要点n设整数除竖式计算每次试商的被除数为设整数除竖式计算每次试商的被除数为a，除数为，除数为p（即（即给定的正整

7、数），每次试商的商为给定的正整数），每次试商的商为b，相除的余数为，相除的余数为c。n以余数以余数c0作为条件设置条件循环，循环外赋初值：作为条件设置条件循环，循环外赋初值：c=111,n=3;或或c=11,n=2等等。等等。n被除数被除数a=c*10+1，试商余数，试商余数c=a%p，商，商b=a/p即为所寻即为所寻求数求数q的一位。若余数的一位。若余数c=0，结束；否则，继续下一轮试商，结束；否则，继续下一轮试商，直到直到c=0为止。为止。)9()8()7()6()5()4()3()2()1(aaaaaaaaa)9()8()7()6()5()4()3()2()1(aaaaaaaaansca

8、nfscanf(%(%d,&pd,&p););nprintfprintf(寻求的最小乘数寻求的最小乘数q为：为：);nn=1;c=1;n=1;c=1;/确定初始值确定初始值n,cnwhile(cwhile(c*10+1p)10+1pnp，说明，说明乘积乘积p p*q q为若干个为若干个z z的乘数的乘数q q不存在。不存在。n（2 2）求出求出n n个个z z能被能被p p整除之后，再次模拟除运整除之后，再次模拟除运算，对每一个算，对每一个z z的每一位逐位试商，每试商一位，的每一位逐位试商，每试商一位，输出所寻求的输出所寻求的q q的一位。的一位。n/构成元素构成元素z z为为k k个数字个

9、数字djdjn/确定大于确定大于p p的由若干个的由若干个z z组成的组成的y ync=y%p;/c=y%p;/确定初始值确定初始值 nwhile(c!=0)while(c!=0)n for(j=k;j=1;j-)for(j=k;j=1;j-)n a=c a=c*10+dj;c=a%p;b=a/p;10+dj;c=a%p;b=a/p;n printf(%d,b);/printf(%d,b);/输出整数输出整数q q的一位数的一位数 n n nprintf(n printf(n 乘积乘积p p*q q为为%d%d个个%d.n,n,z);%d.n,n,z);值值 n 9.3.1 9.3.1 尾数限

10、一个数字尾数限一个数字n 整数整数n n的尾数是的尾数是9 9，把尾数，把尾数9 9移到其前面移到其前面(成为最成为最高位高位)后所得的数为原整数后所得的数为原整数n n的的3 3倍，原整数倍，原整数n n至少至少为多大为多大?n整数整数n的尾数的尾数q（限为一位）移到（限为一位）移到n的前面所得的的前面所得的数为数为n的的p倍，记为倍，记为n(q,p)，这里约定，这里约定1pq9。n对于指定的尾数对于指定的尾数q与倍数与倍数p，求解，求解n(q,p)。n 设设n n为为efgwqefgwq（每一个字母表示一位数字），尾数（每一个字母表示一位数字），尾数q q移移到前面变为到前面变为qefgw

11、qefgw，它是，它是n n的的p p倍。倍。n 注意到尾数注意到尾数q q前移后数的首位为前移后数的首位为q q，而第二高位，而第二高位e e即为所即为所求求n n的首位，第三高位的首位，第三高位f f即为即为n n的第二高位，的第二高位，。n 应用竖式除模拟：第一位数应用竖式除模拟：第一位数q q除以除以p p（约定（约定qpqp），余），余数为数为c c，商为，商为b b。输出数字。输出数字b b作为所求作为所求n n的首位数。的首位数。n 进入模拟循环，当余数进入模拟循环，当余数c=0c=0且商且商b=qb=q时结束，因而循环时结束，因而循环条件为：条件为：c!=0|b!=qc!=0|

12、b!=q。n 在循环中计算被除数在循环中计算被除数a=ca=c*10+b10+b，b b为上轮试商的商；为上轮试商的商；n 试商得试商得b=a/pb=a/p，输出即，输出即n n的一位；的一位；n 求得余数求得余数c=a%pc=a%p；nscanf(“%d,%d,&q,&p);scanf(“%d,%d,&q,&p);/输入处理数据输入处理数据q,p q,p nb=q/p;c=q%p;b=q/p;c=q%p;/确定初始条件确定初始条件 nprintf(n(%d,%d)=%d,q,p,b);printf(n(%d,%d)=%d,q,p,b);/输出输出n n的首位的首位b b nwhile(c!=

13、0|b!=q)while(c!=0|b!=q)/试商循环处理试商循环处理 n a=c a=c*10+b;10+b;n b=a/p;c=a%p;b=a/p;c=a%p;/模拟整数除竖式计算模拟整数除竖式计算 n printf(%d,b);printf(%d,b);n n 设置存储数设置存储数n n的的w w数组。从尾数数组。从尾数w(1)=qw(1)=q开始，乘开始，乘数数p p与与n n的每一位数字的每一位数字w(i)w(i)相乘后加进位数相乘后加进位数m m，得，得a=w(k)a=w(k)*p+mp+m；n 积积a a的十位以上的数作为下一轮的进位数的十位以上的数作为下一轮的进位数m=a/1

14、0m=a/10；而；而a a的个位数此时需赋值给乘积的下一位的个位数此时需赋值给乘积的下一位w(i+1)=a%10w(i+1)=a%10。n 当计算的被除数当计算的被除数a a为尾数为尾数q q时结束。时结束。n scanf(%d,%d,&q,&p);scanf(%d,%d,&q,&p);n for(j=1;j100;j+)wj=0;for(j=1;j=1;j-)for(j=k-1;j=1;j-)/从高位到低位打印每一位从高位到低位打印每一位 n printf(%d,wj);printf(%d,wj);n printf(n printf(n 共共%d%d 位。位。n,k-1);n,k-1);n

15、关于圆周率关于圆周率的计算，历史非常久远。我国数学家祖冲的计算，历史非常久远。我国数学家祖冲之最先把圆周率之最先把圆周率计算到计算到3.14159263.1415926，领先世界一千多年。，领先世界一千多年。其后，德国数学家鲁特尔夫把其后，德国数学家鲁特尔夫把 计算到小数点后计算到小数点后3535位，日位，日本数学家建部贤弘计算到本数学家建部贤弘计算到4141位。据称位。据称18741874年英国数学家香年英国数学家香克斯利用微积分倾毕生精力把克斯利用微积分倾毕生精力把 计算到计算到707707位，但位，但528528位后位后的数值是错的。的数值是错的。n 应用计算机计算圆周率应用计算机计算圆

16、周率 曾有过计算到数百万位的报导，曾有过计算到数百万位的报导，主要是通过主要是通过 的计算宣示大型计算机的运算速度。的计算宣示大型计算机的运算速度。n 试计算圆周率试计算圆周率，精确到小数点后指定的，精确到小数点后指定的x x位。位。9.5 圆周率指定高精度计算圆周率指定高精度计算（1）选择计算公式 计算圆周率的公式很多，选取收敛速度快且容易操作的计算公式是设计的首要一环。我们选用以下公式：11 21 2 31 21233 53 5 73 5(21)nn 1211111352121nnnn （2）确定计算项数 首先，要依据输入的计算位数 x 确定所要加的项数 n。显然，若n 太小，不能保证计算

17、所需的精度；若 n 太大，会导致作过多的无效计 算。可 证 明，式 中 分 式 第n项 之 后 的 所 有 余 项之和nnRa。因此，只要选取 n，满足1110nxa即可。即只要使 521lg3lglg12nxn 于是可设置对数累加实现计算到x位所需的项数n。为确保准确，算法可设置计算位数超过 x 位（例如 x+5 位），计算完成后只打印输出 x 位。n 设置设置a a数组，。计算的整数值存放在数组，。计算的整数值存放在a(0)a(0)，小数点后第，小数点后第i i位存放在位存放在a(i)a(i)中中(i=1,2,)(i=1,2,)。n 数组除以数组除以2n+12n+1，乘以，乘以n n，加上

18、，加上1 1；再除以；再除以2n2n1 1，乘以，乘以n n1 1，加上加上1 1；。这些数组操作设置在。这些数组操作设置在j j 循环中实施。循环中实施。n 实施竖式除法模拟操作实施竖式除法模拟操作:被除数为被除数为c c，除数，除数d d分别取分别取2n+1,2n2n+1,2n1,31,3。商仍存放在各数组元素。商仍存放在各数组元素(a(i)=c/d)(a(i)=c/d)。余数余数(c%d)(c%d)乘乘1010加在后一数组元素加在后一数组元素a(i+1)a(i+1)上，作为后一位上，作为后一位的被除数。的被除数。n 竖式乘模拟操作：乘数竖式乘模拟操作：乘数j j分别取分别取n,nn,n1

19、,11,1。乘积要注。乘积要注意进位，设进位数为意进位，设进位数为b b，则对计算的积，则对计算的积a(i)=a(i)a(i)=a(i)*j+bj+b，取，取其十位以上数作为进位数其十位以上数作为进位数b=a(i)/10b=a(i)/10，取其个位数仍存放，取其个位数仍存放在原数组元素在原数组元素a(i)=a(i)%10a(i)=a(i)%10。（3）竖式乘除模拟）竖式乘除模拟n for(c=1,j=n;j=1;j-)/for(c=1,j=n;j=1;j-)/按公式分步计算按公式分步计算n n次次 n d=2d=2*j+1;j+1;n for(i=0;i=x+4;i+)for(i=0;i=0;

20、i-)for(b=0,i=x+5;i=0;i-)/各位实施乘各位实施乘j j n a(i)=a(i)a(i)=a(i)*j+b;b=a(i)/10;a(i)=a(i)%10;j+b;b=a(i)/10;a(i)=a(i)%10;n a(0)=a(0)+1;c=a(0);a(0)=a(0)+1;c=a(0);/整数位加整数位加1 1 n nfor(b=0,i=x+5;i=0;i-)for(b=0,i=x+5;i=0;i-)/按公式各位乘按公式各位乘2 2 n a(i)=a(i)a(i)=a(i)*2+b;b=a(i)/10;a(i)=a(i)%10;2+b;b=a(i)/10;a(i)=a(i)

21、%10;2.竖式乘除模拟描述竖式乘除模拟描述 n3.3.输出结果输出结果n 循环实施竖式乘除模拟完成后，按数组元素循环实施竖式乘除模拟完成后，按数组元素从高位到低位顺序输出。因计算位数较多，为从高位到低位顺序输出。因计算位数较多，为方便查对，每一行控制打印方便查对，每一行控制打印5050位，每位，每1010位空一位空一格。格。n4.4.复杂度分析复杂度分析n 以上综合竖式乘除模拟的时间复杂度以上综合竖式乘除模拟的时间复杂度O(nlogn)O(nlogn)，其中，其中n n为所需计算的位数，为所需计算的位数，loglogn n约为约为所需计算的项数。所需计算的项数。n 案例提出 n 法国数学家泊

22、松法国数学家泊松(Poisson)(Poisson)曾提出以下分酒趣题：曾提出以下分酒趣题：某人有一瓶某人有一瓶1212品脱品脱(容量单位容量单位)的酒，同时有容积为的酒，同时有容积为5 5品脱与品脱与8 8品脱的空杯各一个。借助这两个空杯，如品脱的空杯各一个。借助这两个空杯，如何将这瓶何将这瓶1212品脱的酒平分品脱的酒平分?n 我们要解决一般的平分酒案例：借助容量分别为我们要解决一般的平分酒案例：借助容量分别为bvbv与与cvcv（单位为整数）的两个空杯，用最少的分倒（单位为整数）的两个空杯，用最少的分倒次数把总容量为偶数次数把总容量为偶数a a的酒平分。这里正整数的酒平分。这里正整数bv

23、bv，cvcv与偶数与偶数a a均从键盘输入。均从键盘输入。nkkwklwpl1)()(n 求解一般的求解一般的“泊松分酒泊松分酒”问题：借助容积分别问题：借助容积分别为整数为整数bv,cvbv,cv的两个空杯，用最少的分倒次数把总的两个空杯，用最少的分倒次数把总容量为偶数容量为偶数a a的酒的酒(并未要求满瓶并未要求满瓶)平分，采用直接平分，采用直接模拟平分过程的分倒操作。模拟平分过程的分倒操作。n 为了把输入的偶数为了把输入的偶数a a通过分倒操作平分为两个通过分倒操作平分为两个i:i:i=a/2i=a/2（i i为全局变量），设在分倒过程中：为全局变量），设在分倒过程中：n 瓶瓶A A中

24、的酒量为中的酒量为a,(0a2a,(0a2*i);i);n 杯杯B(B(容积为容积为bv)bv)中的洒量为中的洒量为b,(0bbv);b,(0bbv);n 杯杯C(C(容积为容积为cv)cv)中的酒量为中的酒量为c,(0ccv);c,(0ccv);2模拟设计要点模拟设计要点n（1 1）按）按A ABBCC顺序分倒操作顺序分倒操作n 当当B B杯空杯空(b=0)(b=0)时，从时，从A A瓶倒满瓶倒满B B杯。杯。n 从从B B杯分一次或多次倒满杯分一次或多次倒满C C杯。杯。若若bcvbcvc c，倒满，倒满C C杯，操作杯，操作 若若bcvbcvc,c,倒空倒空B B杯，操作杯，操作n 当当

25、C C杯满杯满(c=cv)(c=cv)时，从时，从C C杯倒回杯倒回A A瓶。瓶。n 分倒操作，用变量分倒操作，用变量n n统计分倒次数，每分倒一次，统计分倒次数，每分倒一次，n n增增1 1。n 若若b=0b=0且且abvacvelse if(bcvc)bc)b=(cv=(cvc);c=cv;c);c=cv;/从从B B倒满倒满C C杯杯 n else c+=b;b=0;else c+=b;b=0;n /从从B B倒倒C C，倒空，倒空B B杯杯 n printf(%6d%6d%6dn,a,b,c);printf(%6d%6d%6dn,a,b,c);n 2.模拟操作描述模拟操作描述n 这一循

26、环操作与（这一循环操作与（1 1）实质上是）实质上是C C与与B B杯互换，杯互换，相当于返回函数值相当于返回函数值Probe(a,cv,bv)Probe(a,cv,bv)。n 试验函数试验函数Probe()Probe()的引入是巧妙的，可综合摸拟的引入是巧妙的，可综合摸拟以上两种分倒操作避免了关于以上两种分倒操作避免了关于cvcv与与bvbv大小关系的大小关系的讨论。讨论。n 同时设计实施函数同时设计实施函数Practice(a,bv,cv)Practice(a,bv,cv)，与试验，与试验函数相比较，把函数相比较，把n n增增1 1操作改变为输出中间过程量操作改变为输出中间过程量a a、b

27、 b、c c，以标明具体操作进程。，以标明具体操作进程。3.按按ACB顺序分倒操作顺序分倒操作n 本章应用竖式乘除模拟非常简捷地解决了高精本章应用竖式乘除模拟非常简捷地解决了高精度整除问题的乘数探求、尾数前移问题、阶乘、度整除问题的乘数探求、尾数前移问题、阶乘、幂、排列与组合数的高精计算，同时求解了圆周幂、排列与组合数的高精计算，同时求解了圆周率率 的指定位数的计算。的指定位数的计算。n 这些案例所求解的，既有整数，也有实数。其这些案例所求解的，既有整数，也有实数。其中有些案例，既可以应用竖式乘模拟求解，也可中有些案例，既可以应用竖式乘模拟求解，也可以应用竖式除模拟来求解，有些案例需综合应用以

28、应用竖式除模拟来求解，有些案例需综合应用竖式乘、除模拟来求解。如果应用我们前面介绍竖式乘、除模拟来求解。如果应用我们前面介绍的递推、递归、回溯或动态规划等算法来求解这的递推、递归、回溯或动态规划等算法来求解这些案例，不容易奏效。些案例，不容易奏效。应用竖式模拟注意点应用竖式模拟注意点n 注意联系案例的具体实际设置被除数、除数与注意联系案例的具体实际设置被除数、除数与商等模拟量。试商过程中被除数的确立比较灵活。商等模拟量。试商过程中被除数的确立比较灵活。n（1 1）在在“积为若干个积为若干个”求解时，被除数为：求解时，被除数为：a=ca=c*10+1;10+1;（因为每一位均为（因为每一位均为1

29、 1）。）。n（2 2）在在“积为若干个积为若干个2017”2017”的求解时，被的求解时，被除数变为：除数变为：a=ca=c*10000+201710000+2017。n（3 3）在在“积为任意指定构成积为任意指定构成”的求解时，被除的求解时，被除数变为：数变为：a=ca=c*10+d(j);10+d(j);其中其中d(j)d(j)为某一位数。为某一位数。n（4 4）在在“尾数前移尾数前移“的求解时，被除数又变为：的求解时，被除数又变为：a=ca=c*10+b;10+b;其中其中b b为上一轮试商的商。为上一轮试商的商。应用随机函数模拟注意点应用随机函数模拟注意点n 要注意随机函数发生器的初

30、始化，以避免雷同要注意随机函数发生器的初始化，以避免雷同之外，也要注意联系问题的具体实际，控制随机之外，也要注意联系问题的具体实际，控制随机数的范围。数的范围。n 例如，在模拟发扑克牌时，例如，在模拟发扑克牌时，x x代表代表4 4花色，花色，y y代表每色的代表每色的1313点，应用点，应用 x=rand()%4+1;y=rand()%13+2;x=rand()%4+1;y=rand()%13+2;来实现是适合的。来实现是适合的。rand()%4rand()%4的值为的值为0,1,2,3,0,1,2,3,则则rand()%4+1rand()%4+1的值为的值为1,2,3,4,1,2,3,4,共共4 4 个，代表个，代表4 4花色。花色。rand()%13rand()%13的值为的值为0,1,12,0,1,12,则则y=rand()%13+2y=rand()%13+2的值为的值为2,3,14,2,3,14,共共1313个，分个，分别代表别代表1313个点数（其中个点数（其中1414为为“A”A”点）。点）。