本文主要是介绍分治算法3 题目练习，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

A.一元三次方程求解

内存限制：512 MiB 时间限制：1000 ms 标准输入输出
      题目类型：传统 评测方式：文本比较

• 题目描述

一本通 P 295 P295 P295，第 5 5 5题 有形如： a x 3 + b x 2 + c x + d = 0 ax^{3}+bx^{2}+cx+d=0 ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数（ a , b , c , d a,b,c,d a,b,c,d均为实数），并约定该方程存在三个不同实根（根的范围在 − 100 -100 −100至 100 100 100之间），且根与根之差的绝对值 ≤ 1 \leq 1 ≤1。 要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后 2 2 2位。

提示：记方程 f ( x ) = 0 f(x)=0 f(x)=0，若存在 2 2 2个数 x 1 x_1 x1​和 x 2 x_2 x2​，且 x 1 < x 2 x_1<x_2 x1​<x2​， f ( x 1 ) × f ( x 2 ) < 0 f(x1) \times f(x2)<0 f(x1)×f(x2)<0，则在 ( x 1 , x 2 ) (x1,x2) (x1,x2)之间一定有一个根。 输入： a , b , c , d a,b,c,d a,b,c,d 输出：三个实根（根与根之间留有空格）

• 输入格式

四个实数 a , b , c , d a,b,c,d a,b,c,d

• 输出格式

三个实根（根与根之间留有空格）

• 样例

样例输入

1 -5 -4 20

样例输出

-2.00 2.00 5.00

• 提交

Link

题解部分

1. 定义与输入

首先我们要定义 4 4 4个double类型的变量: a , b , c , d a,b,c,d a,b,c,d。

并将其输入。

double a, b, c, d;
scanf ("%d %d %d %d", &a, &b, &c, &d);

2.check函数

check函数就是把公式翻译成C++代码。

f ( x ) = a x 3 + b x 2 + c x + d f(x)=ax^{3}+bx^{2}+cx+d f(x)=ax3+bx2+cx+d

注:函数的返回类型为double

double check (double x) {
	return a * x * x * x + b * x * x + c * x + d;
}

3.二分内容(重点)

1. 首先，题目中已经写出了上界 100 100 100和下界 − 100 -100 −100，

就暴力枚举整数部分。(因为题目中已经说了每两个解的差超过 1 1 1，且二分查找每次只能查找一个数)

2. 如果解就是整数，就直接输出。

3. 若这两个数之间有解，就二分查找it。

条件: if (check (i) * check (i + 1) < 0)

4. 二分查找。

for (double i = ...(为了防止抄袭，这里不予显示); i < 100; i ++) {
	if (check (i) == 0) {
		printf ("%.2lf ", i);
		continue;
	}
	if (check (i) * check (i + 1) < 0) {
		double l = i, r = i + 1, mid;
		while (r - l > 0.001) {
			mid = (l + r) / 2;
			if (check (mid) * check (l) < 0) {
				r = mid;
			} else {
				l = mid;
			}
		}
		printf ("%.2lf ", mid);
	}
}

代码部分

注: 该AC代码仅供参考,请勿抄袭!

#include <cstdio>
#include <algorithm>
using namespace std;

double a, b, c, d;

double check (double x) {
	return a * x * x * x + b * x * x + c * x + d;
}

int main () {
	scanf ("%lf %lf %lf %lf", &a, &b, &c, &d);
	for (double i = ...(为了防止抄袭，这里不予显示); i < 100; i ++) {
		if (check (i) == 0) {
			printf ("%.2lf ", i);
			continue;
		}
		if (check (i) * check (i + 1) < 0) {
			double l = i, r = i + 1, mid;
			while (r - l > 0.001) {
				mid = (l + r) / 2;
				if (check (mid) * check (l) < 0) {
					r = mid;
				} else {
					l = mid;
				}
			}
			printf ("%.2lf ", mid);
		}
	}
	return 0;
}

B. 二分法求函数的零点

内存限制：128 MiB 时间限制：1000 ms 标准输入输出
     题目类型：传统 评测方式：文本比较

• 题目描述

有函数：
f ( x ) = x 5 − 15 x 4 + 85 x 3 − 225 x 2 + 274 x − 121 f(x)=x^{5}-15x^{4}+85x^{3}-225x^{2}+274x-121 f(x)=x5−15x4+85x3−225x2+274x−121
。已知 f ( 1.5 ) > 0 , f ( 2.4 ) < 0 f(1.5)>0,f(2.4)<0 f(1.5)>0,f(2.4)<0,且方程 f ( x ) = 0 f(x)=0 f(x)=0在区间 [ 1.5 , 2.4 ] [1.5,2.4] [1.5,2.4]有且只有一个根，请用二分法求出该根。

• 输入格式

无。

• 输出格式

该方程在区间 [ 1.5 , 2.4 ] [1.5,2.4] [1.5,2.4]中的根。要求四舍五入到小数点后 6 6 6位。

• 样例

样例输入

无

样例输出

不提供

• 提交

Link

题解部分

1. check函数

check函数就是把公式翻译成C++代码。

f ( x ) = x 5 − 15 x 4 + 85 x 3 − 225 x 2 + 274 x − 121 f(x)=x^{5}-15x^{4}+85x^{3}-225x^{2}+274x-121 f(x)=x5−15x4+85x3−225x2+274x−121

注:函数的返回类型为double

double check (...(为了防止抄袭，这里不予显示) x) {
	return x * x * x * x * x - 15 * x * x * x * x + 85 * x * x * x - 225 * x * x + 274 * x - 121;
}

2.二分内容(重点)

1. 题目中已给出区间 [ 1.5 , 2.4 ] [1.5,2.4] [1.5,2.4],即

double l = 1.5, r = 2.4;

2.二分查找it。

注: 注意精度:1e-6(保留6位小数)

此处不放代码，请读者独立完成。

代码部分

#include <cstdio>
#include <algorithm>
using namespace std;

double check (...(为了防止抄袭，这里不予显示) x) {
	return x * x * x * x * x - 15 * x * x * x * x + 85 * x * x * x - 225 * x * x + 274 * x - 121;
}

int main () {
	double l = 1.5, r = 2.4, mid;
	while (1) {
		mid = (l + r) / 2;
		if (check (mid) > -0.000001 && check (mid) < 0.000001) {
			printf ("%.6lf", mid);
			return 0;
		} else if (check (mid) > 0.000001) {
			l = ...(为了防止抄袭，这里不予显示);
		} else {
			r = mid;
		}
	}
	return 0;
}

C. 和为给定数

内存限制：128 MiB 时间限制：1000 ms 标准输入输出
题目类型：传统 评测方式：文本比较

• 题目描述

给出若干个整数，询问其中是否有一对数的和等于给定的数。

• 输入格式

共三行：

第一行是整数 n ( 0 < n ≤ 1000000 ) n(0 < n \leq 1000000) n(0<n≤1000000)，表示有 n n n个整数。

第二行是 n n n个整数。整数的范围是在 0 0 0到 1 0 8 10^{8} 108之间。

第三行是一个整数 m ( 0 ≤ m ≤ 2 30 ) m(0 \leq m \leq 2^{30}) m(0≤m≤230)，表示需要得到的和。

输出格式
若存在和为 m m m的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行No。

• 样例

样例输入

4
2 5 1 4
6

样例输出

1 5

• 数据范围与提示

新增 Hack 数据，暴力应该跑不过去了。

• 提交

Link

题解部分

1.定义与输入

首先定义两个变量 m , n m,n m,n以及一个整型数组 a a a

int m, n, a[...(为了防止抄袭，这里不予显示)];
scanf ("%d", &n);
for (int i = 1; i <= n; i ++) {
	scanf ("%d", &a[i]);
}
scanf ("%d", &m);

2.二分内容(重点部分)

1. 首先暴力枚举较小数，剪枝: 若该数 > m 2 > \frac {m} {2} >2m​

2. 二分查找较大数。

此处不放代码，请读者独立完成。

代码部分

#include <cstdio>
#include <algorithm>
using namespace std;

int n, m, a[1000005];

int main () {
	scanf ("%d", &n);
	for (int i = 1; i <= n; i ++) {
		scanf ("%d", &a[i]);
	}
	sort (a + 1, a + n + 1);
	scanf ("%d", &m);
	for (int i = 1; i <= n; i ++) {
		if (a[i] > m / 2) break;
		int l = i + 1, r = n, mid;
		while (l <= r) {
			...(为了防止抄袭，这里不予显示)
		}
	}
	printf ("No");
	return 0;
}

这篇关于分治算法3 题目练习的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！