算法设计流程图

第2章算法及算法的流程图表示
数据结构+算法=程序
2.1算法的概念及特性
2.1.1算法的概念
2.1.2算法的特性
2.2算法的流程图表示
2.2.1传统流程图
起止框
处理框
输入输出框
判断框
流程线
连接点
注释框
图2.1 常用的流程图符号
图2.2 求解例2.1的流程图
2(x 0)
2x 3y 0
(x 0)x 1
(x 0)
>⎧+⎪==⎨
⎪+<
⎩
图2.3 求解例2.2的流程图 图2.4 求解例2.3的流程图
2.2.2 结构化程序的3种基本结构
图2.5 顺序结构图2.6 分支结构图2.7 当型循环结构图2.8 直到型循环结构2.2.3结构化流程图
A B
p
成立不成立
A B
当条件p成立
A
直到条件p成立
A
图2.9 顺序结构图2.10 分支结构图2.11 当型循环结构图2.12 直到型循环结构
输入x
x>0?
是否
y=2*x+3 是否
y=0 y=x*x+1
x==0?
输出y aver=0；count=0
输入x
aver=aver+x;count=count+1;
输入x
当x≠0时
aver=aver/count
输出aver
图2.13 例2.2的N-S图图2.14 例2.3的N-S图
习题2。

算法流程图、算法语句一、学习目标：1.了解算法的含义；2.了解算法流程图；了解基本算法语句。

二、知识梳理：1.算法通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是 和 的，而且能够在有限步之内完成.2. ，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形. 流程图是由 和带 组成的，其中图框表示各种操作的 ，图框中的 和 表示操作的内容，带箭头的流线表示操作的 .3.顺序结构是由若干个依次执行的处理步骤组成的，这是任何一个算法都离不开的基本结构.其结构形式为 。

4.选择结构是指算法的流程根据给定的条件是否成立而选择执行不同的流向的结构形式. 其结构形式为 。

5.循环结构是指从某处开始，按照一定条件，反复执行处理某一步骤的情况.反复执行的处理步骤称为 .循环结构又分为 和 .其结构形式为6.几种基本算法语句：赋值语句、输入语句、输出语句、条件语句、循环语句.三、基础训练：1.下列问题的算法适宜用选择结构表示的是 (填序号).①求点P （-1，3）到直线l:3x-2y+1=0的距离;②由直角三角形的两条直角边求斜边③解不等式ax+b>0(a ≠0) ;④计算100个数的平均数2.如图，该程序运行后输出的结果为 .3.（2010·常州模拟）下列伪代码运行的结果是 .S ←1For I From 1 To 7 Step 2S ←S ×IEnd ForPrint S4.右边4种框图结构中，是直到型循环结构的为 （填序号）.5.已知伪代码：Read aIf a<10 Theny ←2×aElsey ←a ×aEnd IfPrint yEnd四、典型例题:例1、 已知点),(00y x P 和直线l:Ax+By+C=0，求点),(00y x P 到直线l 的距离d ，写出其算法并画出流程图. 变式训练：写出解二元一次方程组 的算法.⎩⎨⎧=+-=-②13①33y x y x例2、画出计算222222100994321-++-+-Λ的值的流程图.变式训练：函数 写出求该函数值的算法并出画流程图.例3、（2009·江苏）如图是一个算法的流程图，最后输出的W= .变式训练：（2009·山东改编）执行下边的流程图，输出的T= .例4、如图所示，在边长为4的正方形ABCD 的边上有一点P ，沿着折线BCDA 由点B(起点)向点A(终点)运动.设点P 运动的路程为x ，△APB 的面积为y ，求y 与x 之间的函数关系式，画出流程图，写出伪代码.变式训练：编写一组伪代码计算 的值，并画出相应的流程图. ,)0(1)0(0)0(1⎪⎩⎪⎨⎧<=>-=x x x y 0001131211++++Λ五、课堂练习：1.（2010·无锡模拟）阅读下面的流程图，若输入的a、b、c分别是21、32、75，则输出的a、b、c分别是.2.（2009·兴化市板桥高级中学12月月考）下图的流程图输出的结果为.3.（2009·盐城模拟）定义函数CONRND（a，b）是产生区间（a，b）内的任何一个实数的随机数函数.如图所示的流程图可用来估计π的值.现在N输入的值为100,结果m的输出值为21，则由此可估计π的近似值为.4.（2009山东淄博模拟）阅读下面的流程图，若a=50.6,b=0.65,c=log0.55，则输出的数是.5.（2009·扬州模拟）以下给出的是用条件语句编写的一个伪代码，该伪代码的功能是.6.（2010·镇江模拟）下面是一个算法的伪代码，其运行的结果为.7.（2009·江苏南通模拟）阅读下列伪代码：其输出的结果是.8.（2010·青岛调研）下列伪代码描述的问题是.9.（2009·皖南八校联考）下列程序中，算法Ⅰ的功能为；算法Ⅱ的功能为.算法Ⅰ：算法Ⅱ：10.（2010·江苏南京模拟）已知f（x）=2x-2x-3,求f（3）、f（-5）、f（5）,并计算f（3）+f（-5）+f（5）的值.设计出解决该问题的一个算法，并画出流程图.11.（2010·中山模拟）某玩具厂1996年的生产总值为200万元，如果年生产增长率为5%，计算最早在哪一年生产总值超过300万元.试写出伪代码.12.（2010·苏州模拟）有一个算法如下：S1 输入x;S2 判断x>0是：z←1；否：z←-1;S3 z←1+z;S4 输出z.试写出上述算法的流程图及相应的伪代码.。

c语言程序设计流程图详解介绍常见的流程图符号及流程图的例子。

本章例1 — 1的算法的流程图如图1 — 2所示。

本章例1 - 2的算法的流程图如图1 — 3所示。

在流程图中，判断框左边的流程线表示判断条件为真时的流程，右边的流程线表示条件为假时的流程，有时就在其左、右流程线的上方分别标注“真”、“假"或“T”、“F"或“Y”、“N”注“真"、“假"或“T”、“F”或“Y”、“N"另外还规定，流程线是从下往上或从右向左时,必须带箭头,除此以外,都不画箭头，流程线的走向总是从上向下或从左向右。

2. 算法的结构化描述早期的非结构化语言中都有go to语句，它允许程序从一个地方直接跳转到另一个地方去. 执行这样做的好处是程序设计十分方便灵活，减少了人工复杂度，但其缺点也是十分突出的,一大堆跳转语句使得程序的流程十分复杂紊乱，难以看懂也难以验证程序的正确性，如果有错,排起错来更是十分困难.这种转来转去的流程图所表达的混乱与复杂,正是软件危机中程序人员处境的一个生动写照。

而结构化程序设计，就是要把这团乱麻理清。

经过研究，人们发现,任何复杂的算法,都可以由顺序结构、选择(分支）结构和循环结构这三种基本结构组成,因此，我们构造一个算法的时候，也仅以这三种基本结构作为“建筑单元”，遵守三种基本结构的规范,基本结构之间可以并列、可以相互包含,但不允许交叉，不允许从一个结构直接转到另一个结构的内部去。

正因为整个算法都是由三种基本结构组成的，就像用模块构建的一样，所以结构清晰，易于正确性验证,易于纠错，这种方法，就是结构化方法。

遵循这种方法的程序设计,就是结构化程序设计。

相应地，只要规定好三种基本结构的流程图的画法，就可以画出任何算法的流程图。

(1) 顺序结构顺序结构是简单的线性结构，各框按顺序执行。

其流程图的基本形态如图1 - 4所示，语句的执行顺序为：A→B→C.（2）选择（分支)结构这种结构是对某个给定条件进行判断，条件为真或假时分别执行不同的框的内容。

Dijkstra算法的流程图需求和规格说明：Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止.Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低.算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径,再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列，但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品,对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜.清楚了算法的这种巧妙构思后，理解算法本身就不是难题了.实现注释：想要实现的功能：Dijkstra算法是用来求任意两个顶点之间的最短路径。

在该实验中，我们用邻接矩阵来存储图。

在该程序中设置一个二维数组来存储任意两个顶点之间的边的权值。

用户可以将任意一个图的信息通过键盘输入，让后在输入要查找的两个顶点，程序可以自动求出这两个顶点之间的最短路径.已经实现的功能:在该实验中，我们用邻接矩阵来存储图。

在该程序中设置一个全局变量的二维数组,用它来存储任意两个顶点之间的边的权值。

然后通过最短路径的计算,输入从任意两个顶点之间的最短路径的大小。

用户手册：对于改程序，不需要客户进行什么复杂的输入，关键是用来存放图的任意两个顶点之间的边的权值的二维数组的初始化,即将要通过Dijkstra算法求最短路径的图各条边的权值放入二维数组中。

这样程序就可以自动的计算出任意两个顶点之间的最短路径并且进行输出.设计思想：s为源，w［u，v] 为点u 和v 之间的边的长度，结果保存在 dist［]初始化：源的距离dist[s]设为0，其他的点距离设为无穷大，同时把所有的点状态设为没有扩展过。

循环n-1次：1. 在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展.2. 对于每个与u相邻的点v，如果dist［u] + w［u，v] < dist［v］，那么把dist ［v]更新成更短的距离dist［u］ + w[u，v]。

传统流程图（⽤于设计分析算法）
流程图是每⼀个程序编制⼈员都应当熟练掌握的！
只要规定好三种基本结构的流程图的画法，就可以画出任何算法的流程图！
三种基本结构：
1.顺序结构：
顺序结构是最简单的⼀种线性结构。

执⾏顺序：执⾏完A后必定会执⾏B。

2.选择结构：
此结构中必包含⼀个判断框！根据给定的条件是否成⽴⽽选择执⾏A框或者B框！（⽆论⾛哪⼀条路线，在执⾏完之后均会通过最终交汇的点，然后脱离本选择结构）
执⾏顺序：图a）当条件为真时执⾏A，否则执⾏B；
图b）的执⾏序列为：当条件为真时执⾏A，否则什么也不做。

3.循环结构：（⼜称为重复结构，即反复执⾏某⼀部分的操作，有while和until两类循环结构）
第⼀类：当型（while型）循环结构
当给定的条件成⽴时，执⾏A框操作，执⾏完A后，再判断条件还成不成⽴，若仍成⽴，再执⾏A框。

如此反复执⾏A框，直到有⼀次条件不成⽴，从条件不成⽴的点直接脱离该结构
第⼆类：直到型（until型）循环结构
⼀开始直接执⾏A框，然后才判断条件是否成⽴，若条件成⽴，则再执⾏A框，然后再判断。

如此反复，直到条件不成⽴，直接脱离本结构。

总结：以上三种结构的共同点
1.都只有⼀个⼊⼝
2.都只有⼀个出⼝
3.结构内的每⼀部分都有机会被执⾏到
4.结构中不存在死循环。

程序算法描述流程图程序算法流程图算法的方法递推法递推是序列计算机中的一种常用算法。

它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。

其是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

递归法程序调用自身的编程技巧称为递归(recurion)。

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。

一般来说，递归需要有边界条件、递归前进段和递归返回段。

当边界条件不满足时，递归前进;当边界条件满足时，递归返回。

注意：(1)递归就是在过程或函数里调用自身;(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

穷举法穷举法，或称为暴力破解法，其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解。

它也常用于对于密码的破译，即将密码进行逐个推算直到找出真正的密码为止。

例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。

理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。

因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。

贪心算法贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。

用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。