常用算法与程序设计第7章 模拟.ppt

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