算法设计与分析实用教程杨克昌 第8章 模拟

《算法设计与分析实用教程杨克昌 第8章 模拟》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学要求掌握竖式乘除模拟设计要领并应用解决多位整数与指定精度的小数等高精度计算案例掌握应用随机函数模拟设计求解自然界的随机现象本章重点根据案例的实际选择与确定模拟量第8章模拟算法8.1.1模拟分类1.随机模拟随机性模拟的对象是随机事件，其变化过程相当复杂。随机模拟要利用计算机语言提供的随机函数，设定某一范围内的随机值，并将这些随机值作为参数实施模拟。例如数字模拟（又称数字仿真），可进行一些疑难定积分的近似计算。2.决定性模拟决定性模拟是对决定性过程进行的模拟，其模拟的事件按其固有规律发生发展，最终得出一

2、个明确的结果。例如，乘除竖式计算模拟就是决定性模拟。8.1模拟概述8.1.2竖式运算模拟竖式乘除模拟是按整数的四则运算法则进行模拟操作，最后得出运算的结果。竖式乘除模拟，主要是模拟整数逐位乘或除的竖式计算过程，求解一些整数计算与判定问题。在实施乘除竖式计算模拟之前，必须根据参与运算整数的实际设置模拟量，以模拟乘除竖式计算进程中数值的变化，并判定运算是否结束。竖式除模拟，设竖式除过程中被除数为a，除数为p，试商所得的商为b=a/p，所得余数为c=a%p。实施模拟，可根据问题的具体实际设置模拟循环，并确定终止循

3、环的条件。例如，以试商的余数是否为0作为运算是否完成的终止条件：当c≠0时，继续试商下去，直至余数c=0时，实现整除，终止模拟。竖式除模拟框架描述：输入<原始数据>；确定<初始量>；while(<循环条件>){a=c*t+m;//构造被除数ab=a/p;//实施除运算,计算商bprintf(b);c=a%p;//试商得余数c}1.竖式除模拟通常设w数组表示乘运算的一个乘数，也表示该数乘以p（另一个乘数）的积：w(1)表示个位数，w(2)为十位数，…。实施竖式乘模拟必须考虑进位。设进位数为m并赋初值，显然，乘

4、数的第k位数w(k)乘以另一个乘数p的结果为a=w(k)*p+m，然后把所得到的乘积a的个位数存储为积的第k位数：w(k)=a%10；而a的十位及以上的值做为下轮运算的进位数：m=a/10。w数组（一个乘数）与进位数m的初值、乘运算的结束条件由所求问题的具体实际确定，通常使乘运算达到某一特定值或达到某一规定位数后结束。2.竖式乘模拟竖式乘模拟框架描述：输入<原始数据>确定<初始量>while(<循环条件>){k=k+1;a=w(k)*p+m;//计算乘积a，m为<进位数>w(k)=a%10;//乘积a的个位

5、存储到w(k)m=a/10;//乘积a的十位以上作为下轮的进位数}输出(w(d：1));//从高位到低位输出乘积两位计算机爱好者A、B在老师C的指导下进行乘数探求：A：请你任给定一个正整数p（约整数p为个位数字不是5的奇数），我可寻求正整数q，使得p与q之积为全是“1”组成的整数。B：也请你任给定一个正整数p（同样约定整数p为个位数字不是5的奇数），我可寻求正整数q，使得p与q之积为全是由“2014”组成的整数。C：可以适当拓广，当积的构成由键盘任意指定时，继续你们的乘数探求。请完成以上三例乘数探求设计。8

6、.2乘数探求1.竖式除模拟设计设整数除竖式计算每次试商的被除数为a，除数为p（即给定的正整数），每次试商的商为b，相除的余数为c。以余数c≠0作为条件设置条件循环，循环外赋初值：c=1111,n=4;或c=111,n=3等等。被除数a=c*10+1，试商余数c=a%p，商b=a/p即为所寻求数q的一位。若余数c=0，结束；否则，继续下一轮试商，直到c=0为止。每商一位，设置变量n统计积中“1”的个数，同时输出商b（整数q的一位数）。8.2.1积为若干个1构成scanf("%d",&p);n=4;c=1111

7、;//确定初始值while(c!=0){a=c*10+1;c=a%p;b=a/p;n++;//实施除乘竖式计算模拟printf(“%d”,b);//输出整数q的一位数}printf("乘积p*q为%d个1.",n);2.竖式除模拟设计描述8.2.2积为若干个2014构成1.竖式除模拟设计模拟循环前输出所寻求的数q的前几位为2014/p；同时赋初值n=1;（即积有1个“2004”）,c=2014%p;竖式除模拟条件（c≠0）循环，对每个“2014”试商：被除数为：a=c*10000+2014;余数为：

8、c=a%p;商为b=a/p;统计“2014”个数的变量n增1；输出商必须为4位：printf("%04d",b);当余数c=0时，结束试商循环，输出“2014”个数n,结束。scanf("%ld",&p);n=1;b=2014/p;c=2014%p;//确定初始值if(b>0)printf("%ld",b);while(c!=0){a=c*10000+2014;c=a%p;b=a/p;//实施除竖式计算模拟pri