基础算法入门(一)分治案例.ppt

CFLS NOIP CFLS CFLS NOIP CFLS NOIP 基础算法入门（一）分治、递归、排列组合 CFLS NOIP 分治算法 思考 考虑一个猜数字游戏，即取任何一个大于0，小于1024的自然数，提问方最多问10次“这个数比某数大吗？”，被问方只需回答“是”或者“不是”，提问方就可以猜出这个数字，聪明的你能明白其中的奥秘吗？ CFLS NOIP 　 所谓分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。 　　分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相似。找出各部分的解，然后把各部分的解组合成整个问题的解。 1、解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的： 　　解决子问题所需的工作总量（由子问题的个数、解决每个子问题的工作量 决定）合并所有子问题所需的工作量。 2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法。 这个技巧是很多高效算法的基础，如：排序算法（快速排序，归并排序），傅立叶交换（快速傅立叶交换）…… wps.cn/moban CFLS NOIP 3、分治的具体过程： 　　 {｛开始｝　　　 if ①问题不可分 ②返回问题解　　　　 else {　　　　　　 　　③从原问题中划出含一半运算对象的子问题1；　　　　　　 　　④递归调用分治法过程，求出解1；　　　　　　 　　⑤从原问题中划出含另一半运算对象的子问题2；　　　　　　 　　⑥递归调用分治法过程，求出解2；　　　　　　 　　⑦将解1、解2组合成整个问题的解；　　　　　　}　　 } //结束 【例1】快速排序(递归算法) void qsort(int l,int r) { int i,j,mid,p; i=l;j=r; mid=a[(l+r)/2]; //将当前序列在中间位置的数定义为分隔数 do { while (a[i]mid) {i++;} //在左半部分寻找比中间数大的数 while (a[j]mid) {j--;} //在右半部分寻找比中间数小的数 if (i=j) { //若找到一组与排序目标不一致的数对则交换它们 p=a[i];a[i]=a[j];a[j]=p; i++;j--; //继续找 } }while(i=j); //注意这里要有等号 if (lj) qsort(l,j); //若未到两个数的边界，则递归有哪些信誉好的足球投注网站左右区间 if (ir) qsort(i,r); } 大魔导师ZK曾经说过：“读书使人明智，读诗使人聪慧……”由此可见书籍的重要性是不言而喻的。而与图书天天打交道的图书管理员，更是夺天地之造化，吸日月之精华的神之职业。据史料记载，魔法世界从古至今诞生的众多不平凡的人物中，有不少人都曾经做过图书管理员，如道家创始人老子、微软公司创始人比尔盖茨、少林扫地僧等等。所以，以马虎自负出名的LPZ，在cw的社会实践活动中又怎么会放过图书管理员这个“天将降大任于斯人也”的锻炼呢。但想成为一个合格的图书管理员并不容易，他需要经常在一排（10000以内）已按编号大小排好序的图书中，快速地按照编号找到某本书所在的位置。 输入格式：第一行是N，表示有N本书，第二行是N个数，第三行是M表示要查找的书（数） 输出格式：一个数，如找到该书，输出所在位置，如不在，输出-1 样例输入数据： 3 2 4 6 4 输出：2 ★练习1、折半查找法 LPZ发现cw图书馆里收藏有许多上古时代的魔法书，这些上古时代的魔法书使用一种传说中的“神族文字”来书写，幸运的是，LPZ手边恰好有一本词典可以帮助他。 输入格式： 输入的词典内容最多包含有10000个词条，每一个词条包含一个英文单词，其次是一个空格和一个对应的神族文字，没有一个神族文字在词典里出现一次以上。词典词条全部输入完毕后是一个空行，之后是需要翻译的神族文字，每个词一行，每个单词是一个最多为10个小写字母的字符串。 输出格式： 输出翻译好的英文，每行一个字，若词典里查不到，输出“eh”。 输入样例：