Fork me on GitHub

发表于 | 分类于
字数统计: 1,426字 | 阅读时长 ≈ 7分钟

非线性方程求根

这一部分很大情况下以来与函数本身的单调性，
需要掌握一定的数学基础对函数概念要有清晰的认识。
可能也要有点求导和积分的知识。
还好我会 我会个毛线
:)

UVa-10341 Solve It!

传送门:UVa-10341
题目大意:
试解一个方程，使得

光凭这个方程我们毫无办法，因为对整个函数求导可以得到.

应用分部求导法则就可以了算是简单的求导

得到

眼花缭乱毫无办法,凭借导函数我们看不出任何增减性的变化。

注意到x的边界为0,1。

那么有以下函数在该区间是单减的（严格递减）

有以下的函数在该区间单增（严格递增）

再看一眼题目看到了sin(x),tan(x),tx^2前面的系数都是非正的！那么相当于整个函数为在[0,1]上的减函数。

于是根据介值定理，在某一区间上（这里是[0,1]） ，这个单调递减的函数若满足f(0) >= 0 >= f(1).

则在[0,1]上一定有且仅有一个解.

于是二分就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#include<cmath>
using namespace std;

const double eps = 1e-7;
double p,q,r,s,t,u;
double e = pow(double(1.0+1.0/10000),10000);
double calc(double x){return (p*exp(-x)+q*sin(x)+r*cos(x)+s*tan(x)+t*x*x+u);}
\\e^x 可以写成exp(-x)!
int main(int argc, char *argv[])
{
	while(scanf("%lf%lf%lf%lf%lf%lf",&p,&q,&r,&s,&t,&u) == 6)
	{
		double lim0 = calc(0),lim1 = calc(1);
		if (lim1 > 1e-9 || lim0 < -1e-9)
		{
			puts("No solution");
			continue;
		}
		double l = 0.0,r = 1.0,mid;
		while(r-l > eps)
		{
			mid = (l+r)/2;
			if (calc(mid) > 0.0)
			l = mid;
			else 
			r = mid;
		}
		printf("%.4lf\n",l);
	}
	return 0;
}

LA-5009 Error Curves

传送门:LA-5009

题目大意:给出n个抛物线（开口向上）或者直线，定义一个总函数f(x) = max{Si(x)}.

求这个总函数在[0,1000]上的最小值。

错误思路:
把每个函数在[0,1000]上的最小值求出来最后一遍取最小。
这样虽说看上去毫无问题，但是这个思路对于定义就是不正确的
f(x)的定义是max(si(x))而不是min,也就是说,我们在处理函数时不能以偏概全,必须在某一区间上硬性规定要取的是函数的最大值,换言之,我们的答案不能保证取到这个答案时f(x)能取到这个最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//wrong answer.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
const double eps = 1e-7;
int T,n;
struct Node{
	int a,b,c;
	double ans;
}f[maxn]; 
void calc(Node q)
{
	int x = q.a,y = q.b,z = q.c;
	if (x == 0)
	{
		if (y <= 0) 
		{
			q.ans = (double)(z);
			return ;
		}
		else 
		{
			q.ans = (double)(1000*y+z);
			return ;
		}
	}
	else
	{
		double u = (-y)/(2*x);
		if (u > eps  &&  1000 - u > eps)
			{
				q.ans = u*u*double(x)+u*double(y)+u*double(z);
				return ; 
			}
		if (u < -eps)
			{
				q.ans = double(z);
				return ;
			}
		if (u - 1000 > eps)
			{
				q.ans = 1000*1000*double(x)+double(y)*1000+double(z);
				return ;		
			}		
	}
}
int main(int argc ,char *argv[])
{
	scanf("%d",&T);
	while(T--)
	{
		double ass = 1e8;
		scanf("%d",&n);
		for (int i = 1; i <= n; i++)
			scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c),
		calc(f[i]),
		ass = min(ass,f[i].ans),
		printf("%.4lf\n",ass);
	} 
	return 0;
}

正解:
可以证明，对于两条抛物线或者直线，要么是单增单减，要么是开口向上的凹形图像。
再用一次数学归纳法,证明从n条线推导到n+1条曲线即可。
因为答案呈单峰，三分求解即可。
交了两次,第一次eps =1e-7莫名wa掉,第二次eps=1e-9就AC了
你敢信
Markdown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
const double eps = 1e-9;

int a[maxn],b[maxn],c[maxn],T,n;

inline void read(int &x)
{
	x=0;char ch=getchar();int f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}

double calc(double x)
{
	double ans = a[1]*x*x+b[1]*x+c[1];
	for (int i = 2; i <= n; i++)
		ans = max(ans,a[i]*x*x+b[i]*x+c[i]);
	return ans;
}

int main(int argc, char *argv[])
{
	read(T);
	while(T--)
	{
		read(n);
		for (int i = 1; i <= n; i++)
			read(a[i]),read(b[i]),read(c[i]);
		double l = 0.0,r = 1000.0;
		while(r - l > eps)
		{
			double m1,m2;
			m1 = l+(r-l)/3;
			m2 = r-(r-l)/3;
			if (calc(m2)-calc(m1) > eps)
			r = m2;
			else
			l = m1;
		}
		//printf("%.4lf %.4lf\n",l,r);
		printf("%.4lf\n",calc(l));
	}
	return 0;
}

积分导数技巧

虽然积分和导数算是我高数里比较擅长的东西。
但是还是要理一下的吧。

导数的定义

在可导函数上某一点的瞬时变化率.

基本初等函数导数即求导法则.

Mathjax打得我好累

积分的定义

难以解释.
积分求的是一个函数与x轴围成的面积大小。
只可意会不可言传。（逃

Markdown

Markdown

Markdown

这几个算有用的吧。

之前做过的一点习题

贴上来算了

Markdown

Markdown

积分和导数的综合运用

求曲函数的长度(LA-3485有用)

LA-3485 Bridge

传送门:LA-3485

题目大意:给出一个开口向上的抛物线的曲线长和左右区间，求出抛物线顶点的值（最小值）。

不行这题一定要另外写一篇Mark一下,太震撼了.

qwq

发表于 | 分类于
字数统计: 480字 | 阅读时长 ≈ 2分钟

题面

传送门:UVa-10791
题目大意:给出一个数N,要求出至少两个数以上的正整数,使得

阅读全文 »