《计算机科学与工程学院张玉磊.pptx》由会员分享，可在线阅读，更多相关《计算机科学与工程学院张玉磊.pptx（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、例如：需求例如：需求-无纸化考试无纸化考试 现状现状-当前存在多种无纸化考试系统当前存在多种无纸化考试系统方式：利用已有的程序或软件方式：利用已有的程序或软件“过去时态过去时态”计算机解决问题的方式计算机解决问题的方式 20122012高教社杯全国大学生数学建模竞赛题目（高教社杯全国大学生数学建模竞赛题目（B B）设计太阳能小屋：在建筑物外表面铺设设计太阳能小屋：在建筑物外表面铺设光伏电池光伏电池，既可以供家，既可以供家庭使用，又可将剩余电量输入电网。但发电效率或发电量受诸庭使用，又可将剩余电量输入电网。但发电效率或发电量受诸多因素的影响。多因素的影响。参考附件提供的数据，研究光伏电池在小屋外
2、参考附件提供的数据，研究光伏电池在小屋外表面的优化铺设问题表面的优化铺设问题，使发电总量尽可能大，而单位发电量的，使发电总量尽可能大，而单位发电量的费用尽可能小。费用尽可能小。计算机解决问题的方式计算机解决问题的方式 例如：需求例如：需求-对特定数据实现多种对特定数据实现多种“特定特定”处理处理 现状现状-当前不存在类似的程序或软件当前不存在类似的程序或软件方式：方式：设计满足用户需求的程序或软件设计满足用户需求的程序或软件“将来时态将来时态”程序设计（或软件开发）程序设计（或软件开发）3计算机学科中的一个论断计算机学科中的一个论断 尼克劳斯尼克劳斯-沃思沃思（瑞士计算机科学家）：（瑞士计算机
3、科学家）： Pascal语言之父语言之父 1984年获得图灵奖，年获得图灵奖，后回国任教后回国任教。程序程序= =算法算法+ +数据结构数据结构4本节内容本节内容 定义定义特性特性描述描述方法方法算法设计算法设计方法方法特性特性5算法的定义算法的定义 算法算法: :对特定问题求解方法和步骤的一种描述对特定问题求解方法和步骤的一种描述 指令序列（程序）指令序列（程序）中文名称：算术中文名称：算术+方法；源于公元前方法；源于公元前1世纪世纪周髀算经周髀算经，是我国最古老的天文学著作。介绍了是我国最古老的天文学著作。介绍了勾股定理勾股定理及其在测量及其在测量上的应用。上的应用。英文名称英文名称 Al
4、gorithmlrim算法算法: An algorithm is a series of mathematical steps, especially in a computer program, which will give you the answer to a particular kind of problem or question. 6算法的定义算法的定义 算法是否等于方法？算法是否等于方法？7公认的第一个算法公认的第一个算法-欧几里德算法欧几里德算法 3r1,q3;11215nm 312nm 问题问题1：9和和15的最大公约数？的最大公约数？答答 案：案：3问题问题2：90和和
5、150的最大公约数？的最大公约数？答答 案：案：30问题问题3：999和和2555的最大公约数？的最大公约数？答答 案：案：?问题问题4：正整数正整数m和正整数和正整数n的最大公约数？的最大公约数？答答 案：案： gcd(m,n) -greatest common divisor ;辗转相除法辗转相除法0r4,q0;4 nm，rn，直到，直到r=0，最大公因子为，最大公因子为“当前当前”的的n。8算法算法“递推递推” 回忆：判断两台计算机是否属于同一子网？回忆：判断两台计算机是否属于同一子网？ 输入输入IP1、SMask1和和IP2、SMask2; 计算计算IP1+ SMask1x； 计算计算
6、IP2+ SMask2y； 判断判断x是否等于是否等于y:若相等输出若相等输出“是是” ，否则输出，否则输出“否否” 。 输入输入m和和n的值（的值（mn）; 计算计算m除以除以n的余数并赋值给的余数并赋值给r； 判断判断r是否为是否为0:若为若为0则输出则输出n并结束；不为并结束；不为0继续执行；继续执行； n的值赋给的值赋给m，r的值赋给的值赋给n，跳转到步；，跳转到步； 输出输出n的值。的值。9算法的特性及要求算法的特性及要求 重要特性重要特性 输入（输入（=0=0项）项） 输出（输出（=1=1项）项） 有穷性有穷性 - - 有限步骤有限步骤 确定性确定性 - - 无歧义无歧义 可行性可
7、行性 - - 可分解、可实现可分解、可实现10算法的特性及要求算法的特性及要求 算法满足的要求：算法满足的要求： 正确性正确性 - - 不要不要“南辕北辙南辕北辙” 可读性可读性 - - 符合规范符合规范+ +注释注释 健壮性健壮性 - - 易于处理易于处理“边界值边界值” 高效性高效性 - - 速度快、资源少速度快、资源少11算法的描述工具算法的描述工具 自然语言自然语言 - - “大白话大白话”程序代码程序代码 - - 语言代码语言代码伪代码伪代码 自然语言自然语言+ +代码代码程序流程图程序流程图 - - 图形描述过程图形描述过程12算法的描述工具算法的描述工具-程序流程图程序流程图 起
8、止框起止框 输入输出框输入输出框 判断框判断框 处理框处理框 流程线流程线语句序列语句序列A A语句序列语句序列B B选择结构（分支结构）选择结构（分支结构）顺序结构顺序结构N N语句序列语句序列B B下一语句下一语句Y Y语句序列语句序列A A条件条件N N语句序列语句序列下一语句下一语句Y Y条件条件13算法的描述工具算法的描述工具-程序流程图程序流程图 循环结构（当型）循环结构（当型）循环结构（直到型）循环结构（直到型）N N语句块语句块下一语句下一语句Y Y条件条件Y Y语句块语句块下一语句下一语句N N条件条件14OPENOPENPUSHPUSHCLOSECLOSEN NPUSHPU
9、SHY YIs it a toyN NLEADLEADN=N+1 N=N+1 Y YPUSHPUSHIs it a toyN=5Y YN N“冰箱装大象冰箱装大象”问题程序流程图问题程序流程图 15算法的设计方法算法的设计方法 迭代法迭代法迭代法（递推法）迭代法（递推法），利用问题本身所具有的一种，利用问题本身所具有的一种递推关系递推关系（规律规律）求解问题的一种方法。重复执）求解问题的一种方法。重复执行一组指令，且每次通过变量的旧值推出新值。行一组指令，且每次通过变量的旧值推出新值。)(3nfff2n1nn )(100i1iss 例如：例如： 1 1累加到累加到100100： 斐波那契数列：
10、斐波那契数列：1f1f21 ,自然语言描述：自然语言描述：变量变量s s赋初值为赋初值为0 0，i i赋初值为赋初值为1 1；判读判读i i是否超过是否超过100100，若是执行，否则执行，若是执行，否则执行将将i i加到变量加到变量s s中，即中，即s=s+is=s+i；i i自增自增1 1，即，即i=i+1i=i+1，跳转到，跳转到输出输出s s的值。的值。伪代码描述：伪代码描述：s=0s=0，i=1i=1；do while ido while i100 s=s+i s=s+i i=i+1 i=i+1 输出输出s s的值。的值。S=0,i=1S=0,i=1N Ns=s+is=s+i输出输出
11、s sY Yi=100i=100i=i+1i=i+1如何计算如何计算2+5+8+112+5+8+11+98+98如何计算如何计算2-5+8-112-5+8-11+98+98如何计算如何计算1 12 23 31010i=2i=2i=i+3i=i+3i100i10016算法的设计方法算法的设计方法 穷举法穷举法根据问题中的部分约束条件根据问题中的部分约束条件列举所有可能解的情况列举所有可能解的情况，通，通过一一验证过一一验证, ,筛选符合要求的解。常用于解决筛选符合要求的解。常用于解决“是否存是否存在在”或或“有多少种可能有多少种可能”等类型的问题。尽可能等类型的问题。尽可能优化优化。例如：例如：
12、找出所有找出所有“水仙花数水仙花数”（三位整数，各位数（三位整数，各位数字字的立方和等于该数）的立方和等于该数），如，如153=1153=13 3+5+53 3+3+33 3。作业：作业：“百钱百鸡百钱百鸡”问题：问题：“鸡翁一值钱五，鸡母一鸡翁一值钱五，鸡母一值钱三，鸡雉三值钱一，百钱买百鸡，各几何？值钱三，鸡雉三值钱一，百钱买百鸡，各几何？”17“水仙花数水仙花数”流程图流程图 i=100i=100N N计算百位数计算百位数a a、十、十位数位数b b、个位数、个位数c cY Yi=999i=999N Ni=i+1 i=i+1 Y Y输出输出条件条件成立成立“百钱百鸡百钱百鸡”如何解决？如
13、何解决？18算法的设计方法算法的设计方法 递归法递归法例如：例如： k的阶乘的阶乘:k!=k*(k-1)! (0!=1) 斐波那契数列斐波那契数列:f(n)=f(n-1)+f(n-2) (n3) f(1)=1，f(2)=1作业作业:查查“汉诺塔汉诺塔”问题与宇宙寿命（问题与宇宙寿命（5845亿年）；亿年）； 查查“国际象棋棋盘国际象棋棋盘放麦子放麦子 ”。一个直接或间接的一个直接或间接的调用自身调用自身的算法称为递归算法。的算法称为递归算法。一个使用函数自身给出定义的函数称为递归函数。一个使用函数自身给出定义的函数称为递归函数。递归算法包括递归算法包括“递推递推”（难到易）和（难到易）和“回归回归”两部分。两部分。19作业作业 1、gcd(m,n)算法的程序流程图和伪代码算法的程序流程图和伪代码描述；描述；2、利用、利用Google等搜索引擎查找等搜索引擎查找“周髀算周髀算经经”和和“算经十书算经十书”的相关内容；查的相关内容；查“尼尼克劳斯克劳斯-沃思沃思”的生平及最新研究方向。的生平及最新研究方向。3、解决、解决“百钱百鸡百钱百鸡”问题。问题。20本节小结本节小结 定义定义特性特性描述描述方法方法算法设计算法设计方法方法特性特性