程序设计语言初步二.ppt

1,2,4.1 算法的概念4.2 算法的三种基本结构4.3 算法的描述方法4.4 结构化程序设计方法4.5 算法设计实例研究,提纲,3,程序设计的目的和步骤算法的描述方式计算机算法及其特性,4.1 算法的概念,4,4.1 算法的概念,一.程序设计的目的计算机科学与技术学科的根本问题是：什么能够被有效地自动化；设计程序的根本目的：让计算机帮助人们自动地完成所要处理的复杂任务；程序设计两个核心问题：“做什么”与“怎么做”；其中需求分析解决“做什么”，程序设计解决“怎么做”。,5,4.1 算法的概念,二.程序设计两步走对复杂问题，直接写出能解决该问题的计算机程序是困难的，为此，人们在进行程序设计时分两步走：1）算法设计：不使用程序设计语言，而使用一种较简单明了的表达方式（例如自然语言）设计出求解问题的步骤序列-算法。2）程序编写：根据设计并描述好的算法，使用某种程序设计语言编写对应于该算法的程序。,6,三.算法的概念算法：是解决问题的步骤序列（操作序列）。,4.1 算法的概念,起床穿衣、叠被去水房洗漱回宿舍放洗漱用品骑车去食堂排队买饭吃饭交回餐具骑车去教室,描述的是活动和过程,7:20前离开宿舍7:50前离开食堂8:00前进入教室,描述的是操作执行后的状态，通过状态的转移来描述所执行的操作。,可能的活动：起床、穿衣叠被、洗漱等,可能的活动：骑车到食堂、排队买饭、吃饭、交回餐具,7,4.1 算法的概念,四.计算机算法及其特性什么是计算机可执行的操作；要在计算机能力集上进行算法设计；算法必须具备的五个特性：可执行性：算法中的每一个步骤都是计算机可执行的（在计算机能力集范围内）；确定性：算法中的每一个步骤，必须是明确定义的，不得有任何歧义性；有穷性：算法必须在执行有穷步之后结束；有输入信息的说明：对加工对象提要求；有输出信息的步骤：至少要输出问题答案。,8,例1 求12910，即10！,算法思路：计算机能力集只提供两数相乘的运算。N！=N（N-1）！10！=10 9！=10 9 8！=10 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，得3628800，10pp；,10,#includemain()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次循环用于求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=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)=N1Max(N2,N1)=N1 if N2=N1Max(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,源程序：输入十个整数，求出最大值、最小值,#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);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个学生的学号和成绩分别到变量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);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得到的余数,循环体：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;isPrim=0;,26,S1：输入n的值；S2：i=2；/*i 是除数*/S3：n被i除，得余数r；即n mod i=rS4：如果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和Jacopini)顺序结构、选择结构、循环结构 顺序结构,按书写顺序执行的语句构成的程序段。,29,选择结构,根据给定的表达式是否成立而选择执行操作A或操作B。如果表达式成立，则执行操作A；如果表达式不成立，则执行操作B。操作B可以为空。,4.2 算法的三种基本结构,30,当型循环结构,4.2 算法的三种基本结构,C语言无直到型循环结构。比较：直到型循环结构和C语言中的do-while结构？,直到型循环结构,31,三种控制结构的共同点 只有一个入口（a处）只有一个出口（b处）结构内的每一个部分都有机会被执行到 结构内不存在“死循环”（无终止的循环）,4.2 算法的三种基本结构,由这三种基本结构顺序组成的算法结构，可以解决任何复杂问题！,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,连接点（小圆圈）：用于将画在不同地方的流程线连接起来,39,求10！流程图,使用当型循环结构描述,40,打印学生序号及成绩流程图,41,判断质数的流程图,使用直到型循环结构描述,判断r是否为0,条件成立则跳出循环,42,练习：将以上流程图改成用当型循环结构表示。,该流程图中循环结构有两个出口！违反单入单出原则！,如何改进？,43,改进后的流程图：单入单出,设置标志位isPrim,44,传统流程图的弊端 对流程线的使用没有严格限制，阅读困难；不能保证算法结构的单入单出特性；占用篇幅较多；,4.3 算法的描述方法N-S流程图,必须限制箭头的滥用，让流程只能顺序执行下去！保证结构化原则的流程描述工具N-S图,45,基本结构,4.3 算法的描述方法N-S流程图,p、p1表示的是判断条件；A、B框是操作；注意：A、B框可以是一个简单的操作（如读入数据或打印输出等），也可以是三种基本结构之一,顺序结构,选择结构,当型循环结构,直到型循环结构,46,例1 求10!的N-S流程图,4.3 算法的描述方法N-S流程图,47,例2 打印学生成绩N-S流程图,4.3 算法的描述方法N-S流程图,48,例3 判断质数的N-S流程图,4.3 算法的描述方法N-S流程图,49,4.3 算法的描述方法伪码描述,流程图和N-S图画起来比较费事，适合于表示算法，而在算法设计中使用不是很理想。伪码 用介于自然语言和程序设计语言之间的文字和符号来描述算法。,【返回】,IF x is positive THEN print x ELSE print y,WHILE i60 THEN print score i加1,50,4.3 算法的描述方法,例4：利用泰勒级数：,计算正弦的值，直到最后一项绝对值小于10-6 时为止。,分析：求n项和的算法思路Sum(a1)=a1Sum(a1,a2)=Sum(a1)+a2=a1+a2Sum(a1,a2,a3)=Sum(a1,a2)+a3Sum(a1,a2,an)=Sum(a1,a2,an-1)+an,51,4.3 算法的描述方法,算法的核心操作是求两数之和，其中第一个操作数是前一次求得的和。如何求第二个操作数？算法1：n决定了第n项因子的值，即第二个操作数；因此每一次可根据当前n的值计算出第二个操作数。请用NS图描述出算法1。,52,求sin(x)算法1,i代表下一个p是第几项，因此初值是1,变量抽象：x：存储未知数x的值；sum：存储和；p：存储当前待加的因子；i：当前待加的是第几个因子,53,问题：任何数据类型只能表示一定范围内的数，当试图往变量中存储在范围之外的数，数据无法正确存储。求x的n次方和(2n-1)!时可能会导致结果太大而溢出。解决方法：1.用浮点型变量来保存(2n-1)!的结果2.改进算法算法2,54,4.3 算法的描述方法,=,算法2：设第i项因子表示为，考察 和 的关系。,=*(-1)*x2/(2i-1)*(2i-2),55,请用NS图描述算法2。,4.3 算法的描述方法,【源程序演示】,i代表下一个p是第几项，因此初值是1,56,#include#includemain()int i;float x;double sum,p;/p用于存放待加的那一项printf(input x:);scanf(%f,57,4.1 算法的概念4.2 算法的三种基本结构4.3 算法的描述方法4.4 结构化程序设计方法4.5 算法设计实例研究,提纲,58,源自于对goto语句的争论goto语句详见程序设计教程436页,4.4 结构化程序设计方法,59,#include main()int count=1;start:/标号,是跟有冒号的标识符 if(count10)goto end;printf(%d,count);count=count+1;goto start;end:printf(n);system(pause);return 0;,1 2 3 4 5 6 7 8 9 10请按任意键继续.,运行效果：,60,4.4 结构化程序设计方法,用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、阅读、修改和维护。结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。结构化程序设计方法的基本思想：采用分而治之的方法，将一个复杂问题分解为相对简单的一些子问题，然后针对这些子问题进行求解。如果某个子问题仍然是比较复杂的，再进一步分解为子-子问题，直到所有问题都能够求解。求解问题的过程是分阶段进行的，每个阶段处理的问题都控制在人们容易理解和处理的范围内（67个之内）。,61,4.4 结构化程序设计方法,结构化程序设计方法自顶向下；逐步细化；模块化设计（函数）；结构化编码（三种基本结构）。,62,例4.13 利用辗转相除法求两个正整数的最大公约数。辗转相除法求最大公约数的数学定义如下：GCD（x,y）=y|xy and x MOD y=0 GCD（y,x MOD y）|xy and x MOD y 0;说明：先判断x能否被y整除，若可以，则最大公约数就是除数y；否则，则将y 作为被除数，x MOD y 作为除数继续上面的操作，直到x能否被y整除为止。,GCD(6,4),GCD(4,2),=,=,2,=,GCD(124,6),最大公约数为2,例如：求GCD(124,6)的过程为：,63,算法1,2,交换变量x和y的值：,自顶向下，逐步细化,64,最终算法1,算法设计任务结束的标准是各步骤已精细到能用语句描述，即满足算法的5大特征标志算法设计任务结束。,65,算法2,思考：能否不借助于变量r，而是xy;y x%y？或者y x%y；x y,66,练习3：设计算法，求一个正整数的长度。算法1：例如num=12345，求num的长度第1步：去掉最低位，num=1234，长度len=1第2步：去掉最低位，num=123，长度len=2第3步：去掉最低位，num=12，长度len=3第4步：去掉最低位，num=1，长度len=4第5步：去掉最低位，num=0，长度len=5,算法中每一步的核心操作是从num中去掉最低位，长度len加1,67,68,假设num长度不超过8，例如num=12345，求num的长度算法2：试探能被10的几次方除后商不为0第1步：num/107=0第2步：num/106=0第3步：num/105=0第4步：num/104!=0,说明长度为4+15,算法中每一步的核心操作是试探：num除10i后商是否0,69,增加对输入为0的判断,进一步细化,70,练习4：输入一个不超过8位的正整数，要求把这个整数分解为单个数字，然后打印出每一个数字（每一个数字之间用两个空格分开）。例如用户输入了4200，程序打印结果为：4 2 0 0。设计算法。第1步：得到num最高位4并输出，num=200第2步：得到num最高位2并输出，num=0第3步：得到num最高位0并输出，num=9第4步：得到num最高位0并输出，num=0,71,72,练习5：设计算法，判断一个正整数是否是回文数。回文数是指正读和反读都一样的数。算法1：比较第1位和倒数第1位比较第2位和倒数第2位算法2：反着读，假设读得的数为reverseNum，判断num和reverseNum是否相等,73,以求a0a1a2a3的逆数为例，假设reverse实现逆着读reverse(a3)=a3reverse(a2a3)=a3a2=a3*10+a2=reverse(a3)*10+a2reverse(a1a2a3)=a3a2a1=a3a2*10+a1=reverse(a2a3)*10+a1reverse(a0a1a2a3)=a3a2a1a0=a3a2a1*10+a0=reverse(a1a2a3)*10+a0,74,判断回文数-算法1,75,判断回文数-算法2,76,#includemain()int num;/存放输入的整数 int num1;/*循环中处理的数,每循环一次,右边少一位,假设num为1234,则num1初始值为1234,然后是123,然后是12.;*/int reverse;/*是用分解出来的数字组成的新数*/int m;/*m:存放每一个分解出来的数字;*/printf(请输入一个小于8位的正整数:);/读取要判断的整数 scanf(%d,77,总结：循环结构解题,很多题目都需要循环结构进行求解。当一时难以整理出每次循环（迭代）所做的事情时，可以先看一下如果这件事情交给人做的话，一步一步是怎么做的。在上一步基础上抽象出循环结构的四个方面。,78,总结：循环结构解题,2和3一般没有绝对的先后顺序。在分析清楚2和3后，才分析4（为什么？）。一般将1放在最后分析,在4中，要对出现在2和3中的某些变量进行修改，为下次循环做好准备，并使得循环能最终结束。思考上述四项工作有无先后顺序？应该是什么顺序？,79,总结：对一批数进行处理的模式,循环次数未知,循环次数已知,80,4.1 算法的概念4.2 算法的三种基本结构4.3 算法的描述方法4.4 结构化程序设计方法4.5 算法设计实例研究,提纲,81,例4.14 设计交通车辆观测统计算法。问题描述：在一个路口设置一个探测器，通过通信线路连接到后台的计算机。路口每通过一辆汽车，探测器向计算机发出一个车辆信号1，探测器每隔1秒钟向计算机发出一个时钟信号0，观测结束向计算机发出结束信号。要求在计算机上设计一个程序，能够接收探测器发出的信号，统计出观测的时长、在观测时长内通过的车辆总数、以及两辆车之间最大的时间间隔。,问题分析：探测器向计算机发出的信号可以认为是一个任意长的字符序列（以#结束），比如：“，这样设计程序实际上演变为读取该字符序列，然后进行相关的操作。,1,4.5 算法设计实例研究,观测时长：字符序列中0的个数(6秒)；车辆总数：字符序列中1的个数(9辆)；两车间最大时间间隔：两个1之间的最大连续0的个数(3秒)；,探测器,82,计算观测时长（0的个数）和车辆总数（1的个数）是容易实现的，但是如何计算最大时间间隔需要进一步考虑。在对一个比较复杂的问题进行分析时，我们应该采用分而治之的方法，将复杂的问题分解为相对比较简单的问题，再针对该较简单问题进行求解。我们首先设计算法主体框架。,“0000110100011010#”,！注意：2006年9月出版的教材假设接收到的信号总是以1开始，因此算法会有所简化,83,“0000110100011010#”,signal!=#,待细化,84,85,Level 1层算法设计,第0层算法,第1层算法,86,“0000110100011010#”,分析：处理时钟信号0,观测时长seconds加1；两种情况。如果此前已接收到车辆信号1(如何判断？)，则间隔时长interval加1；否则不做任何处理。,87,“0000110100011010#”,分析：处理车辆信号1第一种：“00001（这是第一个1）车辆总数vehicles加1第二种：“0000110100011010#”（不是第一个1，且前一个信号也是1）车辆总数vehicles加1第三种：“0000110100011010#”（不是第一个1，且前一个信号是0）车辆总数vehicles加1处理是否要更新最长时间间隔（interval：两车之间的时间间隔，longest：两车之间的最长时间间隔）,88,“0000110100011010#”,分析：处理车辆信号1,vehicles vehicles+1；情况1：第一个1 判断式：vehicles=1情况2：不是第一个1，且前一个信号也是1 判断式：vehicles1&interval=0情况3：不是第一个1，且前一个信号是0:判断式：vehicles1&interval0 处理：1）若intervallongest 则 longest interval。2）interval0。,情况1,情况3,情况2,89,“0000110100011010#”验证算法,【程序演示】,90,#includemain()int vehicles;/记录车辆信号总数 int seconds;/记录时钟信号总数 int longest;/记录最长时间间隔 int interval;/记录时间间隔 char signal;/存放读取的信号/*初始化设置*/vehicles=0;seconds=0;longest=0;interval=0;printf(please input signal:n);scanf(%c,/*读入第一个信号*/,91,/*循环结构处理输入信号的字符序列,边读取边处理*/while(signal!=#)if(signal=1)/*处理车辆信号*/vehicles=vehicles+1;if(vehicles1,92,/*输出结果*/printf(%d vehicles passed in%d secondsn,vehicles,seconds);printf(the longest gap was%d secondsn,longest);system(PAUSE);return 0;,93,练习：将一个由数字字符组成的字符串转换为整数或者小数并输出。如：输入:134.567#输出:134.567,94,#includemain()char ch;int num;/存放小数点前面的字符转换后得到的整数 float fnum;/存放小数点后面的字符转换后得到的浮点数 int n;/存放字符对应的数字 int p;/存放小数点后面的字符转换后得到的数字对应的基数1/p。小数点后第一位数的基数是1/10 int flag;/用于表示输入的字符中是否有小数点。若有，则flag值为1；否则为0 num=0;fnum=0;p=10;flag=0;printf(please input the string:);,算法1：读情况对字符进行处理,95,scanf(%c,96,if(flag=0)printf(the result is:%dn,num);else printf(the result is:%fn,num+fnum);system(pause);return 0;,97,#includemain()char ch;int num;float fnum;int n;int p;printf(please input the string:);/处理整数部分 num=0;scanf(%c,算法2：先循环处理小数点前面的字符，再循环处理小数点后面的字符,98,if(ch=.)/处理小数部分 p=10;scanf(%c,99,迭代算法,迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。利用迭代算法解决问题，需要做好以下三个方面的工作 确定迭代变量ai。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。建立迭代关系式，即aif(ai-1)对迭代过程进行控制。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。,100,例4.15 猴子吃桃问题：有一堆桃子不知数目，猴子第一天吃掉一半，觉得不过瘾，又多吃了一只，第二天照此办理，吃掉剩下桃子的一半另加一个，天天如此，到第十天早上，猴子发现只剩一只桃子了，问这堆桃子原来有多少个？,4.5 算法设计实例研究,101,分析：假设第一天早上吃前有桃子a1个,第二天早上吃前有桃子a2个，第三天早上吃前有桃子a3个，以此类推，则a2a1（a1/2+1）=a1/2-1a9a8（a8/2+1）=a8/2-1 a10a9（a9/2+1）=a9/2-1=1,可见，在已知a10的情况下，可以求得a9，已知a9可以求得a8最终求得a1,102,即：a9=2(a10+1)a8=2(a9+1)a1=2(a2+1)也就是：ai2(ai+1+1)i=9,8,7,6,.,1现在已知a10值为1，可以采用迭代法求得a1。,103,104,依次计算出第9天、第8天第1天吃前的桃子数,current_day_count 表示当天的桃子数，代表数学模型中的ai。初始值是1，代表第10天早上的桃子数是1。day_count 表示第几天，代表数学模型中的i。初始值为9，代表第一次循环求的是第9天早上的桃子数。,【程序演示】,105,#includemain()int day；/表示当前求解的是第几天吃前的桃子数 int peach;/示某一天的桃子数 day=9;/第一次循环求第9天吃前的桃子数 peach=1;/第10天吃前的桃子数是1 while(day=1)peach=2*(peach+1);day=day-1;printf(桃子数是：%d,peach);system(pause);,106,第一天：1534个桃子第二天：766个桃子第三天：382个桃子第四天：190个桃子第五天：94个桃子第六天：46个桃子第七天：22个桃子第八天：10个桃子第九天：4个桃子第十天：1个桃子,Common Problems:Sentence 1;Sentence 2;(if,while,for)main(),107,108,逗号运算符和逗号表达式,逗号运算符，用于把几个表达式串在一起。逗号表达式 含有逗号运算符的表达式，实现对各个表达式的顺序求值，主要用于for语句中。执行过程 先计算表达式1，然后依次计算其后的各个表达式的值，并将最右边那个表达式的值作为逗号表达式的值。,y=1 0;x=(y=y-5,30/y);,/运算后y=5，x=6。/逗号表达式优先级比赋值表达式低，所以必须加括号,109,总结：循环结构解题,很多题目都需要循环结构进行求解。当一时难以整理出每次循环（迭代）所做的事情时，可以先看一下如果这件事情交给人做的话，一步一步是怎么做的。在上一步基础上抽象出循环结构的四个方面。,110,总结：循环结构解题,2和3一般没有绝对的先后顺序。在分析清楚2和3后，才分析4（为什么？）。一般将1放在最后分析,在4中，要对出现在2和3中的某些变量进行修改，为下次循环做好准备，并使得循环能最终结束。思考上述四项工作有无先后顺序？应该是什么顺序？,111,总结：对一批数进行处理的模式,循环次数未知,循环次数已知,112,迭代算法,迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。利用迭代算法解决问题，需要做好以下三个方面的工作 确定迭代变量ai。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。建立迭代关系式，即aif(ai-1)对迭代过程进行控制。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。,113,练习6：一个皮球从100m高处落下，每次落地后反弹到原来高度的一半。编写程序，求20次反弹时弹起的高度。,【程序演示】,分析：a0=100a1=a0/2a2=a1/2a20=a19/2,114,#include#define TIMES 20 main()int times;/记录是第几次弹起 double height;/记录小球弹起时的高度 height=10000.0;/*height的单位是cm*/times=1;/*第一次循环求第1次弹起高度*/while(times=TIMES)height=height/2;/*除以2后的height表示第times次弹起的高度*/times=times+1;printf(第%d次小球弹起的高度是%f厘米,TIMES,height);return 0;,115,练习7：在许多情况下，知道一个数是否是素数还不够，有时，还需要知道它的约数。每个大于1的正整数都能表示为素数的乘积。这个因数分解是唯一的，被称为素数分解（prime factorization）。例如，数字60=2*2*3*5,799=17*47,其中每一个约数都是素数。注意，同一个素数在因数分解中可以出现多次。设计一个算法显示数n的素数分解。要求用自顶向下、逐步求精的方法设计算法。,116,问题分析：60=2*2*3*5f(p)=n*f(p/n),n是p的最小质数因子对p进行素数分解，可以转化为两步：1：找到p的最小质数因子n；2：对p/n继续进行素数分解；,117,素数分解算法1：,118,f(p)=n*f(p/n),p从2开始试探，逐渐变大（加1）。若试探过程中发现p能被n整除，则n肯定是素数。原因分析：根据题意，任何合数均能分解为若干个素数的乘积。假设n为6且p除以n余数为0，则n=6*，由于62*3,因此n=2*3*，在分解出6之前早就已经分解得到2*3了，所以 p不可能为6。其他的合数也是如此。,素数分解算法2：,119,穷举法解题,穷举法解题 解题思路：对可能是解的众多候选解按某种顺序进行逐一枚举和检验，从中找出那些符合要求的候选解作为问题的解。如：打印所有除以11后所得商正好是它的各个数字平方和的三位数。,120,穷举法解题,例1：编写程序，求出所有5、6、7组成的、且各位数字互不相同的三位数。,明确所有的组合情况百位可以是5,6,7十位可以是5,6,7个位可以是5,6,7检查是否满足约束条件百、十、个位互不相同,对候选解进行检验并输出,121,穷举法解题,算法优化：,【程序演示】,122,5、6、7组成的数,#include main()int high,mid,low;/依次记录最高位、中间位、最低位数字 int count=0;printf(5、6、7可组成的且各位数字互不相同的数有：n);for(high=5;high=7;high+)for(mid=5;mid=7;mid+)if(high!=mid)for(low=5;low=7;low+)if(low!=high,123,穷举法解题,例2：5位跳水高手将参加10m高台跳水决赛，好事者让5人据实力预测比赛结果。A选手说：B第二，我第三；B选手说：我第二，E第四；C选手说：我第一，D第二；D选手说：C最后，我第三；E选手说：我第四，A第一。决赛成绩公布后，每位选手的预测都说对了一半，即一对一错。请设计算法求出比赛的实际名次。,124,明确组合情况：A可以是第一、第二、第三、第四或者第五B可以是第一、第二、第三、第四或者第五C可以是第一、第二、第三、第四或者第五D可以是第一、第二、第三、第四或者第五E可以是第一、第二、第三、第四或者第五检查是否满足约束条件：A说：B第二，A第三；B说：B第二，E第四；C说：C第一，D第二；D说：C第五，D第三；E说：E第四，A第一。而且都只说对了一半。,穷举法解题,125,例2算法主体框架,126,检测条件：,A说：B第二，A第三；B说：B第二，E第四；C说：C第一，D第二；D说：C第五，D第三；E说：E第四，A第一。而且都只说对了一半。,(b=2&a!=3|b!=2&a=3)&(b=2&e!=4|b!=2&e=4)&(c=1&d!=2|c!=1&d=2)&(c=5&d!=3|c!=5&d=3)&(e=4&a!=1|e!=4&a=1),countA=(b=2)+(a=3);countB=(b=2)+(e=4);countC=(c=1)+(d=2);countD=(c=5)+(d=3);countE=(e=4)+(a=1);if(countA=1&countB=1&countC=1&countD=1&countE=1),127,比赛名次-1,main()int a,b,c,d,e;/用于记录AE分别的名次 int countA,countB,countC,countD,countE;/用于记录AE分别说对的话个数 for(a=1;a=5;a+)/ae分别代表AE选手的名次 for(b=1;b=5;b+)if(a!=b)for(c=1;c=5;c+)if(c!=a,128,比赛名次-2,main()int a,b,c,d,e;/用于记录AE分别的名次 int countA,countB,countC,countD,countE;/用于记录AE分别说对的话个数 for(a=1;a=5;a+)/ae分别代表AE选手的名次 for(b=1;b=5;b+)if(a!=b)f