算法入门PPT课件.ppt

1、2010年8月.1算法入门 算法-程序的灵魂 随机数函数 数组 整数问题 平方数问题 用算法提高程序的运行速度 参考书籍2010年8月.2算法-程序的灵魂 硬件硬件:摩尔定律速度提高约10亿倍. 软件软件:发展相对缓慢对算法研究不足2010年8月.3算法-程序的灵魂哥德巴赫猜想哥德巴赫猜想费马定律费马定律现代数论现代数论的建立和发展的建立和发展大素数大素数公开密钥公开密钥加密密钥加密密钥数字签名数字签名2010年8月.4算法-程序的灵魂 算法的描述算法的描述:自然语言/流程图 算法的实现算法的实现:计算机语言编程，上机实现伪代码:if(aabb是平方数) printf(“Yesn”);2010

2、年8月.5算法的多样性 求多个正整数的最大公约数和最小公倍数的3种算法，如（756，504，630，2226）的最大公约数，最小公倍数。算法算法1 1：分解质因数法：分解质因数法756=2*2*3*3*3*7 504=2*2*2*3*3*7630=2*3*3*5*7 2226=2*3*7*53最大公约数:4个数的公因子相乘=2*3*7=42最小公倍数:在同样的质因数中,选取最多的个数相乘(不重复),即3个2,3个3,1个5,1个7,1个53=2*2*2*3*3*3*5*7*53=4006802010年8月.6算法的多样性算法算法2 2：辗转相除：辗转相除- -递推法递推法1.(756,504)

3、:756%504=252,504%252=0,所以(756,504)=2522.(630,252):630%252=126,252%126=0,所以(630,252)=1263.(2226,126):2226%126=84,126%84=42,84%42=0,所以(2226,126)=42因此,(756,504,630,2226)的最大公约数为422010年8月.7算法的多样性算法算法2 2：辗转相除：辗转相除- -递推法递推法最小公倍数:1.756,504=756*504/252=15122.1512,630:先求(1512,630)=126,再1512,630=1512*630/126=7

4、5603.7560,2226:先求(7560,2226)=42,再7560,2226=7560*2226/42=400680所以,756,504,630,2226=4006802010年8月.8算法的多样性算法算法3 3：逐次相减法求最大公约数、逐次相除法求最小公倍数：逐次相减法求最大公约数、逐次相除法求最小公倍数（756,504,630,2226）=（2226，756，630，504） /先从大到小排序=(2226-2*756,756-630,630-504,504) /逐次相减逐次相减,满足A=A-n*B0=(714,126,126,504)再重复上述过程:=(714,504,126,12

5、6)=(714-504,504-3*126,126,126) /逐次相减时逐次相减时不能为0=(210,126,126,126)再重复=(42,42,42,42),因此,最大公约数为422010年8月.9算法的多样性算法算法3 3：逐次相减法求最大公约数、逐次相除法求最小公：逐次相减法求最大公约数、逐次相除法求最小公倍数倍数逐次相除法逐次相除法: :设有若干个数设有若干个数, ,其中最大的数为其中最大的数为a,a,用用a a的的1 1倍倍,2,2倍倍,除以除以其余的个数其余的个数, ,若第若第n n次恰好都能除尽次恰好都能除尽, ,则此时的则此时的n n* *a a即为它们即为它们的最小公倍数

6、的最小公倍数. .如本题如本题756,504,630,2226,756,504,630,2226,最大数为最大数为2226,2226,其其180180倍恰好倍恰好能被其余数除尽能被其余数除尽, ,所以所以, , 756,504,630,2226=2226*180=4006802010年8月.10算法的奇妙性 例 1-2+3=？ 例=10000*10000/20000.0=？2010年8月.11算法的奇妙性 韩信大点兵。韩信校场点兵，2人一伍多1人，3人一伍多2人，4人一伍多3人，5人一伍多4人，6人一伍多5人，7人一伍多6人，8人一伍多7人，9人一伍多8人，10人一伍多9人，11人一伍多10人

7、，12人一伍多11人。请问：韩信至少有多少兵？2010年8月.12算法的奇妙性 分析：都是“少1人”，因此，求最小公倍数（再减1）2，3，4，5，6，7，8，9，10，11，12-1=277192010年8月.13算法的奇妙性 N个人参加乒乓球单打淘汰赛，至决出冠军需要打多少场？ 传统算法：（1）知道N的具体值；（2）考虑可能的轮空；（3）. 创新算法：N-1场。（N个人比赛，只有冠军不被淘汰，共需淘汰N-1人，即N-1场）2010年8月.14穷举法编程的瑰宝 穷举法（枚举法）：将集合中的元素一一列举出来，验证是否有问题的解。 穷举法：没有办法的办法，但往往是高效的（算法构造快，程序编写快，运

8、行快）。 穷举法的关键：如何把实际问题定义成穷举问题，将可能的解限定在一个容易表达的集合内。-循环+if2010年8月.15随机数函数计算机模拟的基石 真随机数真随机数:掷硬币等。 伪随机数伪随机数：计算机模拟用，按某种算法计算产生的，是一个固定的序列。简单：随机数函数的使用复杂复杂：随机数函数的原理、算法、质量，对要解决的问题是否可靠/可信2010年8月.16高质量的均匀分布的随机数函数 均匀分布的随机数用得最多，而且是其他类型分布的随机数的基础。 质量质量：均匀性/覆盖性/独立性. 算法：查阅已有的经典算法，如乘法同余法乘法同余法/列表法/平方取中法 编写随机数函数double rnd(i

9、nt x)：生成0和1之间（不包括0和1）均匀分布的随机小数 x=0，重复上一随机数 x=1,得到一个新的随机数 x=-1,第一次使用随机数 在头文件rndlib.h中自行定义2010年8月.17高质量的均匀分布的随机数函数 编写小学生乘法练习程序，由两位数乘以一位数。 分析：被乘数a是两位正整数，区间为（10，99），令a=rnd(1)*90+10,并转换成整型，得到1099之间的数。同理b=rnd(1)*8+2，得到29之间的数。int a,b,c;a=rnd(1)*90+10; b=rnd(1)*8+2;printf(“n%d %d=”,a,b);scanf(“%d”,&c); if(c

10、=a*b)2010年8月.18八种常用的随机数函数 1、等地铁时间-在区间（a,b）上均匀分布的随机数函数 算法：rnd(1)*(b-a)+a/在在(a,b)区间上均匀分布的随机数函数区间上均匀分布的随机数函数double abjvn(double a,double b)double f;f=rnd(1)*(b-a)+a;return f;2010年8月.19八种常用的随机数函数 设地铁每10分钟一趟，乘客到达车站的时间是随机的，试以分钟为单位（不满一分钟按一分钟计），模拟10000名乘客等车时间的人数分布，即等了1分钟、2分钟、10分钟的各有多少人。int a11,i,k;for(i=1;i

11、贝努利试验-几何分布） 算法：x=lnr/lnq+1double jihe(double q) /几何分布的随机数函数几何分布的随机数函数double f;f=log(rnd(1)/log(q)+1.0; /p:命中概率，命中概率，q:缺失概率缺失概率return f; /q=1-p2010年8月.21八种常用的随机数函数 设导弹射手命中率为p，射击同一坦克，直到命中为止，模拟所用导弹的发数。程序运行一次，模拟200次。P的值由键盘输入。int a31; /设每次所用导弹数不超过设每次所用导弹数不超过30发发q=1-p;for(i=1;i=200;i+) k=jihe(q); /此次模拟用了此

12、次模拟用了k发子弹发子弹 ak+; /用用k发导弹的次数加发导弹的次数加1 /ak表示用了表示用了k发导弹才命中的次数发导弹才命中的次数结果：用结果：用k发导弹命中的次数有发导弹命中的次数有ak次次2010年8月.22八种常用的随机数函数 3、日光灯管的寿命-指数分布的随机数函数 算法：- rdouble zhishu(double z) /指数分布的随机数函数指数分布的随机数函数double f;f= -z*log(rnd(1); /z为给定的一个平均值为给定的一个平均值return f; /f为正数为正数2010年8月.23八种常用的随机数函数 模拟电子管的寿命100次，设其平均寿命t=1

13、000小时。int a11,i,k; /k不超过不超过10，限制极限寿命，限制极限寿命double s,t=1000; for(i=1;i10) k=10;ak+; /使用寿命分成了使用寿命分成了10个时间区域，个时间区域，ak表示表示结果：寿命结果：寿命k*1000k*1000+1000小时的有小时的有ak次次2010年8月.24八种常用的随机数函数 4、n次射击有k次命中-二项分布的随机数函数 5、射击至第k次命中的射击次数-负二项分布的随机数函数 6、人到齐才开会的等待时间- 分布的随机数函数 7、一天进入某商店的人数-泊松分布的随机函数 8、人身体高度正态分布的随机数函数2010年8月

14、.25数组设计算法的重要手段 百灯判熄百灯判熄数组元素变号代替开关 有100盏灯,编号1100,分别由相应的100个开关控制。开始时全部朝上（开，灯亮），然后进行以下操作：编号凡是为1的倍数的灯反方向拨一次开关；是2的倍数的再反方向拨一次；是3的倍数的再反方向拨一次；是100的倍数的反方向拨一次。 问：最后为熄灭状态的灯的编号？2010年8月.26数组设计算法的重要手段 分析：分析： （1）定义数组a101，a0不用。ai=1表示第i盏灯为开亮状态， ai=-1表示第i盏灯为熄灭状态。 （2）利用循环。为数组a的100个元素赋初值1，表示全亮。 （3）利用两重循环，实现拨动开关操作。外循环k:

15、1100，步长为1，循环100次，表示100种拨动方法。内循环i:k100，步长为k，表示按k的倍数拨动开关。 （4）拨动一次开关用ai=-ai表示。 （5）最后，输出满足ai=-1的i。同时可以用变量n统计熄灭状态的灯的个数。2010年8月.27数组设计算法的重要手段int a101,i,k,n=0;for(i=1;i=100;i+) ai=1; /初始化初始化for(k=1;k=100;k+) for(i=k;i=100;i+=k) ai=-ai; /拨动一次开关拨动一次开关2010年8月.28数组设计算法的重要手段 打印杨辉三角形打印杨辉三角形数组元素相加胜过组合 1 1 1 1 2 1

16、 1 3 3 1 1 4 6 4 1 1 5 10 10 5 12010年8月.29数组设计算法的重要手段 分析分析 2010年8月.30数组设计算法的重要手段 (1)用二维数组aNN表示，按下三角阵考虑。 (2)第i行的首尾元素为：ai1=1,aii=1 (3)其余元素：从第3行开始，为其左上角和右上角两元素之和，即 aij=ai-1j-1+ai-1j注：0行0列不用2010年8月.31数组设计算法的重要手段 新战士的年龄新战士的年龄数组嵌套 班里来了个新战士，是个数学迷。班长问他年龄，他说：我的年龄恰好是个团拜数。它的平方是个3位数，立方是个4位数，四次方是个6位数。三次方和四次方正好用遍

17、09这十个数字，也就是说，这全部10个数字都在向我团拜呢。 问：新战士的年龄？2010年8月.32数组设计算法的重要手段 数学分析： （1）设年龄为x，应满足 （2）174=83521，小于6位；223=10648，大于4位，因此得 （3）验证18，19，20，21，结果183=5832,184=104976，符合条件 （4）新战士年龄为18岁 6454333221010,1010,1010 xxx2118 x2010年8月.33数组设计算法的重要手段 （1）对x=18,19,20,21进行穷举 （2）定义变量n3=x*x*x（4位数），变量n4=x*x*x*x（6位数）。分离n3的4个数字，

18、以及n4的6个数字，依次存放到数组a10中。如x=21时，213=9261，214=194481。 （3）判断10个数a0a9互不重复，有一个元素的值不为1，则非解。2010年8月.34整数问题 学徒工工资数:有一位学徒工工资数是ABC元,组内另外五个工人的工资恰好也是三位数(均高于学徒工),分别为:ACB,BAC,BCA,CAB,CBA,且这五个工人工资之和等于3194元. 问:学徒工的工资是多少?2010年8月.35整数问题 ABC vs ACB,BAC,BCA,CAB,CBA, 算法1：穷举（1）A，B，C应互不相同，且ABC。（2）五位工人工资之和：(100A+10C+B)+(100B

19、+10A+C)+(100B+10C+A)+(100C+10A+B)+(100C+10B+A)=122A+212B+221C=3194for(a=1;a=7;a+) /abcfor(b=a+1;b=8;b+) for(c=b+1;c=9;c+) if(122*a+212*b+221*c=3194) ./乘法次数：乘法次数：7*7*7*3=1029次次2010年8月.36整数问题 ABC vs ACB,BAC,BCA,CAB,CBA, 算法2：利用数字有重复的特点进行推导（1）6人工人工资之和：ABC+ACB+BAC+BCA+CAB+CBA= 222(A+B+C)=3194+ABC(2)变换为22

20、2(A+B+C)=14*222+86+ABC，再变为： 222(A+B+C-14)=86+ABC(4)=右边应该是一个3位数，因此A+B+C-14的值只能是1，2，3，4之一，即i=A+B+C-14=1/2/3/4。(5)而学徒工的工资ABC=222*i-862010年8月.37整数问题for(i=1;i=4;i+) n=222*i-86; /n=abc时为解 a=n/100; /分离出百位数字 c=n%10; /分离出各位数字 b=n/10%10; /分离出十位数字 if(a+b+c-14=i) printf(“工资为：%d元n”,n);/乘除法次数：4*5=20。优于算法12010年8月.

21、38整数问题 完全数（完美数）：一个正整数恰好等于它所有的真因子（除自身以外的因子）之和。 如：6=1+2+3 28=1+2+4+7+14 练习：求10000以内的完全数？2010年8月.39平方数问题 一数三平方数一数三平方数 有这样的6位数，不仅它本身是平方数，而且它的前3位和后3位也都是平方数。 例如：225625：225625=4752，225=152，625=2522010年8月.40平方数问题 算法1：穷举法（不用数组） （1）对所有的6位数100000999999，判断是否为平方数（共90万个万个）。 （2）是平方数的，把它分成前后两部分，分别判断是否平方数。（是平方数的有683

22、个，进一步拆分+判断需要判断的个数为683*2=1366个）/开平方和平方的运算量都很大2010年8月.41平方数问题for(i=100000;i=999999;i+) n=sqrt(i); if(i= =n*n) /判断是平方数的 q=i/1000; h=i%1000; /拆出前后两个3位数 r=sqrt(q); s=sqrt(h); if(q=r*r&h=s*s) /两个3位数都是平方数 printf(“%8ld”,i); k+2010年8月.42平方数问题 算法2：利用数组元素表示三位的平方数 思想：先根据平方数原则求出前后两部分(各3位数)，再组合成一个6位数，最后判断该6位数是否平方

23、数。（1）定义long数组a32,算出i=031时的平方i*i，存入数组ai中。（31的平方999）（2）由两个3位的平方数组成一个六位数。前一个平方数是真正的3位数ABC，后一个可以形如00N，0MN，PMN(3)两重循环，外层i=3110，小于10则平方不是3位数。内层j=310/需要判断平方数的个数为：22*32=704704个。/算法1为：901366901366个2010年8月.43平方数问题for(i=0;i=10;i-) m=1000*ai; /高3位数实际值 for(j=31;j=0;j-) /低3位可以是1位，2位，3位数 n=m+aj; /得到六位数 p=sqrt(n)；

24、if(n=p*p) n为正确解2010年8月.44用算法提高程序的运行速度 百鸡问题：鸡翁1值钱5，鸡母1值钱3，鸡雏3值钱1。百钱买百鸡，鸡翁，鸡母，鸡雏各几何？ x+y+z=100 5x+3y+z/3=100 穷举法：三重循环（1）鸡翁x:119 鸡母y:132 鸡雏z:398之间，且应是3的整数倍for(x=1;x=19;x+)for(y=1;y=32;y+)for(z=3;z=98;z+=3)2010年8月.45用算法提高程序的运行速度 优化： 将z=100-x-y代入5x+3y+z/3=100，得：7x+4y=100 转换为二重循环for(x=1;x=19;x+)for(y=1;y=32;y+)if(7*x+4*y=100) printf(“%5d%5d%5dn”,x,y,100-x-y); break;2010年8月.46用算法提高程序的运行速度2010年8月.47参考书籍 程序算法与技巧精选， 郭继展等编著， 机械工业出版社