基础算法入门(一)分治资料课件

,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level, NOIP,*,CFLS,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level, NOIP,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level, NOIP,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,基础算法入门（一）,分治、递归、排列组合,CFLS NOIP,基础算法入门（一）分治、递归、排列组合,分治算法,分治算法,思考,考虑一个猜数字游戏，即取任何一个大于,0,，小于,1024,的自然数，提问方最多问,10,次“这个数比某数大吗？”，被问方只需回答“是”或者“不是”，提问方就可以猜出这个数字，聪明的你能明白其中的奥秘吗？,CFLS NOIP,思考CFLS NOIP,所谓分治就是指的,分而治之,，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。,分治的基本思想是将一个规模为,n,的问题分解为,k,个规模较小的子问题，这些子问题互相独立且与原问题相似。找出各部分的解，然后把各部分的解组合成整个问题的解。,1,、解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的：解决子问题所需的工作总量（由子问题的个数、解决每个子问题的工作量 决定）合并所有子问题所需的工作量。,2,、分治法是把任意大小问题尽可能地,等分成两个子问题的递归算法,。,这个技巧是很多高效算法的基础，如：,排序算法（快速排序，归并排序），傅立叶交换（快速傅立叶交换）,所谓分治就是指的分而治之，即将较大规模的问题分解成, NOIP,3,、分治的具体过程：,开始,if,问题不可分 返回问题解,else,从原问题中划出含一半运算对象的子问题,1,；递归调用分治法过程，求出解,1,；从原问题中划出含另一半运算对象的子问题,2,；递归调用分治法过程，求出解,2,；将解,1,、解,2,组合成整个问题的解；,/,结束, NOIP3、分治的具体过程,【,例,1】,快速排序,(,递归算法,),void qsort(int l,int r),int i,j,mid,p;,i=l;j=r;,mid=a(l+r)/2;/,将当前序列在中间位置的数定义为分隔数,do,while(aimid)j-;/,在右半部分寻找比中间数小的数,if(i=j),/,若找到一组与排序目标不一致的数对则交换它们,p=ai;ai=aj;aj=p;,i+;j-;/,继续找,while(i=j);/,注意这里要有等号,if(lj)qsort(l,j);/,若未到两个数的边界，则递归搜索左右区间,if(ir)qsort(i,r);,【例1】快速排序(递归算法),大魔导师,ZK,曾经说过：“读书使人明智，读诗使人聪慧,”由此可见书籍的重要性是不言而喻的。而与图书天天打交道的图书管理员，更是夺天地之造化，吸日月之精华的神之职业。据史料记载，魔法世界从古至今诞生的众多不平凡的人物中，有不少人都曾经做过图书管理员，如道家创始人老子、微软公司创始人比尔盖茨、少林扫地僧等等。所以，以马虎自负出名的,LPZ,，在,cw,的社会实践活动中又怎么会放过图书管理员这个“天将降大任于斯人也”的锻炼呢。但想成为一个合格的图书管理员并不容易，他需要经常在一排（,10000,以内）已按编号大小排好序的图书中，快速地按照编号找到某本书所在的位置。,输入格式：第一行是,N,，表示有,N,本书，第二行是,N,个数，第三行是,M,表示要查找的书（数）,输出格式：一个数，如找到该书，输出所在位置，如不在，输出,-1,样例输入数据：,3,2 4 6,4,输出：,2,练习,1,、折半查找法,大魔导师ZK曾经说过：“读书使人明智，读诗使人,LPZ,发现,cw,图书馆里收藏有许多上古时代的魔法书，这些上古时代的魔法书使用一种传说中的“神族文字”来书写，幸运的是，,LPZ,手边恰好有一本词典可以帮助他。,输入格式：,输入的词典内容最多包含有,10000,个词条，每一个词条包含一个英文单词，其次是一个空格和一个对应的神族文字，没有一个神族文字在词典里出现一次以上。词典词条全部输入完毕后是一个空行，之后是需要翻译的神族文字，每个词一行，每个单词是一个最多为,10,个小写字母的字符串。,输出格式：,输出翻译好的英文，每行一个字，若词典里查不到，输出“,eh,”。,输入样例：输出样例：,CFLS NOIP,拓展练习,2,：神族文字,题目描述,:,神族文字,dictionary.cpp,dog ogday,cat atcay,pig igpay,froot ootfray,loops oopslay,atcay,ittenkay,oopslay,cat,eh,loops,LPZ发现cw图书馆里收藏有许多上古时代的魔法书，这些上古时,【,题目描述,】,魔法石的诱惑（,rob.cpp),LJZ,远远地看见,FUYU,狂奔而来，问道：“慌慌张张地跑什么？”,FUYU,大口大口地喘气：“我路过一家魔法石店，看到摆着那么多髙阶魔法石，我就跑进 去抢了一大袋。”,LJZ,怒道：“光天化日，朗朗乾坤,众目睽睽之下，你也敢抢？”,FUYU,：“我抢魔法石的时候，压根儿就没看见人，眼里只看见魔法石了。”,LJZ,：“,”,其实,FUYU,的贪婪很容易理解，因为高阶魔法石有一个特征：即它的重量进行阶乘运算后 末尾有几个,0,就拥有同等重量普通魔法石几倍的魔法力。例如,5!=5X4X3X2X1=120,。而,120,结尾包含,1,个零,.,这意味着该魔法石拥有同等重量的普通魔法石,1,倍的魔法力。你的任务是找到最小自然数,N,，使,N!,在十进制下包含,Q,个零。,【,输入格式,】,个数,Q(0=Q 0),n=n/5;,numofZero+=n;,return numofZero;,提示：CFLS NOIP参考代码：,CFLS NOIP,3,：魔法石的诱惑,(,二分法,),CFLS NOIP3：魔法石的诱惑(二分法),CFLS NOIP,3,：魔法石的诱惑,(fuyuhhh),CFLS NOIP3：魔法石的诱惑(fuyuhhh),CFLS NOIP,【,題目描述,】,近似整數（,Approximation.cpp),给定一个浮点教,A,和一个整教,L,求在范围,1,，,L,内的两个整教,n,和,d,使得,n/d,能近似等于,A,，且使误差丨,A n/d|,最小,.,【,输入格式,】,第一行为一个浮点教,A,第二行为一个整教,L,【,输出格式,】,两个整教,n,和,d,。,【,输入样例,】,3.14159265358979,10000,【,输出样例,】,355 113,拓展练习,4,CFLS NOIP【題目描述】近似整數（Approximat,【,题目描述,】,逃亡（,escape.cpp),FUYU,紧张地说：“老大，警察快追过來了，我们快逃跑吧,!”LJZ,傲然道：“在我的字典里没有逃跑,”,FUYU,内心崇敬地想：“老大实在是太有领袖范了,”,LJZ,接着说：“只有战略转移。”,FUYU,：“,现在,LJZ,和,FUYU,两人：要从,A,地出发尽快到达,B,地。出发时,A,地有一辆可带一人 的自动驾驶悬浮车。又知两人步行速度相同。问怎样利用小车才能使两人尽快同时到达,B,地。,【,输入格式,】,输入文件为,escape.in,，有三个,int,类型整数，分別表示,A,、,B,两地的距离，步行速度和 车速。,【,输出格式,】,输出文件为,escape.out,，有一个小数位数为,2,的浮点数,.,即最短时间。,【,输入样例,】,100 5 10,【,输出样例,】,14.00,CFLS NOIP,拓展与练习,5,【题目描述】逃亡（escape.cpp)CFLS NOIP,解题思路,CFLS NOIP,解题思路CFLS NOIP,【,题目描述,】,花费（,Expense.Cpp,）,FUYU,发愁地说：“这么高级的车怎么就断轴了？”,LJZ,一脸的郁闷：“是啊，当时车主还信誓旦旦地拍胸脯说这车经过魔法加强处理的。没办法，剩下的路程只好走路了。”,FUYU,摸摸钱袋，说：“好像钱也没多少了。”,已知,LJZ,和,FUYU,的逃亡天数为,N(1=N=100000),，每天需要花的钱已 经分配好，请把这些天分成,M,（,1=M=0,n=0,。,【,输出格式,】,输出文件为,power.out,，一个整数即结果，保证结果不超过整型范围。,【,输入样例,】,3 2,【,输出样例,】,9,CFLS NOIP,快速幂运算,8,【题目描述】快速幂运算（power.cpp)CFLS NOI,【,问题描述,】,输入,a,，,b,，,n,的值，求,ab mod n,的值。其中,a,，,b,，,n,均为整数范围内的数。,【,输入样例,】,2 10 9,【,输出样例,】,7,【,算法分析,】,本题主要的难点在于数据规模很大（,a,，,b,都可以是长整型数），对于,ab,显然不能死算，那样的话时间复杂度和编程复杂度都很大。,下面先介绍一个原理：,a*b%n=(a%n)*(b%n)%n,。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢？,显然对于任何一个自然数,P,，有,P=2*P/2+P%2,，如,19=2*19/2+19%2=2*9+1,，利用上述原理就可以把,B,的,19,次方除以,K,的余数转换为求,B,的,9,次方除以,K,的余数，即,B,19,=B,2*9+1,=B*B,9,*B,9,，再进一步分解下去就不难求得整个问题的解。,拓展练习,9,、取余运算（,Modulo.cpp,）,【问题描述】拓展练习9、取余运算（Modulo.cpp）,显然对于任何一个自然数,P,，有,P=2*P/2+P%2,，如,19=2*19/2+19%2=2*9+1,，利用上述原理就可以把,B,的,19,次方除以,K,的余数转换为求,B,的,9,次方除以,K,的余数，即,B,19,=B,2*9+1,=B*B,9,*B,9,，再进一步分解下去就不难求得整个问题的解。,显然对于任何一个自然数P，有P=2*P/2+,【,题目描述,】,循环比赛（,competition.cpp),在,LJZ,和,FUYU,亡命天涯的同时，,CW,一年一度的运动会正开得如火如荼。赛场上，业余评论员,ZHU,老师正在给观众作激情解说：“鬣狗群,咬住！咬住！鬣狗头子立功 了！不要给斑马任何的机会！伟大的鬣狗！伟大的鬣狗头子！它继承了猛兽光荣的历史和传统！豹子、老虎、雄狮在这一刻灵魂附体！”,呃，这个，我们不要管那些场上选手的绰号了，现在的问题是有某个项目的,n,个选手进行循环比赛，其中,n=2,m,要求每名选手要与其他,n-1,名选手都赛一次。每名选手每天比赛一次，循环赛共进行,