计算机科学与工程学院张玉磊.ppt

《计算机科学与工程学院张玉磊.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机科学与工程学院张玉磊算法设计大学计算机基础例如：需求-无纸化考试现状-当前存在多种无纸化考试系统方式：利用已有的程序或软件“过去时态”计算机解决问题的方式2012高教社杯全国大学生数学建模竞赛题目（B）设计太阳能小屋：在建筑物外表面铺设光伏电池，既可以供家庭使用，又可将剩余电量输入电网。但发电效率或发电量受诸多因素的影响。参考附件提供的数据，研究光伏电池在小屋外表面的优化铺设问题，使发电总量尽可能大，而单位发电量的费用尽可能小。计算机解决问题的方式例如：需求-对特定数据实现多种“特定”处理现状-当前不存在类似的程序或软件方式：设计满足用户需求的程序或软件

2、“将来时态”程序设计（或软件开发）4计算机学科中的一个论断尼克劳斯-沃思（瑞士计算机科学家）：Pascal语言之父1984年获得图灵奖，后回国任教。程序=算法+数据结构5本节内容定义特性描述方法算法设计方法特性6算法的定义Ⅰ算法:对特定问题求解方法和步骤的一种描述指令序列（程序）中文名称：算术+方法；源于公元前1世纪《周髀算经》，是我国最古老的天文学著作。介绍了勾股定理及其在测量上的应用。英文名称Algorithm[‘ælɡəriðəm]算法:Analgorithmisaseriesofmathematicalsteps,especiallyinacomput

3、erprogram,whichwillgiveyoutheanswertoaparticularkindofproblemorquestion.7算法的定义Ⅱ算法是否等于方法？8公认的第一个算法-欧几里德算法问题1：9和15的最大公约数？答案：3问题2：90和150的最大公约数？答案：30问题3：999和2555的最大公约数？答案：???问题4：正整数m和正整数n的最大公约数？答案：gcd(m,n)-greatestcommondivisor;辗转相除法n→m，r→n，直到r=0，最大公因子为“当前”的n。9算法“递推”回忆：判断两台计算机是否属于同一子网？①

4、输入IP1、SMask1和IP2、SMask2;②计算IP1+SMask1→x；③计算IP2+SMask2→y；④判断x是否等于y:若相等输出“是”，否则输出“否”。①输入m和n的值（m≥n）;②计算m除以n的余数并赋值给r；③判断r是否为0:若为0则输出n并结束；不为0继续执行；④n的值赋给m，r的值赋给n，跳转到②步；⑤输出n的值。10算法的特性及要求Ⅰ重要特性输入（>=0项）输出（>=1项）有穷性-有限步骤确定性-无歧义可行性-可分解、可实现11算法的特性及要求Ⅱ算法满足的要求：正确性-不要“南辕北辙”可读性-符合规范+注释健壮性-易于处理“边界值”高效

5、性-速度快、资源少12算法的描述工具Ⅰ自然语言-“大白话”程序代码-语言代码伪代码–自然语言+代码程序流程图-图形描述过程13算法的描述工具-程序流程图Ⅰ起止框输入输出框判断框处理框流程线语句序列A语句序列B选择结构（分支结构）顺序结构N语句序列B下一语句Y语句序列A条件N语句序列下一语句Y条件14算法的描述工具-程序流程图Ⅱ循环结构（当型）循环结构（直到型）N语句块下一语句Y条件Y语句块下一语句N条件15OPENPUSHCLOSENPUSHYIsitatoyNLEADN=N+1YPUSHIsitatoyN<=5YN“冰箱装大象”问题程序流程图16算法的设计方

6、法Ⅰ迭代法迭代法（递推法），利用问题本身所具有的一种递推关系（规律）求解问题的一种方法。重复执行一组指令，且每次通过变量的旧值推出新值。例如：①1累加到100：②斐波那契数列：自然语言描述：①变量s赋初值为0，i赋初值为1；②判读i是否超过100，若是执行⑤，否则执行③③将i加到变量s中，即s=s+i；④i自增1，即i=i+1，跳转到②⑤输出s的值。伪代码描述：①s=0，i=1；②dowhilei≤100{s=s+ii=i+1}③输出s的值。S=0,i=1Ns=s+i输出sYi<=100i=i+1如何计算2+5+8+11…+98如何计算2-5+8-11…+98

7、如何计算1×2×3×…×10i=2i=i+3i<10017算法的设计方法Ⅱ穷举法根据问题中的部分约束条件列举所有可能解的情况，通过一一验证,筛选符合要求的解。常用于解决“是否存在”或“有多少种可能”等类型的问题。尽可能优化。例如：找出所有“水仙花数”（三位整数，各位数字的立方和等于该数），如153=13+53+33。作业：“百钱百鸡”问题：“鸡翁一值钱五，鸡母一值钱三，鸡雉三值钱一，百钱买百鸡，各几何？”18“水仙花数”流程图i=100N计算百位数a、十位数b、个位数cYi<=999Ni=i+1Y输出条件成立“百钱百鸡”如何解决？19算法的设计方法Ⅲ递归法例如

8、：①k的阶乘:k!=k*(k-1)!(