14 编程例题.ppt

第1页：第十四讲编程例题封面

本页为第十四讲 编程例题封面，本讲包含三个例题：用变步长梯形法与辛普生公式求定积分、随机数与蒙特卡罗法求几何面积、整数分拆求最大乘积。

第2页：梯形公式求面积

求定积分

1、用梯形公式计算面积的近似值。这样计算面积误差太大。

第3页：变步长梯形法

2、改进：将区间 b-a 划分成 2n 等分。用变步长的梯形法，定义 Tn 为将积分区间 n 等分时求出的近似面积。

第4页：划分示意图

本页为区间划分后的示意图，图中给出划分后的分点与中线位置。

第5页：面积的两部分

1. （1）为按公式算出的面积的二分之一
2. （2）为等分中线的函数值 f(x1+h/2) 与 h 的乘积，得出面积的二分之一

第6页：合并后的面积

（3）代表面积，即上述两部分合并后的定积分近似面积。

第7页：辛普生公式

3、用辛普生公式计算积分的近似值。

第8页：求积分程序的定义部分

#include <stdio.h>#include <math.h>double f(double x);void main(){ int k,n=1; double x,x1=0,x2=2; double s,h,tn,t2n,In,I2n; const double eps=1e-6; h=x2-x1; t2n=I2n=(h*(f(x1)+f(x2)))/2; printf("第一次近似计算梯形面积值为%lf\n",t2n); In=0;

第9页：求积分程序的循环

while(fabs(I2n-In)>=eps){ tn=t2n; In=I2n; s=0.0; for(k=0;k<n;k=k+1) { x=x1+(k+0.5)*h; s=s+f(x); } t2n=(tn+h*s)/2.0; I2n=(4*t2n-tn)/3.0;

第10页：求积分程序的收尾

 n=2*n; h=h/2; }printf("积分值为%lf\n",I2n);}double f(double x){ return ( (exp(x)+x*x)/(1+x*x*x));} 
第11页：随机数的用法
随机数
说明：
要产生随机数需要在预编译中加入库函数 #include <stdlib.h>
rand() 是产生随机数的函数，它可生成 0 至 32767 的整数
最大随机数为 RAND_MAX，值为 32767
产生随机数需要设置种子 srand((unsigned)time(NULL)); 因为时间每分每秒不同，第一个随机数就不会固定。你可以做试验，如去掉这条，产生十个随机数，每次都会是一样的
第12页：十个随机数的示例
产生的随机数：
41 18467 6334 26500 19169 15724 11478 29358 26962 24464
加上 srand((unsigned)time(NULL)); 这条之后，你再观察，每一次出的十个数都不同。
第13页：随机函数4.c程序
#include <stdio.h>#include <math.h>#include <stdlib.h>void main(void){ int k; srand( (unsigned)time(NULL)); for(k=0;k<10;k=k+1) { printf("%f\n",(float)rand()/RAND_MAX); } printf("最大随机数为%d\n",RAND_MAX);} 
第14页：产生随机小数的说明
说明：
用 rand() / RAND_MAX 来产生大于 0 而小于 1 的小数
因为 rand() 是整型数，RAND_MAX 是整型常数，两者相除，如不作特殊处理得不出小数，只能为 0，因为被除数小于除数。因此需要强制转换数据类型，在除式前加 (float)，即 (float) rand() / RAND_MAX
第15页：蒙特卡罗法求π
例：求 π 的近似值。如右图，正方形的面积 A=1；1/4 圆的面积 B=π/4。我们想象有一个容器在正方形中夹有一个极薄的圆弧隔板。下小雨时搬至屋外，经一定时间后，称 1/4 圆的容器内的水重 C，与作为一个整体的正方形中的水重 D。C 与 D 之比应该等于 B 与 A 之比，即可得 π 的近似值。
伪随机数的应用——蒙特卡罗法求几何面积。
第16页：用伪随机数模拟雨点
我们让计算机产生伪随机数 x 和 y，让 x 的值的范围在 0～1 之间；让 y 的值的范围也在 0～1 之间，模拟雨点落在正方形中，当然会有的雨点落在 1/4 圆中，数以百万计雨点可以累计得到 C 和 D，从而用上述公式算出 π 的近似值。
这里关键是落入扇形区的判据：如果满足了 sqrt(x*x+y*y)<=1，则让 C=C+1。参考程序见“随机函数1.c”。
第17页：蒙特卡罗法求π的程序
#include <iostream.h>#include <math.h>#include <stdlib.h>void main(void){ long k,c=0,d=0; float pai,x,y; srand( (unsigned)time(NULL)); for(k=1;k<=100000000;k=k+1) { d=d+1; x=(float)rand()/32767; y=(float)rand()/32767; if(sqrt(x*x+y*y)<=1)c=c+1; } pai=4.0*(float)c/d; cout<<"pai= "<<pai<<endl;} 
第18页：推广到阴影面积
下面可演化为计算图形的面积。如图所示计算有阴影线的图形的面积，乍看似乎有些难，但仔细分析即可在上面程序的基础上来做了。从思路上考虑落在阴影这块面积上的雨点数 g 与落在正方形整体上的雨点数 d 的比就是这块面积 s 的近似值。
第19页：阴影区的判据
此题的关键是如何判断雨点是落在阴影线的区域内。这就要用到解析几何的知识：
对于以原点 x=0，y=0 为圆心，半径为 1 的圆弧，阴影线中的每个点应满足 sqrt(x*x+y*y)>1
对于以 x=1，y=0 为圆心的圆弧，阴影线中的每个点应满足 sqrt((x-1)*(x-1)+y*y)>1
当然这个条件在产生随机数时就已经保证了，故可以不再考虑了。因此，要同时满足公式 1 和公式 2，雨点才能落入阴影线区域，语句如下。
第20页：判据语句与精确值
if ((sqrt(x*x+y*y)>1)&&(sqrt((x-1)*(x-1)+y*y)>1)) g=g+1;
就是依据上述的思路。为了比较所得结果是否有效，程序中给出了 s 的精确值，这个值是用几何的解法计算出的，见图：无阴影线部分可分解为 A、B、A 三块。
第21页：阴影面积程序的定义部分
参考程序如下（随机函数6.c）
#include <iostream.h>#include <math.h>#include <stdlib.h>void main(void){ long k,d=0,g=0; float s,x,y; srand( (unsigned)time(NULL)); 
第22页：阴影面积程序的循环与输出
for(k=1;k<=10000000;k=k+1){ d=d+1; x=(float)rand()/32767; y=(float)rand()/32767; if((sqrt(x*x+y*y)>1)&&(sqrt((x-1)*(x-1)+y*y)>1)) g=g+1;}s=(float)g/d;cout<<"s= "<<s<<endl;//输出s的精确值 cout<<"s的精确值为"<<(1.0-(3.14159/6.0+1.73205/4.0))<<endl;
说明：源文件该行输出语句的括号存在粘连与缺失，整理时按 C++ 语法补足为 cout<<"s的精确值为"<<(1.0-(3.14159/6.0+1.73205/4.0))<<endl;，与原意一致。
第23页：整数分拆题目
整数分拆
题目：有一个整数 n，将 n 分解成若干个整数之和，问如何分解能使这些数的乘积最大，输出这个乘积 m。
分析：分解出的数既不是越多越好，也不是越大越好。
例（以 n=12 为例）：
分解为 1+1+1+…+1，12 个 1
分解为 2+2+…+2，6 个 2
第24页：整数分拆的其余方案
分解为 3+3+3+3，4 个 3
分解为 4+4+4，3 个 4
分解为 6+6，2 个 6
分解为 5+7
分解为 4+8
第25页：最优分解方案
显然，3 最好。
算法：见与或结点图。
第26页：算法的三种情况
图的说明：
当 n 可以被 3 整除时，就让 n 分解成 k 个 3，k=n/3。之后，调用一个算 3 的 k 次方的函数 p(k)，输出 p(k)
当 n 除 3 余 1 时，可分解为 1, 3, 3, …, 3。从使乘积最大的角度出发，我们不希望分解出 1 来，这时，宁可让 1 与其中的一个 3 合并，为 4。让 k=(n-4)/3，接着调用 p(k)，但输出时再将原来减去的 4 当作一个乘数乘进来，即输出 4*p(k)
当 n 除 3 余 2 时，可分解为 2, 3, 3, …, 3。可以沿用上述思路让 k=(n-2)/3，求 p(k)。最后输出时将 2 乘入，即输出 2*p(k)
这个程序我们采用多分支选择语句，格式如下
第27页：switch语句的格式
switch(表达式) { case常量表达式1: {语句块1; } case常量表达式2: {语句块2; } case常量表达式n: {语句块n; } }
switch 后面括弧中的表达式的值与 case 后面的常量表达式的值相等时，就执行其后的语句。比如：
第28页：switch语句的示例
switch( a ) { case 0 : { b = 1; break; } case 1 : { b = 10; break; } case 2 : { b = 100; break; } case 3 : { b = 1000; break; } case 4 : { b = 10000; } }
实际上完成的任务是按 a 的取值给 b 赋以 1、10、100、1000、10000。
第29页：break语句的作用
注意：不可以没有 break。如果没有的话，不管 a 为 0，还是为 1，为 2 或为 3，b 的值均为 10000。
第30页：整数分拆程序的main
#include <iostream.h>long p(int ) ;void main(){ int n,k; long m; cout<<"请输入正整数n=" ; cin>>n; switch(n % 3) { 
第31页：switch的三种分支
case 0:{ k=n/3; m=p(k); break; } case 1:{ k=(n-4)/3; m=4*p(k); break; } case 2:{ k=(n-2)/3; m=2*p(k); break; } } 
第32页：输出与p函数
cout<<"最大乘积为"<<m<<endl;}//以下函数是被主程序调用的函数 long p(int kk){ int i,mm=1; for(i=1;i<=kk;i=i+1) mm=mm*3; return mm;}