程序设计语言初步二

《程序设计语言初步二》由会员分享，可在线阅读，更多相关《程序设计语言初步二（140页珍藏版）》请在金锄头文库上搜索。

1、1,2,4.1 算法的概念 4.2 算法的三种基本结构 4.3 算法的描述方法 4.4 结构化程序设计方法 4.5 算法设计实例研究,提纲,3,程序设计的目的和步骤 算法的描述方式 计算机算法及其特性,4.1 算法的概念,4,4.1 算法的概念,一. 程序设计的目的 计算机科学与技术学科的根本问题是：什么能够被有效地自动化 ； 设计程序的根本目的：让计算机帮助人们自动地完成所要处理的复杂任务； 程序设计两个核心问题：“做什么”与“怎么做” ；其中需求分析解决“做什么”，程序设计解决“怎么做” 。,5,4.1 算法的概念,二. 程序设计两步走 对复杂问题，直接写出能解决该问题的计算机程序是困难的

2、，为此，人们在进行程序设计时分两步走： 1）算法设计：不使用程序设计语言，而使用一种较简单明了的表达方式（例如自然语言）设计出求解问题的步骤序列-算法。 2）程序编写：根据设计并描述好的算法，使用某种程序设计语言编写对应于该算法的程序 。,6,三. 算法的概念 算法：是解决问题的步骤序列（操作序列）。,4.1 算法的概念,起床 穿衣、叠被 去水房洗漱 回宿舍放洗漱用品 骑车去食堂 排队买饭 吃饭 交回餐具 骑车去教室,描述的是活动和过程,7:20前离开宿舍 7:50前离开食堂 8:00前进入教室,描述的是操作执行后的状态，通过状态的转移来描述所执行的操作。,可能的活动：起床、穿衣叠被、洗漱等,

3、可能的活动：骑车到食堂、排队买饭、吃饭、交回餐具,7,4.1 算法的概念,四. 计算机算法及其特性 什么是计算机可执行的操作； 要在计算机能力集上进行算法设计； 算法必须具备的五个特性： 可执行性：算法中的每一个步骤都是计算机可执行的（在计算机能力集范围内） ； 确定性：算法中的每一个步骤，必须是明确定义的，不得有任何歧义性 ； 有穷性：算法必须在执行有穷步之后结束； 有输入信息的说明：对加工对象提要求； 有输出信息的步骤 ：至少要输出问题答案。,8,例1 求12910 ，即10！,算法思路： 计算机能力集只提供两数相乘的运算。 N！=N （N-1）！ 10！=10 9！=10 9 8！ =1

4、0 9 8 7！ = =10 9 8 2 1! 先计算1！、再计算2!=2*1!、再计算3!=3*2!,以此类推，直到计算出10!=10*9!。 使用变量p,9,例1 求12910 ，即10！,第一种算法：,S1(求2!)：先求21，得到结果2并赋值给变量p；即：21p；,S2 (求3!) ：将步骤S1得到的乘积p（p=2）再乘以3，得结果6并 赋值给变量p；即： 3 pp；,S3(求4!)：将p（p=6）再乘以4，得24并赋值给变量p；即： 4pp；,S4(求5！)：将p（p=24）再乘以5，得120并赋值给变量p；即： 5pp；, S9(求10!)：将p（p=362880)乘以10，得36

5、28800，10pp；,10,#include main() int p; p=2*1; /求2!赋值给p p=3*p; /求3!赋值给p p=4*p; p=5*p; p=6*p; p=7*p; p=8*p; p=9*p; p=10*p; /求10!赋值给p printf(“%d“,p); system(“pause“); return 0; ,评价：求10!需要写9个赋值操作，算法过于繁琐！试想：求1000！的算法,11,对算法进行抽象: 核心操作就是两数相乘ipp ，反复相乘10-1=9次，i初始值为2，p初始值为1，每相乘一次i的值加1。 根据上述分析，本题可利用循环结构求解： 第1次循

6、环用于求2！，第2次循环在第1次循环基础上求3！，,第9次循环在第8次循环基础上求10！,例1 求12910 ，即10！,12,定义两个变量p和i，p代表阶乘结果,i代表本次循环要求的是i!；,循环条件：i10,循环体：p=i*p；(求i！) i=i+1;,i!,(i-1)!,例1 求12910 ，即10！,初始化：i=2；p=1,由于本次循环求得的i*p的值将作为下次循环p的值，故本次循环将i*p赋值给p，为下一次循环做准备。,13,S1：使i=2 ； S2：使p=1 ；/*变量初始化*/ S3：执行ip，乘积仍放在变量p中，即ip =p； S4：使i的值加1，即i+1=i； S5：如果i=

7、10，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。 最后得到p的值就是10！的值。,求12910算法思路：,“迭代”和“循环” ：在程序设计中，重复执行同样操作的过程称为“迭代”。程序中被重复执行的程序段称为“循环”。,14,例1源程序,#include main() int n, i, p; /n：存储要求阶乘的数；p：存储求得的阶乘； printf(“input n:n“); scanf(“%d“, ,15,练习1：输入十个整数，求出最大值、最小值。 算法思路：采用迭代计算的方法 以求最大值为例，即： Max(N1)=N1 Max(N2,N1)= N1 if N2=N1

8、Max(N3,N2,N1)= Max( N3, Max(N2,N1) ) . Max(Nn , Nn-1 ,N2,N1) Max(Nn ,Max(Nn-1 ,N2,N1),定义变量max来存储前n-1个整数的最大值。第n个数将和max比较，决定前n个数的最大值。,整个问题就被转变为求9次两个数的最大值。 每一次都是读入一个数，和之前求得的最大数再去比较。,16,循环条件：i10,循环体： 读入第i个整数n； 如果nmax,则max=n； 否则，如果nmin,则min=n； i=i+1;,循环初始化： 读入一整数n; minn; max=n; i2；,请写出本题源程序,17,源程序：输入十个整数

9、，求出最大值、最小值,#include #define COUNT 10 main() int i, n, max, min;/i:循环计数；n:读取的数； /max:当前最大值; min:当前最小值 scanf(“%d“, /代表接下去要读取的是第2个数,18,源程序：输入十个整数，求出最大值、最小值(续),while (i max) /求最大数 max = n; else if (n min) /求最小数 min=n; i=i+1; printf(“max number is %d“,max); printf(“min number is %d“,min); system(“pause“)

10、; return 0; ,19,例2 输入120个学生的学号和成绩，要求将他们之中成绩在60分以上者的学号和成绩打印出来。,循环结束条件: 已经处理了120个学生的信息。为了计数当前输入的是第几个学生的信息，可以引入变量i，用于表示当前处理的学生顺序。 循环体: 1：读入第i个学生的学号和成绩（抽象出变量num和score）; 2：如果score 60，则打印num和score ，否则不打印; 3：i+1=i；,问题分析：就是反复输入处理每一个学生的信息，处理120次。,20,输入120个学生的学号和成绩，要求将他们之中成绩在60分以上者的学号和成绩打印出来。,S1：1=i； S2：读入第i个

11、学生的学号和成绩分别到变量num和score中； S3：如果score 60，则打印num和score ； S4：i+1=i； S5：如果i120，则返回S2，继续执行；否则，算法结束。,循环处理模式： 处理本次循环要做的任务； 为下一次循环做准备；,21,4.1 算法的概念,练习2：请写出本题对应的程序,22,4.1 算法的概念,#include main() int no,total,count;/no:学号。total:总学生数。count：计数 float score; /成绩 printf(“how many int numbers do you want to input:n“);

12、 scanf(“%d“, return 0； ,23,例3 一个大于或等于3的正整数，判断它是否为一个素数（质数） 。,所谓质数，是指除了1和该数本身外，不能被其他任何整数整除的数。例如，13是素数（质数）。因为它不能被2，3，4，12整除。 由于素数在当代的密码学中扮演了中心的作用，所以该问题具有重要意义。 判断一个数n（n3）是否为质数：将n作为被除数，将2到（n-1）各个整数依次作为除数，如果都不能被整除，则n为素数。,4.1 算法的概念,24,判断质数,看n能否被2到（n-1）之间的各个整数整除：,变量抽象：n：存放被判断的整数；i：存放除 数，取值为2,n-1；r：存放n/i得到的余

13、数,循环体： n被i除，得余数r；即n mod i=r； 如果r=0，表示n能被i整除，则打印 n“不是素数”，算法结束；否则i+1=i；,循环条件： i=n-1,循环初始化： i=2,问题：当r为0时如何退出循环，结束算法？,25,判断质数,设置一个标记变量isPrim，初始值为0，当r为0时使isPrim值为1，在循环条件中加入对该变量值的判断，以决定是否提前退出循环,循环体： n被i除，得余数r；即n mod i=r； 如果r=0，表示n能被i整除，则打印 n“不是素数”，令isPrim=1；否则i+1=i；,循环条件： i=n-1 & isPrim=0,循环初始化： i=2;isPri

14、m=0;,26,S1：输入n的值； S2：i=2；/* i 是除数 */ S3：n被i除，得余数r；即n mod i=r S4：如果r=0，表示n能被i整除，则打印 n“不是素数”，算法结束；否则执行 S5； S5：i+1=i； S6：如果in-1，返回S3；否则，打印n“是素数”，算法结束。,n：被判断的整数；i：被除数； r：存放n/i得到的余数,事实上，i只需2到 之间的整数整除即可。,27,4.1 算法的概念 4.2 算法的三种基本结构 4.3 算法的描述方法 4.4 结构化程序设计方法 4.5 算法设计实例研究,提纲,28,4.2 算法的三种基本结构,三种控制结构(Bohra和Jac

15、opini ) 顺序结构、 选择结构、循环结构 顺序结构,按书写顺序执行的语句构成的程序段。,29,选择结构,根据给定的表达式是否成立而选择执行操作A或操作B。如果表达式成立，则执行操作A；如果表达式不成立，则执行操作B。 操作B可以为空。,4.2 算法的三种基本结构,30,当型循环结构,4.2 算法的三种基本结构,C语言无直到型循环结构。 比较：直到型循环结构和C语言中的do-while结构？,直到型循环结构,31,三种控制结构的共同点 只有一个入口（a处） 只有一个出口（b处） 结构内的每一个部分都有机会被执行到 结构内不存在“死循环”（无终止的循环）,4.2 算法的三种基本结构,由这三种

16、基本结构顺序组成的算法结构，可以解决任何复杂问题！,32,4.1 算法的概念 4.2 算法的三种基本结构 4.3 算法的描述方法 4.4 结构化程序设计方法 4.5 算法设计实例研究,提纲,33,4.3 算法的描述方法,用自然语言描述 用流程图描述 用N-S流程图描述 用伪码描述 用计算机语言描述,34,4.3 算法的描述方法自然语言,文字冗长； 不严格，易产生歧义（二义性）； 不方便描述分支和循环结构；,35,4.3 算法的描述方法流程图,流程图的基本元素（ANSI规定）,起止框,输入/出框,判断框,处理框,流程线,连接点,注释框,36,4.3 算法的描述方法流程图,流程图描述的选择结构,37,当型循环结构,直到型循环结构,流程图描述的循环结构,4.3 算法的描述方法流程图,38,连