第七章 分治算法.pdfVIP

第七章 分治算法 【上机练习】 1、方程 f(x)的根(equation) 【问题描述】 求方程f(x)=2x x x +3 -4 =0 在[1，2] 内的根。 提示：2x可以表示成exp(x*log(2))的形式（需包含cmath库）。 【输入格式】 输入[1，2] 的区间值。 【输出格式】 输出方程 f(x)=0 的根，x 的值精确小数点 10 位。 【输入样例】 1 2 【输出样例】 1.5071105957 2、二分查找(binary) 【问题描述】 给出有 n 个元素的由小到大的序列，请你编程找出某元素第一次出现的位置。(n=10^6) 【输入格式】 第一行：一个整数，表示由小到大序列元素个数；下面 n 行，每行一个整数；最后一行 一个整数 x ，表示待查找的元素； 【输出格式】 如果 x 在序列中，则输出 x 第一次出现的位置，否则输出-1 。 【输入样例】 5 3 5 6 6 7 6 【输出样例】 3 3 、求逆序对(deseq) 【问题描述】 给定一个序列 a1,a2,…,an，如果存在 ij 并且 aiaj，那么我们称之为逆序对，求逆序对 的数目。 【输入格式】 第一行为 n,表示序列长度，接下来的 n 行，第 i+1 行表示序列中的第 i 个数。 【输出格式】 所有逆序对总数。 【输入样例】 4 3 2 3 2 【输出样例】 3 【数据范围】 5 5 N=10 ，A =10 。 i 4、麦森数(mason) 【问题描述】 形如 2P-1 的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个 素数，2P-1 不一定也是素数。到 1998 年底，人们已找到了 37 个麦森数。最大的一个是 P=3021377 ，它有 909526 位。麦森数有许多重要应用，它与完全数密切相关。 任务：从文件中输入P （1000P3100000），计算2P-1 的位数和最后 500 位数字（用十 进制高精度数表示）。 【输入格式】 文件中只包含一个整数 P （1000P3100000）。 【输出格式】 第一行：十进制高精度数 2P-1 的位数； 第 2-11 行：十进制高精度数 2P-1 的最后 500 位数字（每行输出 50 位，共输出 10 行， 不足 500 位时高位补 0 ）； 不必验证 2P-1 与P是否为素数。 【输入样例】 1279 【输出样例】 386 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000104079321946643990819252403273640855 38615262247266704805319112350403608059673360298012 23944173232418484242161395428100779138356624832346 49081399066056773207629241295093892203457731833496 61583550472959420547689811211693677147548478866962 50138443826029173234888531116082853841658502825560 46662248318909188018470682222031405210266984354887 32958028878050869736186900714720710555703168729087