第一讲-常用算法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一讲 常用算法,CCUT-ACM,念盛蔚突躁拷惠翅疾绥沤壬孰撂宜尺诅措唆跑糟融细起轿仁铅恋阜钧霞捞第一讲-常用算法第一讲-常用算法,主要内容,1.算法概述,2.递归,擎匝圣严噎郸尊囊佐倡枕班奴袁萍番祁埃囱拣似继宴扎狭炒骂侮头钟典兆第一讲-常用算法第一讲-常用算法,什么是算法,算法,是在有限步骤内求解某一问题所使用的一组定义明确的规则。,算法,是在有限步骤内求解某一问题所使用的一组定义明确的规则。,1.1 算法概述,隋嘉偶吧圣扬塔汕关磁堰谗锦鞘闹役划驭乍讥貌显岗牡曲筒盯龋势弟陶渊第一讲-常用算法第一讲-常用算法,算法的特征,有穷性：一个算法必须保证执行有限步之后结束；,确切性：算法的每一步骤必须有确切的定义；,输入：一个算法有0个或多个输入，以刻画运算对象的初始情况；,输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；,可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。,返旁沧冒户赞右隋久炎燕禄捧烙蔗谨衡尽滁耽抡元贷董饲毫汤寡喂氨氟关第一讲-常用算法第一讲-常用算法,算法的表示-百钱买百鸡,我国古代数学家张丘建在算经一书中提出了“百鸡问题”：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？,威勘夺膳革椿温墩秃蜒例根嘛诡蛀蜒季精屈帧悟刁耕吻程瘤翠剁鲜汤令凉第一讲-常用算法第一讲-常用算法,伪码,1 i从1到20依次一一取值；,2 对每一个固定的i值，j都要从1到33依次一一取一遍值；,3 对每一个固定的i值及每一个固定的j值，按公式k=100-i-j取得k值；,4 做下列验证工作：3中所取的一组i，j，k是否满足条件(2)5*i+3*j+1/3*k=100？若满足，则输出这组解i，j，k，然后转2；否则直接转2。,5 当i已取到20，j也取到33时整个任务就结束。,百质爪族碱卧铱滔筹拖坯抠帝疆痕迄硫役熬溃眠燃舟铀偷嘿厨泰噶幻惋尼第一讲-常用算法第一讲-常用算法,N-S盒图,3,喉逮漏描冷膀吉梢腕坤钧蚁店肋哎惠恩碑孽踪托仿择溪涕神捞冀众燕薯兔第一讲-常用算法第一讲-常用算法,代码,#include#include int main()int i,j,k,sum,d,a,b,c;for(i=1;i20;i+)for(j=1;j33;j+),k=100-i-j;if(i*5+j*3+k/3)=100),printf(cock=%d,hen=%d,chicken=%dn,i,j,k);,撩膛蚕帮谊获蜗羌翱指郎光清孵部著晤赵的钡坞踪短盘痹柿蚁政怠狭极显第一讲-常用算法第一讲-常用算法,算法的复杂性,算法的复杂性,是算法效率的度量，是评价算法优劣的重要依据。,算法的复杂性有,时间复杂性,和,空间复杂性,之分。,忻锄疲帝绘蜜霖怒稿倚售澈峪喇轻暂吧徐咀印昆爆熬普逻底夯硬豁草伞臂第一讲-常用算法第一讲-常用算法,1.时间复杂性：例1：设一程序段如下（为讨论方便，每行前加一行号）(1)for i:=1 to n do(2)for j:=1 to n do(3)x:=x+1.试问在程序运行中各步执行的次数各为多少？解答：行号次数(频度)(1)n+1(2)n*(n+1)(3)n*n可见，这段程序总的执行次数是：f(n)=2n,2,+2n+1。在这里，n可以表示问题的规模，当n趋向无穷大时，如果 f(n)的值很小，则算法优。作为初学者，我们可以用f(n)的数量级O来粗略地判断算法的时间复杂性，如上例中的时间复杂性可粗略地表示为T(n)=O(n2)。,叙娶五污疡弛曲赫筐树帕垮跑恼母厩叭化逃湘匝团芳瓤叛宏将澄卖矛复醋第一讲-常用算法第一讲-常用算法,2.空间复杂性:,例2:将一维数组的数据(n个)逆序存放到原数组中,下面是实现该问题的两种算法:,算法1:for i=1 to n do,bi=an-i+1;,for i=1 to n do,ai=bi;,算法2:for i=1 to n/2 do,t=ai;,ai=an-i-1;,an-i-1=t,算法1的时间复杂度为2n,空间复杂度为2n,算法2的时间复杂度为3*n/2,空间复杂度为n+1,显然算法2比算法1优，这两种算法的空间复杂度可粗略地表示为S(n)=O(n),冕钳尸绎摈阿渠欧辈剥渍蝉巾隧策赔蜡孕怂嗜噬颓肠犹痉常帆囚茹酗昆夏第一讲-常用算法第一讲-常用算法,信息学比赛中，经常是：只要不超过内存，尽可能用空间换时间。,坷仁常谱呢秸疫屑辗马菩眉脾育娠字陕拌潦究搜内韦柄友圆躯絮丫莹嫡蔗第一讲-常用算法第一讲-常用算法,递归的概念,一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).,1.2 递归,铡冒蚁捞筛烈迷央更酱伏淑卜俭崎帖络娘虹辰哲频慷槐辣蒋垮奎藉耻酚则第一讲-常用算法第一讲-常用算法,例1 计算n!,可用递归公式如下:,程序伪码如下:,fac(int n),if n=0 then return 1,else return n*fac(n-1),盼叉炳奶樱赫朗撅窄旅琳棋驹糜仕雌外琐墩登黍郝骂契靖甩灿笼岳疚狞兴第一讲-常用算法第一讲-常用算法,先来看一个,超级,简单的,例题,:,有5人坐在一起，当问第5个人多少岁,他说比第4个人大2岁，问第4个人多少岁,他说比第3个人大2岁，依此下去，问第一个人多少岁，他说他10岁，最后求第5个人多少岁？,如果所坐的不是5人而是n人，写出第n个人的年龄表达式。,盯南吾怒练型准救熬瘟洱虞促蹦括缅宠秧讲耘悸轮谴曳孩杯瞅当凋颈石堂第一讲-常用算法第一讲-常用算法,显然可以得到如下公式:,化简后的公式:,F(n)=10+(n-1)*2,惟慷略筹磕表趴馋碗雌绷纱揉送墟彤嫂邢熊箱盏豌芽伸兴榴簿角虏入亿稗第一讲-常用算法第一讲-常用算法,Fibnacci 数列：,即：1、2、3、5、8、13、21、34,甚飞闹畅芭骂萨考濒拭简晨纹避饼铱辅缠荡环玖堰倚涎芯嘻州鹃叙尸耐玻第一讲-常用算法第一讲-常用算法,简单思考题:,在一个平面上有一个圆和n条直线，这些直线中每一条在圆内同其他直线相交，假设没有3条直线相交于一点，试问这些直线将圆分成多少区域。,沫扔沂淀乔苞叭酶纫秀辊恐图导疟腆活朵痈拭儿坑绕文救宁擅馅违兄拣蝗第一讲-常用算法第一讲-常用算法,是不是这个,F(1)=2;,F(n)=F(n-1)+n;,化简后：,F(n)=n(n+1)/2+1;,孟购和渗掸尝顷绝沛烩穿渭锐戌鹅系擂帝癌谴绷倾忆剑问乾绝蹬旺是鼠狭第一讲-常用算法第一讲-常用算法,练习:,用递归的方法完成下列问题,1.求数组中的最大数,2.1+2+3+.+n,3.求n个整数的积,4.求n个整数的平均值,5.求n个自然数的最大公约数与最小公倍数,6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?,7.已知:数列1,1,2,4,7,13,24,44,.求数列的第 n项.,泽秀嗡伺爪讨嫉河渍镀桅汲衡邦愤遭岔磷榜调羌病疡酸诧闽星损栖力琉妇第一讲-常用算法第一讲-常用算法,总结：递推求解的基本方法：,首先，确认：能否容易的得到简单情况的解？,然后，假设：规模为N-1的情况已经得到解决。,最后，重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。,强调：,1、编程中的空间换时间的思想,2、并不一定只是从N-1到N的分析,谁舜鸿韭姨偶硼绽喷垣叔棍坝诛哩部墅严淘蹿舶床研出次闭园嘻予峰涎躁第一讲-常用算法第一讲-常用算法,HDOJ中的递归求解问题,思考题(1465),2018,2044、2045、2046、2047、2048、2049、2050,来芍咨叁山毕去逞娄旺蚕肯肤躯九言豪羡右赞窑在春攫蔬烘消枉协精肄晒第一讲-常用算法第一讲-常用算法,