《算法入门课件.ppt》由会员分享，可在线阅读，更多相关《算法入门课件.ppt（47页珍藏版）》请在三一办公上搜索。
1、2010年8月,.,1,算法入门,算法-程序的灵魂随机数函数数组整数问题平方数问题用算法提高程序的运行速度参考书籍,2010年8月,.,2,算法-程序的灵魂,硬件:摩尔定律速度提高约10亿倍.软件:发展相对缓慢,对算法研究不足,2010年8月,.,3,算法-程序的灵魂,哥德巴赫猜想费马定律,现代数论的建立和发展,大素数,公开密钥加密密钥数字签名,2010年8月,.,4,算法-程序的灵魂,算法的描述:自然语言/流程图算法的实现:计算机语言编程，上机实现,伪代码:if(aabb是平方数) printf(“Yesn”);,2010年8月,.,5,算法的多样性,求多个正整数的最大公约数和最小公倍数的3
2、种算法，如（756，504，630，2226）的最大公约数，最小公倍数。,算法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=400680,2010年8月,.,6,算法的多样性,算法2：辗转相除-递推法1.(756,504):756%504=252,504%252=0,所以(756,504)=2522.(630,252):6
3、30%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)的最大公约数为42,2010年8月,.,7,算法的多样性,算法2：辗转相除-递推法最小公倍数:1.756,504=756*504/252=15122.1512,630:先求(1512,630)=126,再1512,630=1512*630/126=75603.7560,2226:先求(7560,2226)=42,再7560,2226=7560*2226/42=4006
4、80所以,756,504,630,2226=400680,2010年8月,.,8,算法的多样性,算法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,126)=(714-504,504-3*126,126,126) /逐次相减时不能为0=(210,126,126,126)再重复=(42,42,42,42),因此,最大公约数为4
5、2,2010年8月,.,9,算法的多样性,算法3：逐次相减法求最大公约数、逐次相除法求最小公倍数逐次相除法:设有若干个数,其中最大的数为a,用a的1倍,2倍,除以其余的个数,若第n次恰好都能除尽,则此时的n*a即为它们的最小公倍数.如本题756,504,630,2226,最大数为2226,其180倍恰好能被其余数除尽,所以, 756,504,630,2226=2226*180=400680,2010年8月,.,10,算法的奇妙性,例 1-2+3=？例=10000*10000/20000.0=？,2010年8月,.,11,算法的奇妙性,韩信大点兵。韩信校场点兵，2人一伍多1人，3人一伍多2人，4
6、人一伍多3人，5人一伍多4人，6人一伍多5人，7人一伍多6人，8人一伍多7人，9人一伍多8人，10人一伍多9人，11人一伍多10人，12人一伍多11人。请问：韩信至少有多少兵？,2010年8月,.,12,算法的奇妙性,分析：都是“少1人”，因此，求最小公倍数（再减1）2，3，4，5，6，7，8，9，10，11，12-1=27719,2010年8月,.,13,算法的奇妙性,N个人参加乒乓球单打淘汰赛，至决出冠军需要打多少场？传统算法：（1）知道N的具体值；（2）考虑可能的轮空；（3）.创新算法：N-1场。（N个人比赛，只有冠军不被淘汰，共需淘汰N-1人，即N-1场）,2010年8月,.,14,穷
7、举法编程的瑰宝,穷举法（枚举法）：将集合中的元素一一列举出来，验证是否有问题的解。穷举法：没有办法的办法，但往往是高效的（算法构造快，程序编写快，运行快）。穷举法的关键：如何把实际问题定义成穷举问题，将可能的解限定在一个容易表达的集合内。-循环+if,2010年8月,.,15,随机数函数计算机模拟的基石,真随机数:掷硬币等。伪随机数：计算机模拟用，按某种算法计算产生的，是一个固定的序列。,简单：随机数函数的使用复杂：随机数函数的原理、算法、质量，对要解决的问题是否可靠/可信,2010年8月,.,16,高质量的均匀分布的随机数函数,均匀分布的随机数用得最多，而且是其他类型分布的随机数的基础。质量
8、：均匀性/覆盖性/独立性.算法：查阅已有的经典算法，如乘法同余法/列表法/平方取中法编写随机数函数double rnd(int 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)*9
9、0+10; b=rnd(1)*8+2;printf(“n%d%d=”,a,b);scanf(“%d”, if(c=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名乘客等车时
10、间的人数分布，即等了1分钟、2分钟、10分钟的各有多少人。,int a11,i,k;for(i=1;i=10000;i+) k=abjvn(0,10)+1; /取整后为110的整数 ak+; /等k分钟的人数加1 /ak表示等了k分钟的人数结果：等k分钟的有ak人,2010年8月,.,20,八种常用的随机数函数,2、射击直至命中的射击次数-几何分布的随机数函数 （每次试验结果只有2个-贝努利试验-几何分布）算法：x=lnr/lnq+1,double jihe(double q) /几何分布的随机数函数double f;f=log(rnd(1)/log(q)+1.0; /p:命中概率，q:缺失概
11、率return f; /q=1-p,2010年8月,.,21,八种常用的随机数函数,设导弹射手命中率为p，射击同一坦克，直到命中为止，模拟所用导弹的发数。程序运行一次，模拟200次。P的值由键盘输入。,int a31; /设每次所用导弹数不超过30发q=1-p;for(i=1;i=200;i+) k=jihe(q); /此次模拟用了k发子弹 ak+; /用k发导弹的次数加1 /ak表示用了k发导弹才命中的次数结果：用k发导弹命中的次数有ak次,2010年8月,.,22,八种常用的随机数函数,3、日光灯管的寿命-指数分布的随机数函数算法：- r,double zhishu(double z) /
12、指数分布的随机数函数double f;f= -z*log(rnd(1); /z为给定的一个平均值return f; /f为正数,2010年8月,.,23,八种常用的随机数函数,模拟电子管的寿命100次，设其平均寿命t=1000小时。,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次命中的射击次数-负二项分
13、布的随机数函数6、人到齐才开会的等待时间- 分布的随机数函数7、一天进入某商店的人数-泊松分布的随机函数8、人身体高度正态分布的随机数函数,2010年8月,.,25,数组设计算法的重要手段,百灯判熄数组元素变号代替开关有100盏灯,编号1100,分别由相应的100个开关控制。开始时全部朝上（开，灯亮），然后进行以下操作：编号凡是为1的倍数的灯反方向拨一次开关；是2的倍数的再反方向拨一次；是3的倍数的再反方向拨一次；是100的倍数的反方向拨一次。问：最后为熄灭状态的灯的编号？,2010年8月,.,26,数组设计算法的重要手段,分析：（1）定义数组a101，a0不用。ai=1表示第i盏灯为开亮状态
14、， ai=-1表示第i盏灯为熄灭状态。（2）利用循环。为数组a的100个元素赋初值1，表示全亮。（3）利用两重循环，实现拨动开关操作。外循环k: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;
15、 /拨动一次开关,2010年8月,.,28,数组设计算法的重要手段,打印杨辉三角形数组元素相加胜过组合 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1,2010年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,数组设计算法的重要手段,新战士的年龄数组嵌套班里来了个新战士，是个
16、数学迷。班长问他年龄，他说：我的年龄恰好是个团拜数。它的平方是个3位数，立方是个4位数，四次方是个6位数。三次方和四次方正好用遍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岁,2010年8月,.,33,数组设计算法的重要手段,（1）对x=18,19,20,21进行穷举（2）定义变量n3=x*x*x（4
17、位数），变量n4=x*x*x*x（6位数）。分离n3的4个数字，以及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应互不相
18、同，且ABC。（2）五位工人工资之和：(100A+10C+B)+(100B+10A+C)+(100B+10C+A)+(100C+10A+B)+(100C+10B+A)=122A+212B+221C=3194,for(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+C
19、AB+CBA= 222(A+B+C)=3194+ABC(2)变换为222(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-86,2010年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(“
20、工资为：%d元n”,n);/乘除法次数：4*5=20。优于算法1,2010年8月,.,38,整数问题,完全数（完美数）：一个正整数恰好等于它所有的真因子（除自身以外的因子）之和。如：6=1+2+3 28=1+2+4+7+14练习：求10000以内的完全数？,2010年8月,.,39,平方数问题,一数三平方数有这样的6位数，不仅它本身是平方数，而且它的前3位和后3位也都是平方数。例如：225625：225625=4752，225=152，625=252,2010年8月,.,40,平方数问题,算法1：穷举法（不用数组）（1）对所有的6位数100000999999，判断是否为平方数（共90万个）。（
21、2）是平方数的，把它分成前后两部分，分别判断是否平方数。（是平方数的有683个，进一步拆分+判断需要判断的个数为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 k+,2010年8月,.,42,平方数问题,算法2：利用数组元素表示三位的平方数思想：先根据平方数原则求出前后两部分(各3位数)，再组合成一个6位数，最后判
22、断该6位数是否平方数。（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=704个。/算法1为：901366个,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
23、(n)； if(n=p*p) n为正确解,2010年8月,.,44,用算法提高程序的运行速度,百鸡问题：鸡翁1值钱5，鸡母1值钱3，鸡雏3值钱1。百钱买百鸡，鸡翁，鸡母，鸡雏各几何？x+y+z=1005x+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,参考书籍,程序算法与技巧精选，郭继展等编著，机械工业出版社,
