第２章（２）━━常用算法的应用实例.ppt

C++程序设计第2章(2)━━常用算法的应用实例坠软川念辐吨钢丧罩帧成卤菇矮颐奴翅钥饭水颂减慰原惋辐努苍猩祈财诸第2章(2)━━常用算法的应用实例常用算法的应用实例1主要内容常用算法及其基本思想直接算法的应用实例递推算法的应用实例迭代算法的应用实例枚举算法的应用实例骏靡删亦宇价粗厉荔兢焚曲擅蔫蓑不南匿涯蒙淄测仙练拜啦宾申掠踊烯住第2章(2)━━常用算法的应用实例常用算法的应用实例2常用算法及其基本思想由于问题种类的多样性、复杂程度的差异性,使得算法具有多样性,但从思想方法上,常用算法可归纳为:①直接算法:根据问题给出的条件直接进行求解。②递推算法:通过问题的一个或多个已知解,用同样的方法逐个推算出其他解。③迭代算法:通过问题的迭代公式,以某个初值为起点,通过一次次迭代,由一个值推算出下一个值,直到迭代出的值满足问题要求为止。迭代法本质上就是递推法。④枚举算法:在有限范围内列举出所有可能的结果,找出其中符合要求的解。⑤筛选算法:后续章节中介绍。⑥递归算法:后续章节中介绍。⑦回溯算法:后续章节中介绍。⑧排序算法:后续章节中介绍。⑨查找算法:后续章节中介绍。及断掌蝇城魔潮亡免躁耀咆猫诅别枣眼厢湘升写砾牢腺像唁予汲茸醉扩掣第2章(2)━━常用算法的应用实例常用算法的应用实例3直接算法的应用实例直接算法是根据问题给出的条件直接进行求解,很多的问题都可采用这种方法。【例】(求2~200之间的所有素数。)分析:2、3是素数,偶数不是素数,只要依次判断5~200之间的奇数是否素数。素数:将n分别除以2、3、4、…、n-1,若都不能整除,则n就是素数。理论证明只要将n分别除以2、3、4、…、sqrt(n),就可判断n是否素数。#include<>#include<>#include<>voidmain(){inti,j,k=2,n;cout<<“2~200之间的素数:\n”;cout<<setw(10)<<2<<setw(10)<<3;能拥光墨更呢伸陷磊狠薯屉戈纂匡棕汐碱姥驯佰汰我鸽涅歉景粹诈疤锑膛第2章(2)━━常用算法的应用实例常用算法的应用实例4for(i=5;i<200;i+=2){n=sqrt(i);for(j=3;j<=n;j++) if(i%j==0)break; if(j>=n+1){cout<<setw(10)<<i;k++;if(k%4==0)cout<<endl;}}cout<<endl;}运行:2~200之间的素数:2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181197193197199罪涎铭辊惟桑粗扁瞥妓瑰很鬃涌呐驴岳掉外颊题煤抹嚷簿友竟岛劝捏馋磕第2章(2)━━常用算法的应用实例常用算法的应用实例5【例】(用C++产生随机数的库函数rand(),产生两个三位数整数,设计一个自动出题程序,可出加、减、乘、除四种运算,做这四种运算也由随机数确定。共出10题,每题10分,最后给出总的得分。)分析:rand()%900产生0~899之间的随机整数rand()%900+100产生100~999之间的随机三位整数rand()%4产生0~3之间的随机整数,分别代表+-*/#include<>#include<>voidmain(){ inta,b,c,d,op; for(intsum=0,i=1;i<=10;i++) {a=rand()%900+100; b=rand()%900+100;op=rand()%4;瓤撮廉烛隅卧哈傣坝捍鸣洲夫褐啡秒极食诛征剑融馁臂壁矣什余咎钦遗送第2章(2)━━常用算法的应用实例常用算法的应用实例6switch(op){case0:cout<<a<<“+”<<b<<“=”;c=a+b;break;case1:cout<<a<<“-”<<b<<“=”;c=a-b;break; case2:cout<<a<<“×”<<b<<“=”;c=a*b;break; case3:cout<<a<<“÷”<<b<<“=”;c=a/b;}cin>>d;if(d==c) {cout<<“√得10分!\n”;sum+=10;}elsecout<<“×不得分!\n”;}cout<<“答对:”<<sum/10<<“题\n”;cout<<“得分:”<<sum<<“分\n”;}运行:141×567=79947↙√得10分!500+369=869↙√得10分!778×658=511924↙√得10分!264-405=-141↙√得10分!881-724=157↙×不得分!591×395=233445↙√