2021.1.31 数学构造
1.31
1.整数划分问题
最优分解方案 将一个整数n分成若干个互不相同的数的和，使得这些数的乘积最大。其中1<=n<=1000。
思路：
观察这几组数据，不难发现所有的分解方案的数的个数都等于ｎ可以分出的最多个数，其实我们并不难想到，要想使乘积最大，应尽量使分得的数多。
另一方面，我们在初中数学中就已经证明过当数（正数）的和相等时，数的差越小，数的积也就越大，因此我们可以在分的数的个数最多的情况下使数之间的差尽量小，这样得出来的方案必定是最优的。
2.整数分划
若干个正整数之和为n，其中：n<2000，试求它们乘积的最大值以及该最大值的位数k
思路
根据数学规律可知,若要使和固定的数的乘积最大，必须使这些数尽可能的多为3，于是可推得以下规律：
当N mod 3＝1 时，N可分解为一个4和若干个3的和；
当N mod 3＝2 时，N 可分解为一个2和若干个3的和；
当N mod 3＝0 时，N 直接分解为若干个3的和。
按照这一分解方法，所有因数的乘积必定最大。
注意：因N 的最大值可达2000，乘积将超过长整型数据范围，所以需用高精度运算。
3.整数分划的方案总数
把一个正整数N表示成如下表达式的一系列正整数的和，叫做整数N的一个分划。某个正整数N的不同表达式的个数称做整数N的分划数。编程计算指定正整数的分划数。 N＝n1＋n2＋…＋nk Nj>=1,j=1,2,……，k,k>=1 1<=n1<=n2<=…<=nk 输入正整数N（N＜＝100），输出N的分划数。
思路
在求解整数N的分划数时，设分解方案（表达式）中最大可以分解的整数因子nj的值最大不超过m，用F（N，m）记录N被划分成不超过m的整数的方案总数，通过数学分析，容易得到一个递归定义的递推关系式：
此处省略。。
n=read();
for(int i=1 ; i<=n ; i++)dp[0][i]=1;
for(int i=0 ; i<=n ; i++)dp[i][1]=1;
for(int i=1 ; i<=n ; i++){
for(int j=2 ; j<=n ; j++){
if(j>i)dp[i][j]=dp[i][i];
else dp[i][j]=dp[i-j][j]+dp[i][j-1];
}
}4.极值问题
已知m、n为整数，且满足下列两个条件：
① m、n∈1，2，…，K，（1≤K≤109）
② (n 2－mn－m2)2＝1编一程序，由键盘输入K，求一组满足上述两个条件的m、n，并且使m2＋n2的值最大。例如，若K＝1995，则m＝987，n＝1597，则m、n满足条件，且可使m ²＋n²的值最大。
思路
分析小数据会发现：m,n是Fibonacci数列的相邻两项。 因为： （n ²－mn－m²）² ＝1
故： （ m² + mn－ n ² ）² ＝1
又： m ²＋mn－n²＝(m＋n)²－mn－2n² ＝(m＋n)²－(m＋n)n－n²
故： （m²＋mn－n²）²＝ [ (m＋n)²－(m＋n)n－n² ]²
即： （n²－mn－m²）²＝[ (m＋n)²－(m＋n)n－n² ]²
ohhhhhhhhhhhhhhhhhhhhh
nice。 【分析】由上述数学变换式可以得出，
如果m和n为一组满足条件①和条件②的解， 设n’＝m＋n，m ’＝n那么n’，m ’也是一组满足条件①和条件②的一组解。
将所有满足条件①和条件②的m和n 按递增顺序排成一个Fibomacci数列 ｛1，1，2，3，5，8，……｝ 数列中小于k的最大两个相邻数即为试题所要求的一组m和n。
算法： 利用Fibomacci数列顺推m,n，求出在条件范围内的m,n最大值，此时m2＋n2的值最大。
//Fibomacci数列自己写4.Kathy函数
Tiger非常喜欢数学，所以他参加了学校组织的数学课外兴趣小组。在兴趣小组的学习当中，老师向Tiger介绍了Kathy函数，Kathy函数是这样定义的：
Tiger对Kathy函数产生了浓厚的兴趣，他通过研究发现有很多的数n都满足f(n)=n,对于一个给定的数m，他希望你求出所有的满足f(n)=n (n<=m)的自然数n的个数，其中m<=10的100次方。
思路
（被10的100次方震惊到的孩子）
换成二进制看看！！
一个数只要在二进制是回文数，那么f(x)=x,
手推几个一个: 5 =101 ,f(5)=5 , 101 是回文数
······
这就是规律，我也不知道为什么，（老师说的）
目前还未打出来。。。（keep uploading~!）