基础算法入门(一)分治

1、CFLS基础算法入门（一）基础算法入门（一）分治、递归、排列组合分治、递归、排列组合 CFLS NOIP CFLS分治算法分治算法 v思考思考 考虑一个猜数字游戏，即取任何一个大于考虑一个猜数字游戏，即取任何一个大于0，小，小于于1024的自然数，提问方最多问的自然数，提问方最多问10次次“这个数这个数比某数大吗？比某数大吗？”，被问方只需回答，被问方只需回答“是是”或者或者“不是不是”，提问方就可以猜出这个数字，聪明的你，提问方就可以猜出这个数字，聪明的你能明白其中的奥秘吗？能明白其中的奥秘吗？CFLS NOIP 所谓分治就是指的分而治之分而治之，即将较大规模的问题分解成几个较小规模的问题，

2、通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相似。找出各部分的解，然后把各部分的解组合成整个问题的解。 1、解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的： 解决子问题所需的工作总量（由子问题的个数、解决每个子问题的工作量 决定）合并所有子问题所需的工作量。2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法。这个技巧是很多高效算法的基础，如：排序算法（快速排序，归并排序），傅立叶交换（快速傅排序算法（快速排序

3、，归并排序），傅立叶交换（快速傅立叶交换）立叶交换） CFLS NOIP3、分治的具体过程： 开始 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; /将当前序列在中间位置的数定义为分隔数将当前序列在中间位置的数定义为分隔数dowhile (aimid)

4、 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); 大魔导师大魔导师ZK曾经说过：曾经说过：“读书使人明智，读诗使人聪慧读书使人明智，读诗使人聪慧”由此由此可见书籍的重要性是不言而喻的。而与图书天天打交道

5、的图书管理员，更可见书籍的重要性是不言而喻的。而与图书天天打交道的图书管理员，更是夺天地之造化，吸日月之精华的神之职业。据史料记载，魔法世界从古是夺天地之造化，吸日月之精华的神之职业。据史料记载，魔法世界从古至今诞生的众多不平凡的人物中，有不少人都曾经做过图书管理员，如道至今诞生的众多不平凡的人物中，有不少人都曾经做过图书管理员，如道家创始人老子、微软公司创始人比尔盖茨、少林扫地僧等等。所以，以马家创始人老子、微软公司创始人比尔盖茨、少林扫地僧等等。所以，以马虎自负出名的虎自负出名的LPZ，在，在cw的社会实践活动中又怎么会放过图书管理员这的社会实践活动中又怎么会放过图书管理员这个个“天将降大

6、任于斯人也天将降大任于斯人也”的锻炼呢。但想成为一个合格的图书管理员并的锻炼呢。但想成为一个合格的图书管理员并不容易，他需要经常在一排（不容易，他需要经常在一排（10000以内）已按编号大小排好序的图书中，以内）已按编号大小排好序的图书中，快速地按照编号找到某本书所在的位置。快速地按照编号找到某本书所在的位置。 输入格式：第一行是输入格式：第一行是N，表示有，表示有N本书，第二行是本书，第二行是N个数，第三行是个数，第三行是M表示要查找的书（数）表示要查找的书（数） 输出格式：一个数，如找到该书，输出所在位置，如不在，输出输出格式：一个数，如找到该书，输出所在位置，如不在，输出-1样例输入数据

7、：样例输入数据：32 4 64输出：输出：2练习练习1、折半查找法、折半查找法LPZ发现cw图书馆里收藏有许多上古时代的魔法书，这些上古时代的魔法书使用一种传说中的“神族文字”来书写，幸运的是，LPZ手边恰好有一本词典可以帮助他。输入格式：输入的词典内容最多包含有10000个词条，每一个词条包含一个英文单词，其次是一个空格和一个对应的神族文字，没有一个神族文字在词典里出现一次以上。词典词条全部输入完毕后是一个空行，之后是需要翻译的神族文字，每个词一行，每个单词是一个最多为10个小写字母的字符串。输出格式：输出翻译好的英文，每行一个字，若词典里查不到，输出“eh”。输入样例： 输出样例：CFLS

8、 NOIP拓展练习拓展练习2：神族文字：神族文字题目描述题目描述: 神族文字神族文字dictionary.cppdog ogdaycat atcaypig igpayfroot ootfray loops oopslay atcayittenkayoopslaycatehloops【题目描述题目描述】魔法石的诱惑（魔法石的诱惑（rob.cpp)LJZ远远地看见远远地看见FUYU狂奔而来，问道：狂奔而来，问道：“慌慌张张地跑什么？慌慌张张地跑什么？”FUYU大口大口地喘气：大口大口地喘气：“我路过一家魔法石店，看到摆着那么多髙阶魔法石，我就跑进我路过一家魔法石店，看到摆着那么多髙阶魔法石，我就跑

9、进 去抢了一大袋。去抢了一大袋。”LJZ怒道：怒道：“光天化日，朗朗乾坤光天化日，朗朗乾坤,众目睽睽之下，你也敢抢？众目睽睽之下，你也敢抢？”FUYU：“我抢魔法石的时候，压根儿就没看见人，眼里只看见魔法石了。我抢魔法石的时候，压根儿就没看见人，眼里只看见魔法石了。”LJZ：“”其实其实FUYU的贪婪很容易理解，因为高阶魔法石有一个特征：即它的重量进行阶乘运算后的贪婪很容易理解，因为高阶魔法石有一个特征：即它的重量进行阶乘运算后 末尾有几个末尾有几个0,就拥有同等重量普通魔法石几倍的魔法力。例如就拥有同等重量普通魔法石几倍的魔法力。例如5! =5X4X3X2X1 = 120。而。而120结尾包

10、含结尾包含1个零个零.这意味着该魔法石拥有同等重量的普通魔法石这意味着该魔法石拥有同等重量的普通魔法石1倍的魔法力。倍的魔法力。 你你的任务是找到最小自然数的任务是找到最小自然数N，使，使N!在十进制下包含在十进制下包含Q个零。个零。【输入格式输入格式】个数个数 Q (0=Q 0) n = n/5; numofZero += n;return numofZero;CFLS NOIP3：魔法石的诱惑：魔法石的诱惑(二分法二分法)CFLS NOIP3：魔法石的诱惑：魔法石的诱惑(fuyuhhh)CFLS NOIP【題目描述題目描述】近似整數（近似整數（Approximation.cpp) 给定一个

11、浮点教给定一个浮点教A和一个整教和一个整教L,求在范围求在范围1，L内的两个整教内的两个整教n和和d,使得使得n/d 能近似等于能近似等于A，且使误差丨，且使误差丨A n/d|最小最小.【输入格式输入格式】第一行为一个浮点教第一行为一个浮点教A,第二行为一个整教第二行为一个整教L 【输出格式输出格式】两个整教两个整教n和和d。【输入样例输入样例】3. 1415926535897910000【输出样例输出样例】355 113拓展练习拓展练习4【题目描述】逃亡（escape.cpp)FUYU紧张地说：“老大，警察快追过來了，我们快逃跑吧!” LJZ傲然道：“在我的字典里没有逃跑”FUYU内心崇敬地

12、想：“老大实在是太有领袖范了”LJZ接着说：“只有战略转移。”FUYU：“现在LJZ和FUYU两人：要从A地出发尽快到达B地。出发时A地有一辆可带一人 的自动驾驶悬浮车。又知两人步行速度相同。问怎样利用小车才能使两人尽快同时到达 B地。【输入格式】输入文件为escape.in，有三个int类型整数，分別表示A、B两地的距离，步行速度和 车速。【输出格式】输出文件为escape.out，有一个小数位数为2的浮点数.即最短时间。【输入样例】100 5 10 【输出样例】14.00CFLS NOIP拓展与练习拓展与练习5解题思路解题思路CFLS NOIP【题目描述题目描述】花费（花费（Expense

13、. Cpp）FUYU发愁地说：发愁地说：“这么高级的车怎么就断轴了？这么高级的车怎么就断轴了？”LJZ一脸的郁闷：一脸的郁闷：“是啊，当时车主还信誓旦旦地拍胸脯说这车经过魔法加强处是啊，当时车主还信誓旦旦地拍胸脯说这车经过魔法加强处理的。没办法，剩下的路程只好走路了。理的。没办法，剩下的路程只好走路了。”FUYU摸摸钱袋，说：摸摸钱袋，说：“好像钱也没多少了。好像钱也没多少了。”已知已知LJZ和和FUYU的逃亡天数为的逃亡天数为N(1 = N =100000)，每天需要花的钱已，每天需要花的钱已 经分配好，请把这些天分成经分配好，请把这些天分成M（1 = M =0, n=0。 【输出格式输出格

14、式】输出文件为输出文件为power.out，一个整数即结果，保证结果不超过整型范围。，一个整数即结果，保证结果不超过整型范围。【输入样例输入样例】3 2【输出样例输出样例】9CFLS NOIP快速幂运算快速幂运算8【问题描述问题描述】 输入输入a，b，n的值，求的值，求ab mod n的值。其中的值。其中a，b，n均为整数范围内的数。均为整数范围内的数。【输入样例输入样例】 2 10 9 【输出样例输出样例】 7【算法分析算法分析】 本题主要的难点在于数据规模很大（本题主要的难点在于数据规模很大（a，b都可以是长整型数），对于都可以是长整型数），对于ab显然显然不能死算，那样的话时间复杂度和编

15、程复杂度都很大。不能死算，那样的话时间复杂度和编程复杂度都很大。 下面先介绍一个原理：下面先介绍一个原理：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的余数转换为求的余数转换为求

16、B的的9次方除以次方除以K的余数，即的余数，即B19=B2*9+1=B*B9*B9，再进一步分解下去就不难求得整个，再进一步分解下去就不难求得整个问题的解。问题的解。 拓展练习拓展练习9、取余运算（、取余运算（Modulo.cpp）v 显然对于任何一个自然数显然对于任何一个自然数P，有，有P=2 * P/2 + P%2，如，如19=2 * 19/2 + 19%2=2*9+1，利用上述原理就可以把，利用上述原理就可以把B的的19次方除次方除以以K的余数转换为求的余数转换为求B的的9次方除以次方除以K的余数，即的余数，即B19=B2*9+1=B*B9*B9，再进一步分解下去就不难求得整个问题的解。

17、，再进一步分解下去就不难求得整个问题的解。【题目描述题目描述】循环比赛（循环比赛（competition.cpp)在在LJZ和和FUYU亡命天涯的同时，亡命天涯的同时，CW一年一度的运动会正开得如火如荼。赛场上，业余评一年一度的运动会正开得如火如荼。赛场上，业余评论员论员ZHU老师正在给观众作激情解说：老师正在给观众作激情解说：“鬣狗群鬣狗群咬住！咬住！鬣狗头子立功咬住！咬住！鬣狗头子立功 了！不要了！不要给斑马任何的机会！伟大的鬣狗！伟大的鬣狗头子！它继承了猛兽光荣的历史和传统！豹子给斑马任何的机会！伟大的鬣狗！伟大的鬣狗头子！它继承了猛兽光荣的历史和传统！豹子、老虎、雄狮在这一刻灵魂附体！、老虎、雄狮在这一刻灵魂附体！”呃，这个，我们不要管那些场上选手的绰号了，现在的问题是有某个项目的呃，这个，我们不要管那些场上选手的绰号了，现在的问题是有某个项目的n个选手进行循个选手进行循环比赛，其中环比赛，其中n = 2m 要求每名选手要与其他要求每名选手要与其他n-1名选手都赛一次。每名选手每天比赛一次名选手都赛一次。每名选手每天比赛一次，循环赛共进行，循环赛共进行n-1天，要求每天没冇选手轮空。比赛时间表格如图所示（假定天，要求每天没冇选手轮空。比赛时间