分治法

╰半夏微凉° 2022-01-06 22:11 298阅读 0赞

**Problem1一元三次方程的解**

**题目描述**

有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。

**输入**

输入仅一行，有四个数，依次为a、b、c、d

**输出**

输出也只有一行，即三个根(从小到大输出)

**Problem2查找第k大元素**

**题目描述**

有N个数，请找出其中第k大的数(N<=10000)

**输入**

输入第一行为N、K，第二行有N个数

**输出**

输出第K大的数

**Problem3麦森数**

**题目描述**

形如2^P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2^P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。

任务：从文件中输入P（1000<P<3100000），计算2^P-1的位数和最后500位数字（用十进制高精度数表示）

**输入**

输入只包含一个整数P（1000<P<3100000）

**输出**

输出第一行是十进制高精度数2^P-1的位数。

第2-11行：十进制高精度数2^P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）

**Problem4逆序对个数**

**题目描述**

给出一个数列\{an\}，如果存在i<j，但是a\[i\]>a\[j\]那么我们称a\[i\]与a\[j\]是一对逆序对，现要求求出数列\{an\}中逆序对的个数

**输入**

输入第一行为整数N(N<=10000)，第二行有N个数，即为数列\{an\}

**输出**

输出仅一个数，即逆序对的个数

**Problem5寻找最近点对**

**题目描述**

给出平面内的N(N<=10000)个点，点两两都有一个距离，现要求出所有点对中距离最小的那一对

**输入**

输入第一行为N，后面有N行，每行两个数分别描述每个点的横纵坐标

**输出**

输出一个数，即最近点对的距离

**Problem6剔除多余括号**

**题目描述**

键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价。

**输入**

输入一行，即为表达式，长度小于250

**输出**

输出也一行，为剔出多余括号之后的表达式

**Problem7赛程安排**

**题目描述**

有n个编号为1到n 的运动员参加某项运动的单循环比赛，即每个运动员要和所有其他运动员进行一次比赛。试为这n个运动员安排一个比赛日程，使得每个运动员每天只进行一场比赛，且整个比赛在n-1天内结束。

**输入**

输入一行，即为运动员人数n(n<=10000)

**输出**

输出一个n阶方阵A\[1..N,0..N-1\](表示比赛日程)，当J＞0时，A\[I,J\]表示第I名运动员在第J天的比赛对手。

转载于:https://www.cnblogs.com/Crakme/archive/2011/03/09/1977920.html

发表评论取消回复

表情：

评论列表（有 0 条评论，298人围观）

还没有评论，来说两句吧...

相关阅读

相关棋盘覆盖--分治法

问题：在一个2^k×2^k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4^k种，因而有4^k种不同

柔情只为你懂/ 2024年02月18日 16:10/ 0 赞/ 61 阅读

相关分治法-归并排序

一、前言归并排序归并排序是建立在归并操作上的一种有效的排序算法，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。该算法是采用分

落日映苍穹つ/ 2022年11月16日 05:47/ 0 赞/ 210 阅读

相关大整数相乘(分治法）

分治法的原理讨论问题时，先来了解一下什么是分治法。 > 分治法的意思就是，分而治之，也就是把一个问题，拆分成几个小问题，最后再汇总解决的方法 ![watermark

「爱情、让人受尽委屈。」/ 2022年09月11日 14:13/ 0 赞/ 543 阅读

相关分治法

问题描述:假定一个已经排好顺序的一维数组,运用二分搜索算法,使得当前输入元素x不在数组中是，返回小于x的最大元素位置i和大于x的最小元素的位置j,当搜索元素在数组中，i 和j

怼烎@/ 2022年06月03日 05:52/ 0 赞/ 260 阅读

相关归并排序 java（分治法）

归并排序：归并排序是将给定的数列，尽可能地数量相同的两个数列。然后通过递归调用进行排序，排序完毕后的，将两个已经排好序的数列

以你之姓@/ 2022年05月31日 07:36/ 0 赞/ 262 阅读

相关【分治法】两分查找

问题描述：已知一个数组为升序，给定一个值，在此数组中查找是否存在，是则返回下标，否则提示“not found”. 解1：思维上最先想到的是顺序查找，即线性查找，对数组做遍

叁歲伎倆/ 2022年04月18日 02:16/ 0 赞/ 233 阅读

相关排序问题（蛮力法，分治法）

蛮力法：选择排序法：算法思想：在剩余序列中选出最小（或最大）的关键字，和剩余序列的第一个关键字交换位置，依次选择下去（每次扫描结束找出最小的一个元素依次放在前面的位

布满荆棘的人生/ 2022年04月16日 04:59/ 0 赞/ 238 阅读

相关分治法

Problem1一元三次方程的解题目描述有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三

╰半夏微凉°/ 2022年01月06日 22:11/ 0 赞/ 299 阅读

相关分治法简介

简介对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，[递归][L

r囧r小猫/ 2021年11月23日 06:30/ 0 赞/ 368 阅读

相关分治法——归并排序

归并排序归并排序是成功应用分治法的完美例子，归并排序是按照记录在序列中的位置对序列进行划分。【问题】应用归并排序方法对一个记录序列进行升序排序。归并排序（m

￡神魔★判官ぃ/ 2021年06月22日 15:36/ 0 赞/ 498 阅读