1、计算机科学与工程学院张玉磊,算法设计,大学计算机基础,计算机解决问题的方式,2012高教社杯全国大学生数学建模竞赛题目（B）设计太阳能小屋：在建筑物外表面铺设光伏电池，既可以供家庭使用，又可将剩余电量输入电网。但发电效率或发电量受诸多因素的影响。参考附件提供的数据，研究光伏电池在小屋外表面的优化铺设问题，使发电总量尽可能大，而单位发电量的费用尽可能小。,计算机解决问题的方式,4,计算机学科中的一个论断,尼克劳斯-沃思（瑞士计算机科学家）： Pascal语言之父 1984年获得图灵奖，后回国任教。,5,本节内容,6,算法的定义,算法:对特定问题求解方法和步骤的一种描述 指令序列（程序）,中文名称
2、：算术+方法；源于公元前1世纪周髀算经，是我国最古老的天文学著作。介绍了勾股定理及其在测量上的应用。,英文名称 Algorithmlrim算法: 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.,7,算法的定义,算法是否等于方法？,8,公认的第一个算法-欧几里德算法,问题1：9和15的最大公约数？答 案：3问题2：90和150的最大
3、公约数？答 案：30问题3：999和2555的最大公约数？答 案：?问题4：正整数m和正整数n的最大公约数？答 案： gcd(m,n) -greatest common divisor ;辗转相除法,nm，rn，直到r=0，最大公因子为“当前”的n。,9,算法“递推”,回忆：判断两台计算机是否属于同一子网？,10,算法的特性及要求,11,算法的特性及要求,12,算法的描述工具,自然语言 - “大白话”程序代码 - 语言代码伪代码 自然语言+代码程序流程图 - 图形描述过程,13,算法的描述工具-程序流程图,起止框 输入输出框 判断框 处理框 流程线,选择结构（分支结构）,顺序结构,14,算法的
4、描述工具-程序流程图,循环结构（当型）,循环结构（直到型）,15,“冰箱装大象”问题程序流程图,16,算法的设计方法,迭代法迭代法（递推法），利用问题本身所具有的一种递推关系（规律）求解问题的一种方法。重复执行一组指令，且每次通过变量的旧值推出新值。,伪代码描述：s=0，i=1；do while i100 s=s+i i=i+1 输出s的值。,如何计算2+5+8+11+98如何计算2-5+8-11+98如何计算12310,i=2,i=i+3,17,算法的设计方法,穷举法根据问题中的部分约束条件列举所有可能解的情况，通过一一验证,筛选符合要求的解。常用于解决“是否存在”或“有多少种可能”等类型的
5、问题。尽可能优化。,例如：找出所有“水仙花数”（三位整数，各位数字的立方和等于该数），如153=13+53+33。作业：“百钱百鸡”问题：“鸡翁一值钱五，鸡母一值钱三，鸡雉三值钱一，百钱买百鸡，各几何？”,18,“水仙花数”流程图,“百钱百鸡”如何解决？,19,算法的设计方法,递归法,例如： k的阶乘:k!=k*(k-1)! (0!=1) 斐波那契数列:f(n)=f(n-1)+f(n-2) (n3) f(1)=1，f(2)=1作业:查“汉诺塔”问题与宇宙寿命（5845亿年）； 查“国际象棋棋盘放麦子 ”。,一个直接或间接的调用自身的算法称为递归算法。一个使用函数自身给出定义的函数称为递归函数。递归算法包括“递推”（难到易）和“回归”两部分。,20,作业,1、gcd(m,n)算法的程序流程图和伪代码描述；2、利用Google等搜索引擎查找“周髀算经”和“算经十书”的相关内容；查“尼克劳斯-沃思”的生平及最新研究方向。3、解决“百钱百鸡”问题。,21,本节小结,
