算法课件算法的定义和特征.doc

《算法课件算法的定义和特征.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法的定义和特征：算法1欧几里德算法输入：正整数m，n输出：m，n的最大公因子1.inteuclid(intm,intn)2.{3.intr;4.do{5.r=m%n;6.m=n;7.n=r;8.}while(r)9.return10.}算法是解某一特定问题的一组有穷规则的集合。特征：1有限性2确定性3输入4输出5能行性算法设计的例子例1．1百鸡问题。公元5世纪末，我国古代数学家张丘建在他所撰写的《算经》中，提出了这样的一个问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何?”意思是公鸡每只5元、

2、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。令a为公鸡只数，b为母鸡只数，c为小鸡只数。根据题意，可列出下面的约束方程：a+b+c=l00(1)5a+3b+c/3=100(2)c%3=0(3)其中，运算符“／”为整除运算，“％”为求模运算，式(1．1．3)表示‘被3除余数为0。这类问题用解析法求解有困难，但可用穷举法来求解。穷举法就是从有限集合中，逐一列举集合的所有元素，对每一个元素逐一判断和处理，从而找出问题的解。·上述百鸡问题中，a、b、c的可能取值范围为0-100，对在此范围内的a、6、c的所

3、有组合进行测试，凡是满足上述3个约束方程的组合，都是问题的解。如果把问题转化为用n元钱买n只鸡，n为任意正整数，则式(1)、式(2)变为：a+b+c=n(4)5a+3b+c/3=n(5)于是，可用下面的算法来实现：算法1．2百鸡问题输入：所购买的3种鸡的总数目n输出：满足问题的解的数目k，公鸡，母鸡，小鸡的只数g[]，m[]，s[])1voidchickenquestion(ihtn,int&k,intg[],intm[],intsi])2{3inta,b,c;4k=O;5for(a=O;a<=n;a++){6for(b=O;b<=n

4、;b++){7for(c=O;c<=n;c++){8.if((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==O)){9.g[k]=a;10.m[k]=b;11.s[k]=c;12.k++;13.}14.}15}16.}17.}算法2:改进的百鸡问题输入：所购买的3种鸡的总数目n输出：满足问题的解的数目k，公鸡，母鸡，小鸡的只数g[]，mC]，s[])1voidchickenproblem(intn,int&k,intg[],intm[],ints[])2{3inti,j,a,b,c;4k=0;5i=n/5;6j

5、=n/3;7.for(a=0;a<=i;a++){8.for(b=O;b<=j;b++){9.c=n-a-b;10.if((5*a+3*b+c/3==n)&&(c%3==O)){11.g[k]=a;12.m[k]=b;13.s[k]=c;14.k++;15.}16.}17.}18.}