第4章 程序设计基础

程序设计基础“程序设计基础”站：？？？①你知道写程序之前要先设计“算法”吗？②你了解“算法”的概念吗？③从“算法”到“程序”还有多远？④你觉得人工智能会替代人类吗？⑤你想不想了解一下“全球最强大脑”——“12306”？第4章

程序设计基础2Basis

ofProgramDesign过去的这半年，是重庆有史以来最艰难的半年引例Example如何在摩托车的背篓里面装入价值最高多的东西？——背包问题把物资送到多个灭火点怎么走路径最短？——旅行商问题设置核酸检测点的位置如何选择，可以使得该检测点覆盖区域内的大部分居民更方便到检测点？——覆盖算法各个检测点的器材损耗表发给你了，如何最快的完成从大到小的排序，完成器材补给？——快速排序算法引例Example超越珠穆朗玛峰有一张足够大的纸，其厚度为0.1毫米，请问，将它对折多少次之后，其厚度将超过珠穆朗玛峰（珠穆朗玛峰的高度为8848.68米）？这个题的算法流程图怎么画？代码如何编写？引例Example课程教学目标s=0.0001i=0whiles<8848.86:s=s*2i+=1print("折叠",i,"次后超过珠穆朗玛峰的高度。")s=0.0001i=0S<8848.68s=s*2是否输出ii=i+1开始结束目标1能够绘制流程图目标2能够大致读懂一些简单代码目录

Contents目录Contents4.1程序和软件壹4.2算法概述贰4.3程序设计语言叁4.4程序设计的方法和步骤肆4.1程序和软件壹COMPUTERPROGRAMANDSOFTWARE回顾计算机工作原理-“存储程序通用电子计算机方案”冯•诺依曼计算机硬件系统由五大部件组成计算机硬件系统由运算器、控制器、存储器、输入设备以及输出设备组成。存储程序通过输入设备输入数据和指令到计算机中存储起来，然后CPU从存储器中取出指令、分析指令、执行指令，直到所有指令全部执行完，最后通过输出设备将结果显示出来信息用二进制格式存储和表示中，无论何种信息，都是用“0”和“1”来表示，即二进制数。活动1程序和软件COMPUTERPROGRAMANDSOFTWARE程序？计算机为完成某个任务所必须执行的一系列指令的集合。软件?程序=算法+数据结构NicklausWirth尼古拉斯·沃斯凭借一句话获得图灵奖的Pascal之父程序设计?将求解某个问题的算法，用计算机语言实现的过程。程序设计=计算机（编程）语言+算法+数据结构。软件包括一个在一定规模和体系结构的计算机中执行的程序，以及软件开发过程中涉及的各种文档和以各种形式存在的数据。软件=程序+支持模块+数据模块。活动24.2算法贰ALGORITHM4.2.1算法概述4.2.2算法表示4.2.3流程图表示算法4.2.4算法应用引例Example《未来简史》尤瓦尔·赫拉利在《未来简史》中以宏大的视角审视人类未来的终极命运，表达出惊人的预测：“生命本身就是不断处理数据的过程，生物本身就是算法；计算机和大数据，将比我们自己更了解自己。未来，只有1%的人将完成下一次生物进化，升级成新物种，而剩下99%的人将彻底沦为无用阶级！”算法的概念是。。。算法ALGORITHM

4.2.1算法概述活动3算法：为解决某一问题对采取的有限的方法或步骤的描述。算法ALGORITHM

4.2.1算法概述活动3算法ALGORITHM

Example#1:菜谱Example#2：一首曲子Example#3：看电影Step1：买票Step2：检票Step3：入场Step4：观看Step5：离场算法ALGORITHM

Example#4:输入秒数，转化成对应的“小时：分：秒“形式输出Example#5：求两个数中的最大数。Example#6：计算1+2+3+……+100的和输入总秒数x计算小时h计算分钟m计算秒数s显示h:m:s输入第一个数a输入第二个数ba>b?输出第二个数b输出第一个数aYs=0i=1i<=100s=s+ii=i+1Y输出sNN算法ALGORITHM1、算法的特征一个算法必然是由一系列操作组成的，比如加、减，比较大小，逻辑判断，输入、输出数据等；这一系列的操作必然是按一定的控制结构的规定来执行的，这里的控制结构即为顺序、选择、循环这三种基本结构。顺序结构选择结构循环结构活动4算法ALGORITHM2、算法的性质有穷性确定性大于等于0个输入大于等于1个输出可执行性随机几何图活动54.2算法贰ALGORITHM4.2.1算法概述4.2.2算法表示4.2.3流程图表示算法4.2.4算法应用引例Example《礼记·中庸》《礼记·中庸》书中有一句话：“凡事预则立，不预则废；言前定，则不乱；事前定，则不困；行前定，则不疚；道前定，则不穷。”毛泽东同志在引用这句名言时说：“凡事预则立，不预则废。没有事先的计划和准备，就不能获得战争的胜利。”为什么要设计算法？算法ALGORITHM

自然语言描述算法传统流程图N-S流程图伪代码PAD图计算机语言4.2.2算法表示算法ALGORITHM1、自然语言描述例：求输入数的绝对值。Step1：把数据输入到一个存储空间中；Step2：判断存储空间内的值，如果大于等于0，转Step4，否则转Step3；Step3：将存储空间的内容取它的负数后，放回到存储空间内；Step4：输出存储空间的值；Step5：结束。算法ALGORITHM2、传统流程图描述算法SymbolNameFunctionStart/EndAnovalrepresentsastartorendpoint.ArrowsAlineisaconnectorthatshowsrelationshipbetweentherepresentativeshapes.Input/outputProcessArectanglerepresentsainputoroutputorprocess.DecisionAdiamondindicatesadecision.⑴流程图的符号算法ALGORITHM⑵流程图的绘制规则规则1：使用标准的流程图符号。规则2：通常情况下，流程图的逻辑应该按照从页面顶端到页

面底部、从左到右的顺序进行流动。规则3：判断符号具有两个退出点，询问一个“是”或“不是”的问题。其他流程图符号只具有一个进入点和一个退出点。4.2算法贰ALGORITHM4.2.1算法概述4.2.2算法表示4.2.3流程图表示算法4.2.4算法应用算法ALGORITHM

算法的结构01顺序结构是最简单的，只要按照解决问题的顺序写出相应的语句就行，它的执行顺序是自上而下，依次执行。顺序结构02选择结构通过判断某些特定条件是否满足来决定下一步的执行流程，是非常重要的控制结构。选择结构03循环结构是指在需要反复执行某个功能而设置的一种程序结构。它由循环条件，判断继续执行某个功能还是退出循环。循环结构算法ALGORITHM顺序结构按照从上向下的顺序执行多个语句的处理方法。开始结束算法ALGORITHM例1：交换两个存储空间的内容。假设存储空间1的名称为a，存储空间2的名称为b，c为使用到的第三个存储空间的名称。请同学们绘制后拍照上传学习通。顺序结构活动6算法ALGORITHM选择结构根据给定的条件成立与否，而决定从不同的解决方案中选择某一个方案来执行。开始结束算法ALGORITHM例2：

交通监控设备需要根据车辆的速度判断车辆是否超速时，如果限制速度为80km/h，当车辆速度大于80km/h时，为“超速通过”，否则，为“正常通过”。监控结论判断的流程图该如何绘制呢？选择结构活动8算法ALGORITHM

1x>0y(x)=0x=0-1x<0例3：计算分段函数。算法ALGORITHM例4：在限速为50公里以下的道路，交通监控设备根据车辆行驶情况，给出车辆通行信息：①超过10%以内，不罚款，给予警告;②超过限定时速10%以上不到20%的，处50元罚款；③超过限定时速20%以上不到50%的，处100元罚款;④超过限定时速50%以上不到70%的，处300元罚款;⑤超过70%以上的，处500元罚款。要实现这个功能，又该怎么绘制流程图呢？算法ALGORITHM请大家看看以下流程图是否正确：活动9算法ALGORITHM编写多分支的条件时，如果只对一个量进行判断，可通过“数轴”确保各条件的完整性以及条件之间的互斥性。错误的划分正确的划分①②③④⑤⑥算法ALGORITHM例5：小明的姐姐在假日旅行社工作，旅行社为了争取更多的游客，给出优惠措施：团购5人以上（含5人），旅游费用8折；如果在淡季出行（3、6、9、11月），旅游费用5折；同时符合上述条件，旅行费用享折上折。根据顾客人数和出行月份计算折扣信息的流程图该如何绘制？活动10算法ALGORITHM团购5人以上（含5人），旅游费用8折；如果在淡季出行（3、6、9、11月），旅游费用5折；同时符合上述条件，旅行费用享折上折。ABd=0.5d=0.4算法ALGORITHM循环结构按照一定条件控制反复执行某段程序或某个语句的处理方法。开始结束算法ALGORITHM例6：计算1+2+3+……+100。1＋100＝2＋99＝3＋98＝…＝49＋52＝50＋51（1+100）×100÷2＝5050高斯的方法：数学家：高斯循环结构循环结构-三个要素算法ALGORITHM（1）设计循环体。需要被重复执行的语句放入循环体中。（2）设置循环条件。在这里控制循环条件的变量我们称之为循环变量。（3）初始化。对循环中要使用的变量赋初值。算法ALGORITHMi=1，s=s+1i=2，s=s+2i=3，s=s+3……i=100，s=s+100计算机的求解方法（累加算法）：s=0（用于存放累加和），i=1（表示从第一次开始）i<=100s=s+?s=0,i=1i<=100s=s+?是否循环结构-一个要求算法ALGORITHM循环变量必须在循环过程中发生变化。s=0,i=1i<=100s+=？是否i+=1循环结构-一个关系算法ALGORITHM找循环体中变化的量与循环变量的关系来确定这个变化的量。s=0,i=1i<=100s+=？是否i+=1循环结构-一个关系算法ALGORITHM找循环体中变化的量与循环变量的关系来确定这个变化的量。s=0,i=1i<=100s+=i是否i+=1循环结构构造算法ALGORITHM三个要素构造循环体；设置循环条件；设置变量初始化。一个要求

循环变量的值在循环过程中必须改变。一个关系

循环中变化的量与循环变量的关系。“精研计算”—素数问题功能要求：判断输入的数是否为素数。例如，17、9999999967是不是素数？分析问题：素数又称质数，是一个大于1的自然数，除了1和它自身外，不能被其他自然数整除。设计算法用流程图描述算法。设计上追求独具匠心、质量上追求精益求精、技艺上追求尽善尽美的“工匠精神”算法ALGORITHM”“精研计算”-素数问题算法流程图绘制开始输入自然数m结束i≤m-1是否i=2i=i+1i是m的因子否是i>m-1是m是素数否m不是素数算法一算法ALGORITHM”“精研计算”-素数问题算法流程图绘制开始输入自然数m结束i≤m/2是否i=2i=i+1i是m的因子否是i>m/2是m是素数否m不是素数算法二算法ALGORITHM”“精研计算”-素数问题算法流程图绘制开始输入自然数m结束

是否i=2i=i+1i是m的因子否是

是m是素数否m不是素数算法三算法ALGORITHM”“精研计算”-素数问题不同算法比较算法序号输入数据循环次数算法一171599999999679999999965算法二17799999999674999999983算法三173999999996799999算法ALGORITHM01020304正确性能正确地实现预定的功能,满足具体问题的需要。处理数据使用的算法是否得当,能不能得到预想的结果。高效性算法的时空性是该算法的时间性能和空间性能。主要是说算法在执行过程中的时间长短和空间占用多少问题。健壮性输入非法数据，算法也能适当地做出反应后进行处理，不会产生预料不到的运行结果。？如果算法能够处理异常数据，处理能力越强，健壮性越好。可读性易于阅读、理解和交流，便于调试、修改和扩充。如果通俗易懂，在系统调试和修改或者功能扩充的时候，使系统维护更为便捷。算法的评价算法ALGORITHM活动114.2算法贰ALGORITHM4.2.1算法概述4.2.2算法表示4.2.3流程图表示算法4.2.4算法应用算法ALGORITHMAlphaGoAlphaGoMasterAlphaGoZero算法ALGORITHM阿尔法狗到底有多厉害？第一个战胜围棋世界冠军的人工智能机器人2017年3月，阿尔法狗VS李世石

4:12018年初，阿尔法狗VS中日韩围棋高手连胜60局2018年5月，阿尔法狗VS柯洁3:0然后，阿尔法狗宣布“退役”，不再参加围棋比赛了，人类已无挑战性，它的征途是星辰和大海。算法ALGORITHM视野拓展——人工智能算法1、搜索算法：搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。

常见搜素算法：枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。

优化措施：在搜索前，根据条件降低搜索规模；根据问题的约束条件进行剪枝；利用搜索过程中的中间解，避免重复计算。算法ALGORITHM视野拓展——人工智能算法1、搜索算法：①暴力搜索算法“百钱百鸡”问题：百钱百鸡是我国古代数学家张丘建在《算经》一书中提出的数学问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？翻译成现代文是：公鸡5元一只，母鸡3元一只，小鸡1元三只，用100块钱买一百只鸡，问公鸡、母鸡、小鸡各有多少只？算法ALGORITHM视野拓展——人工智能算法②二分搜索算法二分搜索算法用来在已经有序的数组中找到关键字的位置。在说明词义的字典中，词的排列基本是有序的。电话本上，记录也都按照人名、地址或是电话号码排序。通过这样的算法，我们可以由人名，很快地在电话本中找到相应的电话以及地址。算法ALGORITHM视野拓展——人工智能算法③深度优先搜索算法（Depth-First-Search）是一种图形搜索算法。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。④广度优先搜索算法（Breadth-First-Search）是一种图形搜索算法。BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。算法ALGORITHM视野拓展——人工智能算法⑤蒙特卡罗树搜索（MonteCarloTreeSearch,MCTS）（随机数策略）假设所有落子方法分值都相等，设为1。两个棋手都扔骰子下棋，从361种落子方法中随机选择一个走法，棋盘状态变为S1。对方也扔了一个筛子走了一步，棋盘状态变成S2。然后这两个棋手一直扔骰子下棋，一路走到Sn，最后肯定也能分出一个胜负r，赢了就r记为1，输了则为0，假设这第一次r=1。这样就靠搜素下完了一盘围棋。算法ALGORITHM视野拓展——人工智能算法2、群智能算法：由简单个体组成的群落与环境以及个体之间的互动行为称为“群智能”，受动物群智能启发的算法称为“群智能算法（swarmintelligence,SI）”。群智能算法包括蚁群算法、粒子群优化算法和遗传算法。算法ALGORITHM视野拓展——人工智能算法蚁群算法工作原理单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。蚁群算法就是模拟蚂蚁寻找食物的过程，它能够求出从原点出发，经过若干个给定的需求点，最终返回原点的最短路径。这也就是著名的旅行商问题(TravelingSalemanProblem，TSP)。算法ALGORITHM视野拓展——人工智能算法例：蚁群算法工作原理算法ALGORITHM视野拓展——人工智能算法3、机器学习傍晚校区路面上沁出微雨后的湿润，和熙的细风吹来，抬头看看天边的晚霞，嗯，明天又是一个好天气。走到教育超市的水果摊，挑了个根蒂蜷缩、敲起来声音浊响的青绿西瓜，一边满心期待着皮薄肉厚瓜甜的爽落感，一边愉快地回寝室！计算机如何帮助人类来实现预测？机器学习正是这样的一门学科，人的“经验”对应计算机中的“数据”，让计算机来学习这些经验数据，生成一个算法模型，在面对新的情况中，计算机便能作出有效的判断，这便是机器学习。算法ALGORITHM视野拓展——人工智能算法3、机器学习算法ALGORITHM视野拓展——人工智能算法3、机器学习监督学习预测值为离散值的问题为：分类（classification）。预测值为连续值的问题为：回归（regression）。无监督学习聚类关联规则算法ALGORITHM视野拓展——人工智能算法例：决策树、随机森林算法、逻辑回归、SVM、朴素贝叶斯、K最近邻算法、K均值算法、Adaboost算法、马尔可夫……算法ALGORITHM视野拓展——人工智能算法机器学习的应用场景算法ALGORITHM视野拓展——人工智能算法3、机器学习参考书籍：1.李航：统计学习方法2.周志华:机器学习……网上学习：1.吴恩达机器学习(视频教程)(1)视频：/course/introduction.htm?courseId=1004570029(2)笔记：/ml2014/2.李宏毅：机器学习视频：/video/av10590361?from=search&seid=456509998694502607算法ALGORITHM视野拓展——人工智能算法4、神经网络与深度学习（NeuralNetworksandDeepLearning）深度学习的概念源于人工神经网络的研究。含多隐层的多层感知器就是一种深度学习结构。深度学习通过组合低层特征形成更加抽象的高层表示属性类别或特征，以发现数据的分布式特征表示。算法ALGORITHM视野拓展——人工智能算法4、神经网络与深度学习（NeuralNetworksandDeepLearning）同机器学习方法一样，深度机器学习方法也有监督学习与无监督学习之分．不同的学习框架下建立的学习模型很是不同．例如，卷积神经网络（Convolutionalneuralnetworks，简称CNNs）就是一种深度的监督学习下的机器学习模型，而深度置信网（DeepBeliefNets，简称DBNs）就是一种无监督学习下的机器学习模型。算法ALGORITHM视野拓展——人工智能算法4、神经网络与深度学习（NeuralNetworksandDeepLearning）历史上，科学家一直希望模拟人的大脑，造出可以思考的机器。人为什么能够思考？科学家发现，原因在于人体的神经网络。外部刺激通过神经末梢，转化为电信号，转导到神经细胞（又叫神经元）。无数神经元构成神经中枢。神经中枢综合各种信号，做出判断。人体根据神经中枢的指令，对外部刺激做出反应。算法ALGORITHM视野拓展——人工智能算法4、神经网络与深度学习（NeuralNetworksandDeepLearning）上个世纪六十年代，提出了最早的“人造神经元”模型，叫做“感知器”

。图中的圆圈就代表一个感知器。它接受多个输入（x1，x2，x3...），产生一个输出（output），好比神经末梢感受各种外部环境的变化，最后产生电信号。你去看动漫展览，天气：是否晴天？同伴：能否找到人一起去？价格：门票是否可承受？这就构成一个感知器。这三个因素就是外部输入，最后的决定就是感知器的输出。如果三个因素都是Yes（使用1表示），输出就是1（去参观）；如果都是No（使用0表示），输出就是0（不去参观）。（你还可以加上权重和阈值）算法ALGORITHM视野拓展——人工智能算法4、神经网络与深度学习（NeuralNetworksandDeepLearning）车牌自动识别:

车牌照片为输入，车牌号码是输出，照片的清晰度可以设置权重（w）。找到一种或多种图像比对算法，作为感知器。算法得到的结果是一个概率，比如75%的概率可以确定是数字1。这就需要设置一个阈值（b）（比如85%的可信度），低于这个阈值就无效。一组已经识别好的车牌照片，作为训练集数据，输入模型。不断调整各种参数，直至找到正确率最高的参数组合。以后拿到新照片，就可以直接给出结果了。算法ALGORITHM视野拓展——人工智能算法4、神经网络与深度学习（NeuralNetworksandDeepLearning）

算法ALGORITHM视野拓展——人工智能算法4、神经网络与深度学习（NeuralNetworksandDeepLearning）1.吴恩达：深度学习(视频教程)https:///smartSpec/detail/1001319001.htm2.李宏毅：深度学习(1)视频：/video/av9770302?from=search&seid=456509998694502607(2)李宏毅2017深度学习GAN课程/video/av18603573?from=search&seid=456509998694502607(3)李宏毅深度学习合辑/video/av19145699?from=search&seid=456509998694502607(4)深度学习理论DeepLearningTheory/video/av20961661?from=search&seid=47537723156761731683.博客：/hanbingtao/note/433855算法ALGORITHM视野拓展——人工智能算法人工智能、机器学习和深度学习的关系:深度学习是机器学习的子类；深度学习是基于传统的神经网络算法发展到多隐层的一种算法体现；机器学习是人工智能的一个子类。深度学习机器学习人工智能算法ALGORITHM视野拓展——人工智能算法5、专家系统（ExpertSystem）专家系统属于人工智能的一个发展分支，1965年，美国计算机科学家费根鲍姆和美国遗传学家莱德伯格等人合作，开发出世界上第一个专家系统程序DENDRAL，被认为是人工智能研究的一个历史性突破。费根鲍姆将专家系统定义为：一种智能的计算机程序，它运用知识和推理来解决只有专家才能解决的复杂问题。这里的知识和问题均属于同一特定领域。简单的说：专家系统就是能像人类专家一样解决困难、复杂的实际问题的计算机(软件)系统。算法ALGORITHM视野拓展——人工智能算法5、专家系统（ExpertSystem）人类专家与专家系统的主要区别：算法ALGORITHM视野拓展——人工智能算法5、专家系统（ExpertSystem）专家系统与传统的计算机程序的主要区别：算法ALGORITHM视野拓展——人工智能算法5、专家系统（ExpertSystem）用于某一特定领域内的专家系统，可以划分为以下几类：1、诊断型专家系统：根据对症状的观察分析，推导出产生症状的原因及排除故障方法。2、解释型专家系统：根据表层信息解释深层结构或内部情况，如地质结构分析等。3、预测型专家系统：根据现状预测未来情况，如气象预报、经济形势预测等。4、决策型专家系统：对可行方案进行综合评判并优选的一类专家系统。5、规划型专家系统：制定行动规划，如自动程序设计、军事计划的制定等。6、数学专家系统：用于自动求解某些数学问题的一类专家系统。7、监视型专家系统：对某类行为进行监测并在必要时候进行干预，如森林监视等。算法ALGORITHM视野拓展——人工智能算法6、自然语言处理（NaturalLanguageProcessing）自然语言处理（NLP）是计算机科学，人工智能，语言学关注计算机和人类（自然）语言之间的相互作用的领域。它研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法。自然语言处理是一门融语言学、计算机科学、数学于一体的科学。因此，这一领域的研究将涉及自然语言，即人们日常使用的语言，所以它与语言学的研究有着密切的联系，但又有重要的区别。算法ALGORITHM视野拓展——人工智能算法6、自然语言处理（NaturalLanguageProcessing）许多不同类的机器学习算法已应用于自然语言处理任务。这些算法的输入是一大组从输入数据生成的“特征”。一些最早使用的算法，如决策树，产生硬的if-then规则类似于手写的规则，是再普通的系统体系。然而，越来越多的研究集中于统计模型，这使得基于附加实数值的权重，每个输入要素柔软，概率的决策。此类模型具有能够表达许多不同的可能的答案，而不是只有一个相对的确定性，产生更可靠的结果时，这种模型被包括作为较大系统的一个组成部分的优点。算法ALGORITHM视野拓展——人工智能算法6、自然语言处理自然语言处理应用：机器翻译文本摘要问答系统对话系统语音识别阅读理解看图说话算法ALGORITHM视野拓展——人工智能算法6、自然语言处理学习参考书籍：算法ALGORITHM12306挑战的，是全球最难的“算法”/p/187332076/video/BV1og411c7Ne/第4章课后任务Assignment12306挑战的，是全球最难的“算法”一列火车，有很多个座位，可以到很多站，以北京到广州的一列火车G67为例，如何实现合理的抢票策略，才能保证这趟列车能够坐最多的人？（没有站票）请同学们通过资料搜索的方式，了解一下这个全球最难算法！二进制和位运算在12306算法中的应用算法ALGORITHM有算法之“根”，才能撑起产业“繁茂”！让信息赋能，担