基于AI的C语言程序设计（微课版）课件 第2章 算法

第2章

算法算法思维：从生活到代码主

讲

:蒋亚平目录CONTENTS算法的概念算法的表示结构化程序设计方法本章小结01020304问题导入算法的表示方法要给班级30名学生的C语言成绩排序（从高到低），你能想到哪些办法？用“口头描述”“画图”“简单代码片段”三种方式分别怎么表达你的思路？这些不同的表达形式对应算法的哪几种表示方法？算法性能图书馆要从1000本图书中找到某本指定ISBN的书，“逐本翻找”和“按书架编号定位”哪种更快？这两种方式的差异，其实对应了算法的什么核心属性？01算法的概念算法的概念算法的定义算法是解决特定问题的一系列明确且有序的步骤，它指导计算机完成任务。无论是简单的数值计算还是复杂的人工智能应用，其核心都是由精心设计的算法构成。算法与生活的联系生活中，许多事情的完成都遵循着固定且有序的流程，如看电影、家常炒菜、排队买咖啡等。这些流程都可以抽象为算法，体现了算法的普遍性和实用性。算法的多样性对于同一问题，往往存在多种不同的算法。例如计算1到100的和，可以用数学公式直接计算，也可以通过逐个累加的方式实现，但两者的效率差异显著。算法是解决问题的步骤010203特性的重要性通过泡茶的例子，我们可以看到算法的五大特性在实际应用中的重要性。这些特性帮助我们筛选出高质量的算法，确保算法能够正确、高效地解决问题。算法的五大特性算法必须满足有穷性、确定性、可行性、输入和输出五大特性。这些特性确保算法能够在有限步骤内结束，每个步骤明确无歧义，且可通过有限操作实现。五大特性筛出好算法计算1到100的和加2克盐计算两个数的乘积烧开水→洗茶杯→放茶叶→冲开水→静置3分钟一直烧开水+违反了有穷性02算法的表示算法的表示五种算法表示自然语言流程图N-S图编程语言伪代码问题场景校园内有5个快递点（标记为A、B、C、D、E），各点之间的距离如图2-1所示（单位：米），虚线表示不可达。快递员从A点出发，需将包裹送到其他4个点，求从A到每个目标点的最短路径及距离。自然语言校园快递路径第一步，先把A到每个点的距离记下来；第二步，从还没确定最短距离的点里，选一个离A最近的点，标记为‘已确定’；第三步，用这个已确定点的距离，更新它到其他未确定点的距离；......自然语言的优势自然语言描述算法步骤的优点是简单直观，适合初步表达简单的算法逻辑。例如，校园快递路径规划问题可以用自然语言描述初始化、选点、松弛等步骤。自然语言的局限性自然语言描述算法容易产生歧义，对于复杂的逻辑，自然语言的描述可能不够精确，导致理解和执行的偏差。因此，对于复杂的算法，需要使用更精确的表示方法。自然语言流程图的基本符号流程图使用椭圆表示开始或结束，菱形表示判断条件，矩形表示处理步骤，平行四边形表示输入或输出操作，箭头表示流程的方向。流程图：图形化控制流流程图符号连接点示例：判断一个数是否为偶数。流程图：图形化控制流示例：在100名学生中，统计成绩高于85分的学生人数，并输出该人数。流程图的优势流程图通过图形符号直观地展示算法的执行流程，便于理解和实现。它可以帮助我们清晰地表示算法的顺序、分支和循环结构。流程图：图形化控制流流程图的局限性当流程图中的流程线过多时，可能会导致图形复杂，可读性下降。此外，流程图的修改相对繁琐，不如其他表示方法灵活。N-S图：结构化无流线顺序结构选择结构多分支选择结构当型循环结构直到型循环结构三种基本结构：Bohra和Jacopini提出了顺序结构、选择结构和循环结构三种基本控制结构。N-S图：结构化无流线顺序结构选择结构循环结构N-S图表示算法：N-S图是一种结构化的算法表示工具，由美国学者I.Nassi和B.Shneiderman提出，因此得名。通过基本结构的顺序组合即可表达复杂的算法，因此，基本结构之间的流程线变得不再必要。N-S图正是为解决这一问题而设计的。N-S图：结构化无流线示例：判断素数：N-S流程图设计与实践。N-S图的特点N-S图取消了传统流程图中的流程线，通过矩形框等符号紧凑地组合在一起，更适合表示顺序、选择和循环这三种基本结构。N-S图：结构化无流线N-S图的优势和缺点优点：N-S图结构紧凑，无流程线混乱问题，强制使用结构化思想，适合初学者梳理逻辑。它可以帮助我们避免逻辑混乱，使算法结构更加清晰。缺点：不够灵活，如果算法有特别多的嵌套，框会越套越深，看起来有点拥挤。伪代码的定义伪代码是介于自然语言和编程语言之间的算法描述方式，它不严格遵守语法规则，但保留了编程语言的结构化关键词，如IF、WHILE等。伪代码的优势伪代码是一种灵活易懂的算法表示方法，无需关注语法细节，能快速表达算法核心逻辑，适合团队沟通或前期设计。伪代码的局限性伪代码无法直接运行，必须转化为编程语言才能执行。因此，在设计算法时，伪代码是将逻辑转化为可运行程序的重要过渡工具。伪代码：自然到代码的桥梁伪代码：自然到代码的桥梁begin result=1 i=2 whilei≤10 { result=result*i i=i+1 } printresultendbeginn=9 w=0 i=2 whilei≤nandw==0 { result=n%i ifresult==0 w=1 else i=i+1 } ifw==0 print"n是素数" else print"n不是素数"end示例：计算10的阶乘（10!）。示例：判断素数伪代码：自然到代码的桥梁begin//初始化

距离矩阵dist[5][5]={ {0,10,20,INF,INF},//A到各点的距离

{10,0,5,15,INF},//B到各点的距离

{20,5,0,INF,30},//C到各点的距离

{INF,15,INF,0,5},//D到各点的距离

{INF,INF,30,5,0}//E到各点的距离

};

起点=A

最短距离数组shortest[]={0,无穷大,无穷大,无穷大,无穷大}//索引对应A,B,C,D,E

路径记录数组path[]={"A","","","",""}//记录每个点的最短路径

已确定标记数组visited[]={true,false,false,false,false}//A初始为已确定示例：校园快递路径规划伪代码。//循环while未确定的点数量>0{

从visited[i]==false的点中，找到shortest[i]最小的点P

标记visited[P]=true

对每个点Q（Q≠P且visited[Q]=false）：

若shortest[P]+dist[P][Q]<shortest[Q]：

shortest[Q]=shortest[P]+dist[P][Q]path[Q]=path[P]+"→"+Q}//输出

对每个点Q：

打印“从A到Q的最短距离：shortest[Q]米，路径：path[Q]”end编程语言：算法的最终落地编程语言：是算法的“最终实现形式”，它严格遵守语法规则，能被计算机直接执行。示例：用C语言实现图书馆借书算法。#include<stdio.h>#include<string.h>//模拟数据：借书证是否有效（1=有效）、图书状态（1=可借）、当前借阅数量intisCardValid=1;intbookStatus=1;intborrowCount=3;intmain(){charcardID[20],isbn[20];printf("请输入借书证号：");scanf("%s",cardID);printf("请输入图书ISBN号：");scanf("%s",isbn);//步骤1：验证借书证if(isCardValid!=1){printf("借书证无效，无法借书\n");return0;//算法结束}//步骤2：查询图书状态if(bookStatus!=1){printf("图书已被借出，请稍后再借\n");return0;}//步骤3：检查借阅数量if(borrowCount>=5){printf("借阅数量已达上限，无法借书\n");return0;}//步骤4：登记信息并输出结果borrowCount++;//借阅数量+1printf("借阅成功，当前借阅数量：%d，应还日期：30天后\n",borrowCount);return0;}编程语言：算法的最终落地示例：校园快递路径规划的简单代码框架。#include<stdio.h>#defineINF10000//表示无穷大（假设校园内最大距离小于10000米）

intmain(){//距离矩阵：dist[i][j]表示点i到点j的距离（0:A,1:B,2:C,3:D,4:E）

intdist[5][5]={{0,10,20,INF,INF},//A到各点的距离

{10,0,5,15,INF},//B到各点的距离

{20,5,0,INF,30},//C到各点的距离

{INF,15,INF,0,5},//D到各点的距离

{INF,INF,30,5,0}//E到各点的距离

};

intshortest[5]={0,INF,INF,INF,INF};//最短距离数组

char*path[5]={"A","","","",""};//路径数组（简化表示）

intvisited[5]={1,0,0,0,0};//1表示已确定

//此处省略算法核心循环（详细实现见第12章）

printf("从A到B的最短距离：%d米，路径：A→B\n",10);//示例输出

printf("从A到C的最短距离：%d米，路径：A→B→C\n",15);//示例输出

return0;}运行结果：03结构化程序设计方法自顶向下的设计方法自顶向下设计是一种从整体到局部的设计方法。首先确定程序的整体结构，然后逐步细化每个部分的功能，直到所有细节都得到明确。逐步细化的过程逐步细化是指将程序设计分解为层次结构，逐步从高层的抽象逻辑向低层的实现细节进行细化。每个模块都可以独立开发和测试，最终通过组合这些模块来实现完整的程序。自顶向下与逐步细化模块化设计的定义模块化设计是将程序分割成多个相互独立的模块，每个模块完成特定的功能。模块之间通过接口进行通信，模块内部的实现细节对外部不可见。模块化设计的优势模块化设计使得程序更加易于维护和扩展，并且能够有效减少程序中错误的传播。通过将复杂的程序分解为多个模块，可以提高程序的可读性和可维护性。接口隔离的重要性接口隔离是模块化设计中的一个重要概念。通过明确模块之间的接口，可以确保