C语言-算法.pptVIP

第2章 算法 算法的概念 程序设计的公式（Nikiklaus Wirth） 数据结构+算法=程序 其中，数据结构用来描述数据，组织求解对象。 算法用来描述操作步骤和规则。 如何确定算法 先分析问题，找出已知条件，即找出所有给定的信息，列出所需输出的全部信息，然后找出为解决问题还需要的其它信息。 最后确定算法。 例2.1 统计某班单科成绩优秀（即90或90分以上）的人数。 分析：已知成绩，输出优秀的人数。 还需要确定的数据：有多少人？ 一级算法： 输入人数给n； 输入n个人的分数，并统计优秀的人数k； 输出k值。 二级求精：对②进一步细化 方法一： ②-1 输入n个人的分数给一系列变量xi ②-2 检查每个xi，如果xi≥90，对k计数 三级求精：对②-1进一步细化 ②-1-(1) 使i=1； ②-1-(2) 输入分数给xi； ②-1-(3) 使i=i+1； ②-1-(4) 如果i≤n，转②-1-(2)，否则转②-1-(5) ； ②-1-(5) 本步骤结束； 对②-2进一步细化 ②-2-(1) 使i=1； ②-2-(2) 如果xi≥90，使k=k+1， 否则转②-2-(3)； ②-2-(3) 使i=i+1； ②-2-(4) 如果i≤n，转②-2-(2)，否则转②-2-(5) ； ②-2-(5) 本步骤结束； 方法二： ②-1 使i=1； ②-2 输入分数给x； ②-3 如果x≥90，使k=k+1， 否则转②-4； ②-4 使i=i+1； ②-5 如果i≤n，转②-2，否则转②-6 ； ②-6 本步骤结束； 方法二与方法一比较，可知： 变量少，步骤少 同一个问题可以有多种不同的算法 算法有优劣 确定算法的步骤：先粗后细 “自顶而下，逐步细化” 算法的表示方法 自然语言、流程图、伪代码 例2.2 在a，b，c中存放3个不同的数，要求对其排序，最后的结果使abc，并输出a，b，c。 1.用自然语言描述 ①输入a，b，c的值； ②若ab，交换a，b，否则转③；（a小，b大） ③若bc，交换b，c，否则转④ ；（c最大） ④若ab，交换a，b，否则转⑤； （a最小，b其次） ⑤结束。 2.用流程图描述 传统流程图由下列几种基本框组成： 用N-S流程图表示 顺序结构：执行时，顺序逐条执行，没有分支，没有转移。 选择结构：根据条件执行不同分支中的语句。 循环结构：根据条件，是同一组语句重复执行多次，或一次也不执行。分为当型循环结构和直到型循环结构。 用类C语言描述 void sort() /*li4.c*/ { scanf(“%d%d%d”,a,b,c); if(ab) { t=a; a=b; b=t; } if(bc) { t=b; b=c; c=t; } if(ab) { t=a; a=b; b=t; } printf(“%d%d%d\n”,a,b,c); } 算法的特性 算法的五个特性： 有穷性; 确定性; 有效性； 有零个或多个输入; 有一个或多个输出; 算法设计和描述举例 例2.3 求两个正整数m、n的最大公约数GCD，记为gcd(m,n)。 一级算法： 输入m，n； 求最大公约数； 输出最大公约数。 二级求精：对第2步进行细化 方法一：欧几里德算法 定理一：给定正整数m、n，一定存在两个整数q（商数）和r（余数），使得 q≥0，0≤rn且m=qn+r 定理2：给定正整数m和n，且有相应的整数q（商数）和r（余数），使得q≥0，0≤rn且m=qn+r，则 （1）若r=0，则gcd(m,n)=n。 （2）若r≠0，则gcd(m,n)=gcd(n,r)。 (gcd(m,n)==gcd(n*q+r,n)==gcd(n,r).) 分析：求gcd(m,n)，如果r=0，最大公约数就是n，否则就是求gcd(n,r)，可以使n?m，r?n，求新一轮的gcd(m,n)，反复循环，直到r=0，这时最大公约数就是当前n的值。 写出二级求精算法 /*li5.c*/ 2-1 让m除以n，得余数r； 2-2 如果r≠0，n?m，r?n，否则转2-4； 2-3 转2-1； 2-4 输出最大公约数n； 2-5 结束本步骤； 用流程图表示 方法二：根据定义，求最大公约数g。 * * 开始或终止框 处理框 输入输出框 判断框 流程线 连接点 开始 输入a,b,c ab? Y 交换a,b 1 1 bc? Y 交换b,c N N ab? Y 交换a,b N 输出a,b,c 结束 语句1 语句2 N-S流程图 语句1 语句2 传统流程图 判断表达式 语句1 满