调整法、贪心
目录
一，调整法
在中学数学中，调整法应用非常广泛，在各个领域都能用上。
其数学本质，可以描述成，求一个多元函数的最值，通过分析最值点处的任意2个自由变量满足的条件，求出最值点。
调整法有2种调整方向，一种是把2个自由变量的值调整成差值最小，一种是把自由变量调整成差值最大。
也有人称之为局部调整法，磨光法。
二，调整法的应用
1，多元函数、不等式
如，a+b+c=1, 证明f(a,b,c)=a^2+b^2+c^2在a=b=c时取到最小值
证明：
假设a、b不相等，调整a和b的值，都调整为(1-c)/2，
根据基本不等式，新的函数值更小。
所以，当a=b=c时，函数有最小值
如：
证明：
等式左边略，对于等式右边，如果z>=1/2也好证，略
如果z<1/2，那么yz+zx+xy-2xyz = z(x+y)+(1-2z)xy，z值固定，x+y=1-z固定，当x=y时取到最小值，
所以，当x=y=z时有最小值7/27
2，几何
如，证明周长一定的三角形中，正三角形的面积最大
如，周长一定的封闭曲线围成的图形中，若存在最大面积，则一定是圆。
3，三角函数
如，证明在锐角三角形ABC中，sin A + sin B + sin C >2
证明：
题目相当于是证明，A，B，C都在[0, PI/2]的范围内，且和为PI，证明sin A + sin B + sin C >=2，仅当其中一个角为0时取到最小值。
因为sin函数在[0, PI/2]上是上凸函数，所以A和B相差越大，sin A + sin B越小
所以，sin A + sin B + sin C要想取到最小值，至多只有一个角的值不在区间端点
因为和为PI，所以仅当三个角分别为PI/2、PI/2、0时取到最小值
三，调整法和贪心
贪心是一种通过求解局部最优解得到全局最优解的算法。
从数学本质上来说，调整法和贪心本质是一样的。
从表现形式和计算过程上来说，调整法和贪心有一些区别。
就像数学归纳法和动态规划一样，数学归纳法一般是得到一个简洁的结论，动态规划一般是累积式的计算，最后得到一个计算结果，
调整法一般也是得到一个简洁的结论，贪心一般也是累积式的计算，最后得到一个庞大的结果，而不仅仅是一个数值。
四，整数拆分求积问题
1，把正整数n表示成若干个正整数的和，求积的最大值
例如：当n=4时，有4种拆分方法
4=4
4=1+3，1*3=3
4=2+2，2*2=4
4=1+1+2,1*1*2=2
所以积的最大值为4
名词定义：
n的最大分解：满足积最大的分解，比如4的最大分解为4=2*2，最大分解可能不唯一，例如4的最大分解有2种
求解的准备工作：
定理一：如果n>1，那么n的最大分解中，1是不可能出现的
证明：如果n>1且最大分解中出现了1，那么至少还会出现一个整数m，
用m+1替换m和1，那么积会变大，与最大分解的定义矛盾！
定理二：n的最大分解中不可能出现大于4的数
证明：如果最大分解中出现了大于4的数，假设为m
用m-2和2替换m，那么（m-2）*2=m+m-4>m，即积变大，与最大分解的定义矛盾！
定理三：n的所有最大分解中，一定有一种是没有出现4的
证明：假设出现了4，用2和2替换4，积不变
对所有的4都进行这样的变换，乘积仍然不变。
例如将15=4+4+4+3替换成15=2+2+2+2+2+2+3，乘积4*4*4*3=2*2*2*2*2*2*3=192
这样，一定有一种最大分解是没有出现4的
定理四：如果n>1，那么一定有一个最大分解，可以表示成n2个2和n3个3，即n=n2*2+n3*3，其中n2=0或1或2，n3是非负整数
证明：根据定理一、定理二、定理三，一定有一个最大分解，只由若干个2和若干个3组成（若干个可能是0个）
假设最大分解表示成n2个2和n3个3，如果n2>2，那么至少有3个2
用3,3替换2,2,2，乘积变大，与最大分解的定义矛盾！
所以n2=0或1或2，n3是非负整数
问题的求解：
如果n=1，不需要再分解
如果n>1，根据定理四，可以表示成n=n2*2+n3*3
那么n%3的值可以表示成n%3=（n2*2+n3*3）%3=（n2*2）%3
所以n2=（3-n%3）%3
所以，当n%3=0时，n2=0，当n%3=1时，n2=2，当n%3=2时，n2=1
所以，n的一个最大分解是n2个2和（n-n2*2）/3个3，其中n2=（3-n%3）%3
另解：
如果n=1，不需要再分解
如果n>1，n的一个最大分解是1个k和（n-k）/3个3，其中k=（n-2）%3+2
2，把正整数n表示成若干个不同的正整数的和，求积的最大值
把正整数n（n>4）表示成若干个不同的正整数的和，求积的最大值
名词定义：
n的最大分解：满足积最大的分解
假设n的最大分解中，最小的数是m，最大的数是M
求解的准备工作：
定理一：对于n的任何一个最大分解，从m到M，即m,m+1,m+2......M-1，M这些数中，最多只有1个数不在最大分解中。
证明：假设至少有2个数不在最大分解中，
那么一定可以找出2个数a,b，满足a<b且a和b都不在最大分解中且a-1和b+1都在最大分解中。
那么把a-1和b+1换成a和b之后，积变大，与最大分解的定义矛盾！
定理二：m=2或3
证明：首先m很明显不是1
如果m=4，那么M>4，可以分2种情况：
（1）5在最大分解中，把5换成2和3，积变大，与最大分解的定义矛盾！
（2）5不在最大分解中，那么根据定理一，6一定在最大分解中，
把4和6换成2和3和5，积变大，与最大分解的定义矛盾！
所以m=4是不可能的。
如果m>4，将m换成m-2和2，那么积变大，与最大分解的定义矛盾！
综上，m=2或者3
问题的求解：
2+3+4+...+k=(k+2)*(k-1)/2
求出满足(k+2)*(k-1)/2<n的最大k，设r=n-(k+2)*(k-1)/2，则0<=r<=k
如果r<k，只需要把从2到k这k-1个数中，最大的r个数都加1即可
如果r=k，所有的k-1个数都加1之后，新的最大的数还要加1
POJ - 1032 Parliament
题目：
Description
New convocation of The Fool Land's Parliament consists of N delegates. According to the present regulation delegates should be divided into disjoint groups of different sizes and every day each group has to send one delegate to the conciliatory committee. The composition of the conciliatory committee should be different each day. The Parliament works only while this can be accomplished.
You are to write a program that will determine how many delegates should contain each group in order for Parliament to work as long as possible.
Input
The input file contains a single integer N (5<=N<=1000 ).
Output
Write to the output file the sizes of groups that allow the Parliament to work for the maximal possible time. These sizes should be printed on a single line in ascending order and should be separated by spaces.
Sample Input
7
Sample Output
3 4
代码：
-
#include<iostream>
-
using namespace std;
-
-
int main()
-
{
-
int n, k = 1, s = 0, r;
-
cin >> n;
-
while (k++)
-
{
-
s += k;
-
if (s > n)
-
{
-
s -= k--;
-
break;
-
}
-
}
-
r = n - s;
-
if (r == k)
-
{
-
for (int i = 3; i <= k; i++)cout << i << " ";
-
cout << k + 2 << endl;
-
}
-
else
-
{
-
for (int i = 2; i <= k - r; i++)
-
{
-
cout << i;
-
if (i < k)cout << " ";
-
}
-
for (int i = k - r + 1; i <= k; i++)
-
{
-
cout << i + 1;
-
if (i < k)cout << " ";
-
}
-
cout << endl;
-
}
-
return 0;
-
}
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/115369650
- 点赞
- 收藏
- 关注作者
评论（0）