第2章-递归与分治策略-习题与实验.ppt

第2章递归与分治策略 2 2 1递归的概念 例2Fibonacci数列无穷数列1 1 2 3 5 8 13 21 34 55 称为Fibonacci数列 它可以递归地定义为 边界条件 递归方程 第n个Fibonacci数可递归地计算如下 intfibonacci intn if n 1 return1 returnfibonacci n 1 fibonacci n 2 3 2 1递归的概念 例5整数划分问题将正整数n表示成一系列正整数之和 n n1 n2 nk 其中n1 n2 nk 1 k 1 正整数n的这种表示称为正整数n的划分 求正整数n的不同划分个数 例如正整数6有如下11种不同的划分 6 5 1 4 2 4 1 1 3 3 3 2 1 3 1 1 1 2 2 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1 4 2 q n m q n n m n 最大加数n1实际上不能大于n 因此 q 1 m 1 1 q n 1 1 n 1 当最大加数n1不大于1时 任何正整数n只有一种划分形式 即 2 1递归的概念 例5整数划分问题前面的几个例子中 问题本身都具有比较明显的递归关系 因而容易用递归函数直接求解 在本例中 如果设p n 为正整数n的划分数 则难以找到递归关系 因此考虑增加一个自变量 将最大加数n1不大于m的划分个数记作q n m 可以建立q n m 的如下递归关系 5 4 q n m q n m 1 q n m m n m 1 正整数n的最大加数n1不大于m的划分由n1 m的划分和n1 m 1的划分组成 3 q n n 1 q n n 1 正整数n的划分由n1 n的划分和n1 n 1的划分组成 2 1递归的概念 例5整数划分问题前面的几个例子中 问题本身都具有比较明显的递归关系 因而容易用递归函数直接求解 在本例中 如果设p n 为正整数n的划分数 则难以找到递归关系 因此考虑增加一个自变量 将最大加数n1不大于m的划分个数记作q n m 可以建立q n m 的如下递归关系 6 2 1递归的概念 例5整数划分问题前面的几个例子中 问题本身都具有比较明显的递归关系 因而容易用递归函数直接求解 在本例中 如果设p n 为正整数n的划分数 则难以找到递归关系 因此考虑增加一个自变量 将最大加数n1不大于m的划分个数记作q n m 可以建立q n m 的如下递归关系 正整数n的划分数p n q n n 7 整数划分问题 8 比较x和a的中间元素a mid 若x a mid 则x在L中的位置就是mid 如果xa i 同理我们只要在a mid 的后面查找x即可 无论是在前面还是后面查找x 其方法都和在a中查找x一样 只不过是查找的规模缩小了 这就说明了此问题满足分治法的第二个和第三个适用条件 二分搜索技术 给定已按升序排好序的n个元素a 0 n 1 现要在这n个元素中找出一特定元素x 分析 9 二分搜索技术 给定已按升序排好序的n个元素a 0 n 1 现要在这n个元素中找出一特定元素x 算法复杂度分析 每执行一次算法的while循环 待搜索数组的大小减少一半 因此 在最坏情况下 while循环被执行了O logn 次 循环体内运算需要O 1 时间 因此整个算法在最坏情况下的计算时间复杂性为O logn 10 二分搜索技术 数据读取方法 11 循环赛日程表 N 2k个运动员进行网球循环赛 设计一个满足以下要求的比赛日程表 1 每个选手必须与其他n 1个选手各赛一次 2 每个选手一天只能赛一次 3 循环赛一共进行n 1天 12 循环赛日程表 按分治策略 将所有的选手分为两半 n个选手的比赛日程表就可以通过为n 2个选手设计的比赛日程表来决定 递归地用对选手进行分割 直到只剩下2个选手时 比赛日程表的制定就变得很简单 这时只要让这2个选手进行比赛就可以了 13 循环赛日程表 voidtable intk int a intn 1 for inti 1 i k i n 2 for inti 1 i n i a 1 i i intm 1 for ints 1 s k s n 2 for intt 1 t n t for inti m 1 i 2 m i for intj m 1 j 2 m j a i j t 1 m 2 a i m j t 1 m 2 m a i j t 1 m 2 m a i m j t 1 m 2 m 2 14 输油管道问题 某石油公司计划建造一条由东向西的主输油管道 该管道要穿过一个有n口油井的油田 从每口油井都要有一条输油管道沿最短路经 或南或北 与主管道相连 如果给定n口油井的位置 即它们的x坐标 东西向 和y坐标 南北向 应如何确定主管道的最优位置 即使各油井到主管道之间的输油管道长度总和最小的位置 编程任务 给定n口油井的位置 编程计算各油井到主管道之间的输油管道最小长度总和 15 数据输入 第1行是油井数n 1 n 10000 接下来n行是油井的位置 每行2个整数x和y 10000 x y 10000 结果输出 输出的第1行中的数是油井到主管道之间的输油管道最小长度总和 输入示例51222133 233输出示例6 输油管道问题 16 输油管道问题 include include defineN10001 17 输油管道问题O nlogn C sort a a n 需要 include 18 众数问题 给定含有n个元素的多重集合S 每个元素在S中出现的次数称为该元素的重数 多重集S中重数最大的元素称为众数 例如 S 1 2 2 2 3 5 多重集S的众数是2 其重数为3 编程任务 对于给定的由n个自然数组成的多重集S 编程计算S的众数及其重数 19 众数问题 数据输入 输入数据的第1行多重集S中元素个数n 接下来的n行中 每行有一个自然数 结果输出 输出的第1行给出众数 第2行是重数 输入示例6122235输出文件示例23 20 众数问题 intfreq 100000 全局变量 max是所有输入数据中的最大数 temp是读取的数据 freq对读取的数据累加 输入示例6122235输出文件示例23 21 邮局选址问题 在一个按照东西和南北方向划分成规整街区的城市里 n个居民点散乱地分布在不同的街区中 用x坐标表示东西向 用y坐标表示南北向 各居民点的位置可以由坐标 x y 表示 街区中任意2点 x1 y1 和 x2 y2 之间的距离可以用数值 x1 x2 y1 y2 度量 居民们希望在城市中选择建立邮局的最佳位置 使n个居民点到邮局的距离总和最小 编程任务 给定n个居民点的位置 编程计算n个居民点到邮局的距离总和的最小值 22 邮局选址问题 数据输入 第1行是居民点数n 1 n 10000 接下来n行是居民点的位置 每行2个整数x和y 10000 x y 10000 结果输出 第1行中的数是n个居民点到邮局的距离总和的最小值 输入示例51222133 233输出示例10 23 邮局选址问题 defineN1001 intn i j min intx N 0 y N 0 a N 0 b N 0 scanf d 24 邮局选址问题 j a 0 x的最小值及其坐标intx0 0 for i 1 ia i j a i x0 i j b 0 y的最小值及其坐标inty0 0 for i 1 ib i j b i y0 i min a x0 b y0 printf d n min return0 25 半数集问题 给定一个自然数n 由n开始可以依次产生半数集set n 中的数如下 1 n set n 2 在n的左边加上一个自然数 但该自然数不能超过最近添加的数的一半 3 按此规则进行处理 直到不能再添加自然数为止 例如 set 6 6 16 26 126 36 136 半数集set 6 中有6个元素 注意半数集是多重集 编程任务 对于给定的自然数n 1 n 1000 编程计算半数集set n 中的元素个数 26 半数集问题 12112 212 312 412 512 612121213121412 2412 124121512 2512 125121612 2612 12612 3612 13612P 12 20个 27 半数集问题 设set n 中的元素的个数为f n 则显然有 intf intn intans 1 if n 1 for inti 1 i n 2 i ans f i returnans 28 半数集问题 29 半数集问题 30 半数单集问题 给定一个自然数n 由n开始可以依次产生半数集set n 中的数如下 1 n set n 2 在n的左边加上一个自然数 但该自然数不能超过最近添加的数的一半 3 按此规则进行处理 直到不能再添加自然数为止 例如 set 6 6 16 26 126 36 136 半数集set 6 中有6个元素 注意该半数集不是多重集 集合中已经有的元素不再添加到集合中 编程任务 对于给定的自然数n 编程计算半数集set n 中的元素个数 31 半数单集问题 数据输入 输入数据只有1行 给出整数n 0 n 201 结果输出 输出只有1行 给出半数集set n 中的元素个数 输入示例6输出示例6 32 半数单集问题 示例 99199 299 399 499 599 699 799 899 999 1099 1199 4999999 1999 2999 3999 4999 注意条件0 n 201 即0 n 2 100 在计算时可能产生重复的元素是2位数 33 半数单集问题 注意条件0 n 201 即0 n 2 100 在计算时可能产生重复的元素是2位数 一个2位数x重复产生的条件是 在1位数y x 10的半数集中已产生x 因此x 10 y 2 即 2 x 10 x 10 x 10 X 10y 123456789101112 12 34 整数因子分解问题 大于1的正整数n可以分解为 n x1 x2 xm 例如 当n 12时 共有8种不同的分解式 12 12 12 6 2 12 4 3 12 3 4 12 3 2 2 12 2 6 12 2 3 2 12 2 2 3 编程任务 对于给定的正整数n 编程计算n共有多少种不同的分解式 35 整数因子分解问题 数据输入 第一行有1个正整数n 1 n 2000000000 结果输出 计算出的不同的分解式数 输入示例12输出文件示例8 36 整数因子分解问题 对n的每个因子递归