《第7章 模拟【课堂使用】》由会员分享，可在线阅读，更多相关《第7章 模拟【课堂使用】（30页珍藏版）》请在金锄头文库上搜索。
1、1基础教学基础教学基础教学基础教学2基础教学基础教学基础教学基础教学 7.1 模拟概述模拟概述应用计算机程序设计模拟自然界的随机现象，模拟特定应用计算机程序设计模拟自然界的随机现象，模拟特定条件下的操作过程，是程序设计难以把握且颇具魅力的条件下的操作过程，是程序设计难以把握且颇具魅力的课题之一。课题之一。 根据模拟对象的不同特点，计算机模拟可分为决定性模根据模拟对象的不同特点，计算机模拟可分为决定性模拟与随机性模拟。拟与随机性模拟。决定性模拟是对决定性过程进行的模拟，其模拟的事件决定性模拟是对决定性过程进行的模拟，其模拟的事件 按其固有的规律发生发展。按其固有的规律发生发展。例如运算模拟就是决
2、定性模拟。例如运算模拟就是决定性模拟。随机性模拟的对象是随机事件，利用随机数作为参数实随机性模拟的对象是随机事件，利用随机数作为参数实施模拟。施模拟。 例如数字模拟（又称数字仿真）。例如数字模拟（又称数字仿真）。3基础教学基础教学基础教学基础教学 运算模拟是按整数的四则运算法则进行模拟操运算模拟是按整数的四则运算法则进行模拟操作，最后得出模拟运算的结果。作，最后得出模拟运算的结果。7.2.1 运算模拟描述运算模拟描述 运算模拟，主要是模拟整数逐位乘除的运算过运算模拟，主要是模拟整数逐位乘除的运算过程，求解一些整数计算问题。程，求解一些整数计算问题。 在实施乘除运算模拟之前，必须根据参与运算在实
3、施乘除运算模拟之前，必须根据参与运算整数的实际设置模拟量，以模拟乘除运算进程中数整数的实际设置模拟量，以模拟乘除运算进程中数值的变化，并判定运算是否结束。值的变化，并判定运算是否结束。7.2 运算模拟运算模拟4基础教学基础教学基础教学基础教学1. 模拟除法运算模拟除法运算 除运算模拟框架描述：输入输入 确定确定 while(while() a=c*10+m; /* a=c*10+m; /* 构造被除数构造被除数a a，m m为为 */ */b=a/p; /* b=a/p; /* 实施除运算实施除运算, ,计算商计算商b */b */printf(b);printf(b);c=a%p; /* c
4、=a%p; /* 试商得余数试商得余数c */c */ 其中,与必须根据模拟除运算问题的具体实际确定。5基础教学基础教学基础教学基础教学乘运算模拟框架描述：输入输入 确定确定 while(while() k=k+1; k=k+1; a=w(k)*p+m; /* a=w(k)*p+m; /* 计算乘积计算乘积a a，m m为为 */ */ w(k)=a%10; /* w(k)=a%10; /* 积积a a的个位存储到的个位存储到w(k) */w(k) */ m=a/10; /* m=a/10; /* 积积a a的十位以上作为进位数的十位以上作为进位数 * */ / 输出输出(w(d),w(d-1
5、),(w(d),w(d-1),w(1); ,w(1); /* /* 高位到低位输出高位到低位输出 * */ /乘运算模拟的,与根据模拟乘运算问题的实际确定。2. 模拟乘法运算模拟乘法运算6基础教学基础教学基础教学基础教学1. n个个1被被2009整除问题整除问题【例例7.17.1】 一个由一个由n n个个1 1组成的整数能被组成的整数能被20092009整除，整除，n n至少为多大？至少为多大？模拟除运算设计模拟除运算设计 :被除数为被除数为a, 除数除数p=2009，每次试商的余数为，每次试商的余数为c。被除数被除数a=c*10+1,每次试商所得余数为每次试商所得余数为c=a%2009。设置
6、初始值设置初始值c=1111,n=4，进入模拟整除循环。，进入模拟整除循环。循环条件为循环条件为c0。每循环一次，变量。每循环一次，变量n增增1。若余数若余数c=0,结束结束,输出输出n的值。的值。 7.2.2 n个个1的整除问题的整除问题7基础教学基础教学基础教学基础教学 void main()void main() int a,c,n; int a,c,n; c=1111;n=4; /* c=1111;n=4; /* 确定初始值确定初始值 * */ / while(c!=0) while(c!=0) a=c*10+1; /* a=c*10+1; /* 构造被除数构造被除数a */a */
7、c=a%2009; n+; c=a%2009; n+; /* /* 实施除运算实施除运算, ,得余数得余数c */ c */ printf( printf(至少至少%d%d个个1.n,n);1.n,n); 8基础教学基础教学基础教学基础教学2. 积为积为n个个1的数字游戏的数字游戏 【例例7.2】 两位计算机爱好者在进行两位计算机爱好者在进行“积为积为n个个1的数字游戏的数字游戏”：其中一位给定一个正整数：其中一位给定一个正整数p(约定整数约定整数p为个位数字不为个位数字不是是5的奇数的奇数)，另一位寻求正整数，另一位寻求正整数q，使得，使得p与与q之积为全是之积为全是1组成的整数组成的整数.
8、模拟除运算设计模拟除运算设计:设整数除运算每次试商的被除数为设整数除运算每次试商的被除数为a, 除数为除数为p（即给定的（即给定的正整数）正整数）,每次试商的商为每次试商的商为b，相除的余数为，相除的余数为c。被除数被除数a=c*10+1,余数余数c=a%p,商商b=a/p即为所寻求数即为所寻求数q的的一位。若余数一位。若余数c=0,结束；否则，继续运算直到结束；否则，继续运算直到c=0为止。为止。 9基础教学基础教学基础教学基础教学void main()void main() int a,b,c,p,n; int a,b,c,p,n;printf(nprintf(n请输入整数请输入整数p:)
9、; p:); scanf(%d,&p);scanf(%d,&p);printf(nprintf(n寻求的整数寻求的整数q=);q=);n=3; c=111; /* n=3; c=111; /* 确定初始值确定初始值 * */ /while(c!=0)while(c!=0) a=c*10+1; a=c*10+1; c=a%p; b=a/p; n+; /* c=a%p; b=a/p; n+; /* 实施除运算模拟实施除运算模拟 * */ / printf(%d,b); /* printf(%d,b); /* 输出整数输出整数q q的一位数的一位数 * */ /printf(nprintf(n乘积乘
10、积p*qp*q为为%d%d个个1.n,n);1.n,n); 10基础教学基础教学基础教学基础教学7.2.3 尾数前移问题尾数前移问题【例7.3】 整数n的尾数是9，把尾数9移到其前面(成为最高位)后所得的数为原整数n的3倍，原整数n至少为多大?这是这是数学通报数学通报上发表的一个具体的尾数前移问题。上发表的一个具体的尾数前移问题。我们要求解一般的尾数前移问题我们要求解一般的尾数前移问题: :整数整数n n的尾数的尾数q(q(限为一位限为一位) )移到移到n n的前面所得的数为的前面所得的数为n n的的p p倍倍, ,记为记为n(q,p)n(q,p)。这里约定。这里约定。对于指定的尾数对于指定的
11、尾数q q与倍数与倍数p,p,求解求解n(q,p)n(q,p)。下面试用模拟除运算与模拟乘运算两种方法设计求解。下面试用模拟除运算与模拟乘运算两种方法设计求解。 11基础教学基础教学基础教学基础教学1. 模拟整数除法首先第一位数首先第一位数q q除以除以p(p(注意约定注意约定qp),qp),余数为余数为c,c,商商为为b b。输出数字。输出数字b b作为所求作为所求n n的首位数。的首位数。进入模拟循环，当余数进入模拟循环，当余数c=0c=0且商且商b=qb=q时结束，因而时结束，因而循环条件为循环条件为c!=0 | b!=qc!=0 | b!=q。在循环中计算被除数在循环中计算被除数a=c
12、*10+ba=c*10+b，试商得，试商得b=a/p, b=a/p, 输输出作为所求出作为所求n n的一位的一位b b；求得余数；求得余数c=a%pc=a%p；然后；然后b b与与c c构建下一轮试商的被除数，依此递推。构建下一轮试商的被除数，依此递推。 12基础教学基础教学基础教学基础教学void main()void main() int a,b,c,p,q; int a,b,c,p,q; scanf(%d,%d,&q,&p); /* scanf(%d,%d,&q,&p); /* 输入数据输入数据q,p */q,p */ b=q/p;c=q%p; /* b=q/p;c=q%p; /* 确定
13、初始条件确定初始条件 * */ / printf(n(%d,%d)=%d,q,p,b); /* printf(n(%d,%d)=%d,q,p,b); /* 输出输出n n的首位的首位b */b */ while(c!=0 | b!=q) /* while(c!=0 | b!=q) /* 试商循环处理试商循环处理 * */ / a=c*10+b; a=c*10+b; b=a/p;c=a%p; /* b=a/p;c=a%p; /* 模拟整数除法模拟整数除法 * */ / printf(%d,b); printf(%d,b); 13基础教学基础教学基础教学基础教学设置存储数设置存储数n n的的w w
14、数组。数组。从从w(1)=qw(1)=q开始，乘数开始，乘数p p与与n n的每一位数字的每一位数字w(i)w(i)相乘后相乘后加进位数加进位数m ,m ,得得a=w(k)*p+m; a=w(k)*p+m; 积积a a的十位以上的数作为下一轮的进位数的十位以上的数作为下一轮的进位数 m=a/10;m=a/10;而而a a的个位数此时需赋值给乘积的下一位的个位数此时需赋值给乘积的下一位w(i+1)=x%10w(i+1)=x%10。当计算的被除数当计算的被除数a a为尾数为尾数q q时结束。时结束。2. 模拟整数乘法14基础教学基础教学基础教学基础教学void main()void main()
15、int a,m,j,k,p,q,w100; int a,m,j,k,p,q,w100; scanf(%d,%d,&q,&p); scanf(%d,%d,&q,&p); for(j=1;j100;j+) wj=0; /* for(j=1;j=1;j-) /* for(j=k-1;j=1;j-) /* 从高位到低位打印从高位到低位打印 * */ / printf(%d,wj); printf(%d,wj); printf(n printf(n 共共%d %d 位。位。n,k-1);n,k-1); 15基础教学基础教学基础教学基础教学7.2.5 求圆周率关于圆周率关于圆周率的计算的计算,历史非常久远
16、。我国历史非常久远。我国数学家祖冲之最先把圆周率数学家祖冲之最先把圆周率计算到计算到3.1415926,领先世界一千多年。尔后领先世界一千多年。尔后;德国数学家鲁特尔夫把德国数学家鲁特尔夫把计算到小数点后计算到小数点后35位位;日本数学家建部贤弘计算到日本数学家建部贤弘计算到41位。位。1874年英国数学家香克斯利用微积分倾年英国数学家香克斯利用微积分倾毕生精力把毕生精力把计算到计算到707位位,但但528位后的位后的数值是错的。数值是错的。 16基础教学基础教学基础教学基础教学 17基础教学基础教学基础教学基础教学18基础教学基础教学基础教学基础教学（3） 模拟乘除综合运算 设置设置a数组数
17、组, 计算的整数值存放在计算的整数值存放在a(0),小数点后第小数点后第i位存放位存放在在a(i)中中(i=1,2,.)。 依据公式（依据公式（7.1）,应用模拟乘除运算进行计算：应用模拟乘除运算进行计算： 数组赋初值数组赋初值a(0)=1后后: 除以除以2n+1,乘以乘以n,加上加上1; 再除以再除以2n-1,乘以乘以n-1,加上加上1;.这些数组操作设置在循环中实施。这些数组操作设置在循环中实施。 19基础教学基础教学基础教学基础教学模拟乘除运算描述：模拟乘除运算描述：for(c=1,j=n;j=1;j-) /* for(c=1,j=n;j=1;j-) /* 按公式分步计算按公式分步计算n
18、 n次次 * */ / d=2*j+1; d=2*j+1; for(i=0;i=x+4;i+) /* for(i=0;i=0;i-) /* for(b=0,i=x+5;i=0;i-) /* 各位实施乘各位实施乘j */j */ a(i)=a(i)*j+b; b=a(i)/10;a(i)=a(i)%10; a(i)=a(i)*j+b; b=a(i)/10;a(i)=a(i)%10; a(0)=a(0)+1;c=a(0); /* a(0)=a(0)+1;c=a(0); /* 整数位加整数位加1 */1 */ for(b=0,i=x+5;i=0;i-) /* for(b=0,i=x+5;i=0;i-
19、) /* 按公式各位乘按公式各位乘2 */2 */ a(i)=a(i)*2+b; a(i)=a(i)*2+b; b=a(i)/10;a(i)=a(i)%10; b=a(i)/10;a(i)=a(i)%10; 20基础教学基础教学基础教学基础教学 (4) (4) 输出结果输出结果循环实施除乘操作完成后循环实施除乘操作完成后, ,按数组元素从高位到低按数组元素从高位到低位顺序输出。因计算位数较多位顺序输出。因计算位数较多, ,为方便查对为方便查对, ,每一每一行控制打印行控制打印5050位位, ,每每1010位空一格。位空一格。（5 5） 复杂度分析复杂度分析以上模拟乘除运算算法的时间复杂度以上模
20、拟乘除运算算法的时间复杂度O(nlogn)O(nlogn)，其中其中n n为所需计算的位数，为所需计算的位数，lognlogn约为所需计算的项约为所需计算的项数。数。 21基础教学基础教学基础教学基础教学 7.3.3 模拟发扑克牌模拟发扑克牌【例7.8】 模拟扑克升级发牌，把含有大小王的共54张牌随机分发给4家，每家12张，底牌保留6张。 (1) 模拟花色与点数模拟发牌必须注意随机性模拟发牌必须注意随机性,不可重复性。不可重复性。对应四种花色对应四种花色, 设置随机整数设置随机整数x，对应取值为，对应取值为1-4。对应每种花色的对应每种花色的13点点,设置随机整数设置随机整数y，对应取值为，对
21、应取值为1-13。为避免重复为避免重复,把把x与与y组合为三位数：组合为三位数：z=x*100+y,并存放在数组并存放在数组m(54)中。中。为发第为发第i+1张牌，产生数张牌，产生数z与已有的与已有的m(0),m(1),.m(i-1)逐一进行比较逐一进行比较.若不相同发一张牌，然后赋值给若不相同发一张牌，然后赋值给m(i)，作为以后发牌的比较之用。，作为以后发牌的比较之用。若有相同的若有相同的,则重新产生随机整数则重新产生随机整数x与与y得得z进行比较。进行比较。 7.3 随机模拟随机模拟22基础教学基础教学基础教学基础教学(2) 模拟大小王注意到在升级扑克中有大小王，大小王的出现也是随机的
22、注意到在升级扑克中有大小王，大小王的出现也是随机的.把随机整数把随机整数y的取值放宽到的取值放宽到013，则，则z可能有可能有 100, 200，300，400。定义定义z=200时对应大王，时对应大王，z=100时对应小王时对应小王, 同上作打印同上作打印与赋值处理与赋值处理 。若若z=300或或400,则返回重新产生则返回重新产生x与与y。23基础教学基础教学基础教学基础教学(3) 设置比较循环避免重复在已产生i张牌并存储在m数组中，产生第i+1张牌：for(j=1;j=10000;j+)for(j=1;j=10000;j+) x=rand()%4+1; y=rand()%14; x=ra
23、nd()%4+1; y=rand()%14; z=x*100+y; z=x*100+y; if(z=300 | z=400) continue; if(z=300 | z=400) continue; t=0; t=0; for(k=0;k=i-1;k+) for(k=0;k=i-1;k+) if(z=mk) t=1;break; if(z=mk) t=1;break; if(t=0) if(t=0) mi=z;break; mi=z;break; 24基础教学基础教学基础教学基础教学(4) 打印输出打印直接应用C语言中ASCII码16的字符显示大小王与各花色。设置字符数组d，打印点数时把y=
24、1，13，12，11分别转化为A，K，Q，J。为实现真正的随机,根据时间的不同,设置t=time()%10000;srand(t) 初始化随机数发生器,从而达到真正随机的目的。25基础教学基础教学基础教学基础教学7.4 操作过程模拟操作过程模拟【例例7.107.10】 法国数学家泊松法国数学家泊松(Poisson)(Poisson)曾提出以下分酒曾提出以下分酒趣题：某人有一瓶趣题：某人有一瓶1212品脱品脱( (容量单位容量单位) )的酒，同时有容积为的酒，同时有容积为5 5品脱与品脱与8 8品脱的空杯各一个。借助这两个空杯，如何将这品脱的空杯各一个。借助这两个空杯，如何将这瓶瓶1212品脱的
25、酒平分品脱的酒平分? ? 我们要解决一般的平分酒问题：借助容量分别为我们要解决一般的平分酒问题：借助容量分别为bvbv与与cv(cv(单位为整数单位为整数) )的两个空杯的两个空杯, ,用最少的分倒次数把总容量用最少的分倒次数把总容量为偶数为偶数a a的酒平分。这里正整数的酒平分。这里正整数bv,cvbv,cv与偶数与偶数a a均从键盘输均从键盘输入入。7.4.2 泊松分酒泊松分酒26基础教学基础教学基础教学基础教学设设 i=a/2(ii=a/2(i为全局变量为全局变量),),设在分倒过程中设在分倒过程中: : 瓶瓶A A中的酒量为中的酒量为a,(0=a=2*i);a,(0=a=2*i); 杯
26、杯B(B(容积为容积为bv)bv)中的洒量为中的洒量为b,(0=b=bv);b,(0=b=bv); 杯杯C(C(容积为容积为cv)cv)中的酒量为中的酒量为c,(0=c=cv);c,(0=cB-CA-B-C顺序操作顺序操作 当当B B杯空杯空(b=0)(b=0)时，从时，从A A瓶倒满瓶倒满B B杯。杯。 从从B B杯分一次或多次倒满杯分一次或多次倒满C C杯。杯。 bcv-c,bcv-c,倒满倒满C C杯，操作杯，操作 b=cv-c,b=cv-c,倒空倒空B B杯，操作杯，操作 当当C C杯满杯满(c=cv)(c=cv)时，从时，从C C杯倒回杯倒回A A瓶。瓶。27基础教学基础教学基础教学
27、基础教学 若若b=0b=0且且abvacv-c) else if (bcv-c) b-=(cv-c);c=cv;/* b-=(cv-c);c=cv;/* 从从B B倒满倒满C C杯杯 * */ / else c+=b;b=0; /* else c+=b;b=0; /* 从从B B倒倒C C，倒空，倒空B B杯杯 * */ / printf(%6d%6d%6dn,a,b,c); printf(%6d%6d%6dn,a,b,c); 28基础教学基础教学基础教学基础教学(2) (2) 按按A-C-BA-C-B顺序操作顺序操作这一循环操作与这一循环操作与(1)(1)实质上是实质上是C C与与B B杯互
28、换，杯互换， 相当相当于返回函数值于返回函数值Probe(a,cv,bv)Probe(a,cv,bv)。同时设计实施函数同时设计实施函数Practice(a,bv,cv),Practice(a,bv,cv),与试验函与试验函数相比较，把数相比较，把n n增增1 1操作改变为输出中间过程量操作改变为输出中间过程量a,b,c,a,b,c,以标明具体分倒操作进程。以标明具体分倒操作进程。在主函数在主函数main()main()中，分别输入中，分别输入a,bv,cva,bv,cv的值后，为的值后，为寻求较少的分倒次数，调用试验函数并比较寻求较少的分倒次数，调用试验函数并比较m1=Probe(a,bv,cv)m1=Probe(a,bv,cv)与与m2=Probe(a,cv,bv);m2=Probe(a,cv,bv);实施函数实施函数Practice(a,cv,bv)Practice(a,cv,bv)打印整个模拟分倒操打印整个模拟分倒操作进程中的作进程中的a,b,ca,b,c。 29基础教学基础教学基础教学基础教学上机:1. n个1的整除问题2. 尾数前移问题3. 求圆周率4. 模拟发扑克牌5. 泊松分酒作业: 1,3 (设计程序上机通过)30基础教学基础教学基础教学基础教学
