作者 | 梁唐
出品 | 公众号:Coder梁(ID:Coder_LT)
大家好,我是梁唐。
最近在牛客网看到一道腾讯的算法笔试题很有意思,分享给大家。
题目来源牛客网,大家感兴趣想要亲手试一试的可以点击阅读原文跳转。
题目很短,只有一句话,求抛物线y^2 = 2Ax 与直线y=Bx+C 围成的封闭图形面积,如果图形不存在,则输出0.
第一行输入一个正整数T.表示测试数据组数.接下来每行输入三个整数A , B和 C.
1<=T<=1000
1<=A,B<=100-100<=C<=100
每组测试数据输出一个答案.在<1e-4范围内都视为正确输出.
1
1 1 -6
31.2481110540
这是一道典型的数学题,但是需要我们用程序去计算。
计算机编程比赛中的数学题难点都不在编码本身,这些题目考察的就是数学思维。如果我们在纸上可以推算出来那么就可以解出答案,否则,就做不出来。
我们可以观察一下要求面积的图形,它是一个抛物线和直线围成的,显然不是一个规则图形,没办法通过图形面积公式计算,只能使用积分。要求积分又必须知道边界,所以首先我们要求边界,也就是抛物线和直线的两个交点:
这两个点怎么求呢,这个很简单,我们初中就学过了,要求两条线的交点,就是求它们方程相等的值。也就是(Bx + C)^2 = 2Ax
时的值。
展开之后得到:
。
很明显,这是一个一元二次方程,我们可以直接使用求根公式x = \frac{-b \pm \sqrt{\Delta}}{2a} ,其中\Delta = B^2 \pm 4AC ,如果\Delta 小于0,那么方程没有解。
套用求根公式之后我们可以求出交点的坐标,就可以使用积分去计算面积了。怎么算呢?我们观察图形会发现它的x轴的值不是单调的,y轴的值是单调的。所以我们可以考虑横向计算,即将它看成是两个图形x轴差值的围成的面积。
也就是说我们要将y轴看成是自变量,x轴看成是因变量。那么首先,我们要用y来表示x,变形之后,可以得到:
做差之后得到\frac{y-C} B - \frac{y^2}{2A} ,我们对它求积分:
我们套入积分公式之后,即可得到答案。
AC代码如下:
# include <cstring>
# include <iostream>
# include <cmath>
# include <algorithm>
using namespace std;
double f(double A, double B, double C, double x) {
return x * x / (2*B) - C/B*x - x*x*x / (6 * A);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
double A, B, C;
cin >> A >> B >> C;
double b = 2 * (B * C - A);
double a = B * B;
double c = C * C;
// 计算delta,判断方程是否有解
double delta = b * b - 4 * a * c;
if (delta < 0) {
cout << 0 << endl;
continue;
}
double x1 = (-b - sqrt(delta)) / (2 * a);
double x2 = (-b + sqrt(delta)) / (2 * a);
double y1 = B * x1 + C;
double y2 = B * x2 + C;
// 套用积分公式,得到答案
cout << f(A, B, C, y2) - f(A, B, C, y1) << endl;
}
return 0;
}
到这里这道题就算是结束了,怎么样,小伙伴们做得还顺利吗,还是觉得当初学过的高数都还给老师了呢?