http://www.cnblogs.com/xiaoxian1369/archive/2011/09/12/2174212.html
分析与解:我们先考虑分成哪些数时乘积才能尽可能地大。
首先,分成的数中不能有1,这是显然的。
其次,分成的数中不能有大于4的数,否则可以将这个数再分拆成2与另外一个数的和,这两个数的乘积一定比原数大,例如7就比它分拆成的2和5的乘积小。
再次,因为4=2×2,故我们可以只考虑将数分拆成2和3。
注意到2+2+2=6,2×2×2=8;3+3=6,3×3=9,因此分成的数中若有三个2,则不如换成两个3,换句话说,分成的数中至多只能有两个2,其余都是3。根据上面的讨论,我们应该把14分拆成四个3与一个2之和,即14=3+3+3+3+2,这五数的积有最大值 3×3×3×3×2=162。
将上述结论推广为一般情形便是:
把自然数S(S>1)分拆为若干个自然数的和: S=a1+a2+…+an,则当a1,a2,…,an中至多有两个2,其余都是3时,其连乘积m=a1a2…an有最大值。
这一形式时,这些数的乘积最大,其积为 2×3×…×21×23×24×…×63。
https://www.jianshu.com/p/14211b33fbc4
https://www.cnblogs.com/radiumlrb/p/5797168.html
http://www.voidcn.com/article/p-mmrkvgjh-bcg.html
整数划分 --- 一个老生长谈的问题: 1) 练练组合数学能力.
2) 练练递归思想
3) 练练DP
总之是一道经典的不能再经典的题目:
这道好题求:
1. 将n划分成若干正整数之和的划分数。
2. 将n划分成k个正整数之和的划分数。
3. 将n划分成最大数不超过k的划分数。
4. 将n划分成若干奇正整数之和的划分数。
5. 将n划分成若干不同整数之和的划分数。
2) 练练递归思想
3) 练练DP
总之是一道经典的不能再经典的题目:
这道好题求:
1. 将n划分成若干正整数之和的划分数。
2. 将n划分成k个正整数之和的划分数。
3. 将n划分成最大数不超过k的划分数。
4. 将n划分成若干奇正整数之和的划分数。
5. 将n划分成若干不同整数之和的划分数。
1.将n划分成不大于m的划分法:
1).若是划分多个整数可以存在相同的:
dp[n][m]= dp[n][m-1]+ dp[n-m][m] dp[n][m]表示整数 n 的划分中,每个数不大于 m 的划分数。
则划分数可以分为两种情况:
a.划分中每个数都小于 m,相当于每个数不大于 m- 1, 故划分数为 dp[n][m-1].
b.划分中有一个数为 m. 那就在 n中减去 m ,剩下的就相当于把 n-m 进行划分, 故划分数为 dp[n-m][m];
则划分数可以分为两种情况:
a.划分中每个数都小于 m,相当于每个数不大于 m- 1, 故划分数为 dp[n][m-1].
b.划分中有一个数为 m. 那就在 n中减去 m ,剩下的就相当于把 n-m 进行划分, 故划分数为 dp[n-m][m];
2).若是划分多个不同的整数:
dp[n][m]= dp[n][m-1]+ dp[n-m][m-1] dp[n][m]表示整数 n 的划分中,每个数不大于 m 的划分数。
同样划分情况分为两种情况:
a.划分中每个数都小于m,相当于每个数不大于 m-1,划分数为 dp[n][m-1].
b.划分中有一个数为 m.在n中减去m,剩下相当对n-m进行划分,
同样划分情况分为两种情况:
a.划分中每个数都小于m,相当于每个数不大于 m-1,划分数为 dp[n][m-1].
b.划分中有一个数为 m.在n中减去m,剩下相当对n-m进行划分,
并且每一个数不大于m-1,故划分数为 dp[n-m][m-1]
2.将n划分成k个数的划分法:
dp[n][k]= dp[n-k][k]+ dp[n-1][k-1];
方法可以分为两类:
第一类: n 份中不包含 1 的分法,为保证每份都 >= 2,可以先拿出 k 个 1 分
到每一份,然后再把剩下的 n- k 分成 k 份即可,分法有: dp[n-k][k]
第二类: n 份中至少有一份为 1 的分法,可以先那出一个 1 作为单独的1份,剩
下的 n- 1 再分成 k- 1 份即可,分法有:dp[n-1][k-1]
第一类: n 份中不包含 1 的分法,为保证每份都 >= 2,可以先拿出 k 个 1 分
到每一份,然后再把剩下的 n- k 分成 k 份即可,分法有: dp[n-k][k]
第二类: n 份中至少有一份为 1 的分法,可以先那出一个 1 作为单独的1份,剩
下的 n- 1 再分成 k- 1 份即可,分法有:dp[n-1][k-1]
3.将n划分成若干奇数的划分法:(不懂)
g[i][j]:将i划分为j个偶数
f[i][j]:将i划分为j个奇数
g[i][j] = f[i - j][j];
f[i][j] = f[i - 1][j - 1] + g[i - j][j];
g[i][j] = f[i - j][j];
f[i][j] = f[i - 1][j - 1] + g[i - j][j];
int num[nmax][nmax]; //将i划分为不大于j的个数 int num1[nmax][nmax]; //将i划分为不大于j的不同的数 int num2[nmax][nmax]; //将i划分为j个数 int f[nmax][nmax]; //将i划分为j个奇数 int g[nmax][nmax]; //将i划分为j个偶数 void init() { int i, j; for (i = 0; i < nmax; i++) { num[i][0] = 0, num[0][i] = 0, num1[i][0] = 0, num1[0][i] = 0, num2[i][0] = 0, num2[0][i] = 0; } for (i = 1; i < nmax; i++) { for (j = 1; j < nmax; j++) { if (i < j) { num[i][j] = num[i][i]; num1[i][j] = num1[i][i]; num2[i][j] = 0; } else if (i == j) { num[i][j] = num[i][j - 1] + 1; num1[i][j] = num1[i][j - 1] + 1; num2[i][j] = 1; } else { num[i][j] = num[i][j - 1] + num[i - j][j]; num1[i][j] = num1[i][j - 1] + num1[i - j][j - 1]; num2[i][j] = num2[i - 1][j - 1] + num2[i - j][j]; } } } f[0][0] = 1, g[0][0] = 1; for (i = 1; i < nmax; i++) { for (j = 1; j <= i; j++) { g[i][j] = f[i - j][j]; f[i][j] = f[i - 1][j - 1] + g[i - j][j]; } }
将正整数划分成连续的正整数之和如15可以划分成4种连续整数相加的形式:
15
7 8
4 5 6
1 2 3 4 5
首先考虑一般的形式,设n为被划分的正整数,x为划分后最小的整数,如果n有一种划分,那么
结果就是x,如果有两种划分,就是x和x x + 1, 如果有m种划分,就是 x 、x x + 1 、 x x + 1 x + 2 、... 、x x + 1 x + 2 ... x + m - 1
将每一个结果相加得到一个公式(i * x + i * (i - 1) / 2) = n,i为当前划分后相加的正整数个数。
满足条件的划分就是使x为正整数的所有情况。
如上例,当i = 1时,即划分成一个正整数时,x = 15, 当i = 2时, x = 7。
当x = 3时,x = 4, 当x = 4时,4/9,不是正整数,因此,15不可能划分成4个正整数相加。
当x = 5时,x = 1。
这里还有一个问题,这个i的最大值是多少?不过有一点可以肯定,它一定比n小。我们可以做一个假设,
假设n可以拆成最小值为1的划分,如上例中的1 2 3 4 5。这是n的最大数目的划分。如果不满足这个假设,
那么 i 一定比这个划分中的正整数个数小。因此可以得到这样一个公式i * (i + 1) / 2 <= n,即当i满足
这个公式时n才可能被划分。
15
7 8
4 5 6
1 2 3 4 5
首先考虑一般的形式,设n为被划分的正整数,x为划分后最小的整数,如果n有一种划分,那么
结果就是x,如果有两种划分,就是x和x x + 1, 如果有m种划分,就是 x 、x x + 1 、 x x + 1 x + 2 、... 、x x + 1 x + 2 ... x + m - 1
将每一个结果相加得到一个公式(i * x + i * (i - 1) / 2) = n,i为当前划分后相加的正整数个数。
满足条件的划分就是使x为正整数的所有情况。
如上例,当i = 1时,即划分成一个正整数时,x = 15, 当i = 2时, x = 7。
当x = 3时,x = 4, 当x = 4时,4/9,不是正整数,因此,15不可能划分成4个正整数相加。
当x = 5时,x = 1。
这里还有一个问题,这个i的最大值是多少?不过有一点可以肯定,它一定比n小。我们可以做一个假设,
假设n可以拆成最小值为1的划分,如上例中的1 2 3 4 5。这是n的最大数目的划分。如果不满足这个假设,
那么 i 一定比这个划分中的正整数个数小。因此可以得到这样一个公式i * (i + 1) / 2 <= n,即当i满足
这个公式时n才可能被划分。
void split(int n) { int i, j, te, x, xlen; for (i = 1, xlen = 0; (te = i * (i - 1) / 2) < n; i++) { x = n - te; if (x % i == 0) { x /= i; printf("%d", x); for (j = 1; j < i; j++) { printf("%d ", x + j); } printf("\n"); xlen++; } } printf("%d\n", xlen); }
求划分因子乘积最大的一个划分及此乘积
问题简述:给定一个正整数n, 则在n所有的划分中, 求因子乘积最大的一个划分及此乘积。例如:8 = {8}, {7, 1}, {6, 2}, {5, 3}, {4, 4}, {3, 3, 2}, {2, 2, 2, 2} 等,那么在这些当中,3 * 3 * 2 的乘积最大,所以输出整个划分
和这个乘积 18。
算法分析:这是我在某个论坛上看到的问题,以及别人针对此问题的数学分析,现简单的整理如下:
(1)对于任意大于等于4的正整数m, 存在一个划分m = m1+m2, 使 m1*m2 >= m证: 令m1 = int(m/2), 则 m1 >= 2 , m2 = m-m1; 那么m2 > 2,并且 m2 >= m/2 >= m1; m1*m2 >= 2*m2 >= m; 证毕;
该证明简单的来说就是:对于一个大于等于4的正整数m,存在一个2块划分的因子,这两个因子的乘积总是不小于原数m本身。
(2)由(1)知此数最终可以分解为 2^r * 3^s。现证明 r <= 2;
证:若r > 2, 则至少有3个因子为2, 而2*2*2 < 3*3;
所以可以将3个为2的因子,换为两个因子3;积更大;证毕。
综合(1),(2),则有:任何大于4的因子都可以有更好的分解, 而4可以分解为2*2。
所以:此数应该分解为 2^k1 * 3^k2。而且可以证明 k1>=0 并且 k1 <= 2,因此:
A.当n = 3*r 时, 分解为 3^r
B.当n = 3*r+1时, 分解为 3^(r-1)*2*2
C.当n = 3*r+2时, 分解为 3^r*2
剩下编程处理,那就是太简单了,首先是处理 <= 4的特殊情况,再对>4的情况进行模3的3种情况的判断,最后一一输出。可见,数学在整数划分问题上有太强的功能。谁叫这个问题叫整数划分呢,不与数学密切才怪! ^_^。
问题简述:给定一个正整数n, 则在n所有的划分中, 求因子乘积最大的一个划分及此乘积。例如:8 = {8}, {7, 1}, {6, 2}, {5, 3}, {4, 4}, {3, 3, 2}, {2, 2, 2, 2} 等,那么在这些当中,3 * 3 * 2 的乘积最大,所以输出整个划分
和这个乘积 18。
算法分析:这是我在某个论坛上看到的问题,以及别人针对此问题的数学分析,现简单的整理如下:
(1)对于任意大于等于4的正整数m, 存在一个划分m = m1+m2, 使 m1*m2 >= m证: 令m1 = int(m/2), 则 m1 >= 2 , m2 = m-m1; 那么m2 > 2,并且 m2 >= m/2 >= m1; m1*m2 >= 2*m2 >= m; 证毕;
该证明简单的来说就是:对于一个大于等于4的正整数m,存在一个2块划分的因子,这两个因子的乘积总是不小于原数m本身。
(2)由(1)知此数最终可以分解为 2^r * 3^s。现证明 r <= 2;
证:若r > 2, 则至少有3个因子为2, 而2*2*2 < 3*3;
所以可以将3个为2的因子,换为两个因子3;积更大;证毕。
综合(1),(2),则有:任何大于4的因子都可以有更好的分解, 而4可以分解为2*2。
所以:此数应该分解为 2^k1 * 3^k2。而且可以证明 k1>=0 并且 k1 <= 2,因此:
A.当n = 3*r 时, 分解为 3^r
B.当n = 3*r+1时, 分解为 3^(r-1)*2*2
C.当n = 3*r+2时, 分解为 3^r*2
剩下编程处理,那就是太简单了,首先是处理 <= 4的特殊情况,再对>4的情况进行模3的3种情况的判断,最后一一输出。可见,数学在整数划分问题上有太强的功能。谁叫这个问题叫整数划分呢,不与数学密切才怪! ^_^。
小学六年级奥数---整数划分(有用结论)
例1:把14分拆成若干个自然数的和,再求出这些数的积,要使得到的积最大,应该把14如何分拆?这个最大的乘积是多少?
分析与解:我们先考虑分成哪些数时乘积才能尽可能地大。
首先,分成的数中不能有1,这是显然的。
其次,分成的数中不能有大于4的数,否则可以将这个数再分拆成2与另外一个数的和,这两个数的乘积一定比原数大,例如7就比它分拆成的2和5的乘积小。
再次,因为4=2×2,故我们可以只考虑将数分拆成2和3。
注意到2+2+2=6,2×2×2=8;3+3=6,3×3=9,因此分成的数中若有三个2,则不如换成两个3,换句话说,分成的数中至多只能有两个2,其余都是3。根据上面的讨论,我们应该把14分拆成四个3与一个2之和,即14=3+3+3+3+2,这五数的积有最大值 3×3×3×3×2=162。
将上述结论推广为一般情形便是:
把自然数S(S>1)分拆为若干个自然数的和: S=a1+a2+…+an,则当a1,a2,…,an中至多有两个2,其余都是3时,其连乘积m=a1a2…an有最大值。
例2:把1993分拆成若干个互不相等的自然数的和,且使这些自然数的乘积最大,该乘积是多少?
解:由于把1993分拆成若干个互不相等的自然数的和的分法只有有限种,因而一定存在一种分法,使得这些自然数的乘积最大。
若1作因数,则显然乘积不会最大。把1993分拆成若干个互不相等的自然数的和,因数个数越多,乘积越大。为了使因数个数尽可能地多,我们把1993分成2+3…+n直到和大于等于1993。
若和比1993大1,则因数个数至少减少1个,为了使乘积最大,应去掉最小的2,并将最后一个数(最大)加上1。
若和比1993大k(k≠1),则去掉等于k的那个数,便可使乘积最大。
所以n=63。因为2015-1993=22,所以应去掉22,把1993分成(2+3+…+21)+(23+24+…+63)
解:由于把1993分拆成若干个互不相等的自然数的和的分法只有有限种,因而一定存在一种分法,使得这些自然数的乘积最大。
若1作因数,则显然乘积不会最大。把1993分拆成若干个互不相等的自然数的和,因数个数越多,乘积越大。为了使因数个数尽可能地多,我们把1993分成2+3…+n直到和大于等于1993。
若和比1993大1,则因数个数至少减少1个,为了使乘积最大,应去掉最小的2,并将最后一个数(最大)加上1。
若和比1993大k(k≠1),则去掉等于k的那个数,便可使乘积最大。
所以n=63。因为2015-1993=22,所以应去掉22,把1993分成(2+3+…+21)+(23+24+…+63)
这一形式时,这些数的乘积最大,其积为 2×3×…×21×23×24×…×63。
【问题】将整数n表示为一系列正整数的和。
n = n1 + n2 + ...+ nk (n1 >= n2>=......>=nk>=1,k>=1)
并称之为n的划分。不同的划分个数称为正整数n的划分数,p(n)
建立如下递归关系:
在不同的划分中,将最大的加数n1不大于m的划分数计做q(n,m)
1.q(n,1) = 1,n >= 1;表示,最大加数小于等于1,就是,n1<=1.而n1>=1,因此n1 = 1,该种类型划分只有一种。
2,q(n,m) = q(n,n),m>=n;因此,m >=n > n1. 对于数字m和n他们划分的最大加数,都不会比n大,就说明划分数相同。
3.q(n,n) = 1 + q(n,n-1);n的划分由n1 = n,和n1 <= n-1构成。
4.q(n,m) = q(n,m-1) + q(n-m,m),n > m > 1;
n的最大划分数n1不大于m的划分数(n1 <= m)由,n1 = m和n1 <= m-1构成。
n1 = m,则n2 + n3 + ...+nk = n - m,在对n-m中找到最大为m的划分。表示为q(n-m,m);
n1 <= m - 1,表为q(n,m-1)
n = n1 + n2 + ...+ nk (n1 >= n2>=......>=nk>=1,k>=1)
并称之为n的划分。不同的划分个数称为正整数n的划分数,p(n)
建立如下递归关系:
在不同的划分中,将最大的加数n1不大于m的划分数计做q(n,m)
1.q(n,1) = 1,n >= 1;表示,最大加数小于等于1,就是,n1<=1.而n1>=1,因此n1 = 1,该种类型划分只有一种。
2,q(n,m) = q(n,n),m>=n;因此,m >=n > n1. 对于数字m和n他们划分的最大加数,都不会比n大,就说明划分数相同。
3.q(n,n) = 1 + q(n,n-1);n的划分由n1 = n,和n1 <= n-1构成。
4.q(n,m) = q(n,m-1) + q(n-m,m),n > m > 1;
n的最大划分数n1不大于m的划分数(n1 <= m)由,n1 = m和n1 <= m-1构成。
n1 = m,则n2 + n3 + ...+nk = n - m,在对n-m中找到最大为m的划分。表示为q(n-m,m);
n1 <= m - 1,表为q(n,m-1)
https://www.cnblogs.com/radiumlrb/p/5797168.html
http://www.voidcn.com/article/p-mmrkvgjh-bcg.html
但我在做51nod的时候发现数据给的范围很大(5*10^4),这种方法不仅内存存不下,而且还TLE
下面给出n个数拆成不同数的方案的O(nsqrt(n))算法
dp[i][j]代表i个数相加等于j
由于有不同的数最多不超过O(sqrt(n))算法个,则可以优化
由于有不同的数最多不超过O(sqrt(n))算法个,则可以优化
dp[i][j] = dp[i-1][j-i] + dp[i][j-i]
这个递推方程的转移含义是i-1个数每个数都加1,最后再添上一个1,就从dp[i-1][j-i]转到dp[i][j],还有就是i个数每个数都加1,就从dp[i][j-i]转到dp[i][j]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
int dp[600][51000];
int const mod = 1e9+7;
using namespace std;
int main()
{
int n;
while(scanf("%d",&n) != EOF){
dp[0][0] = 1;
for(int i =1; i <= 2*(int)sqrt(n); i++ )
{
for(int j = 0; j <= n; j++)
{
dp[i][j] = (dp[i-1][j-i] + dp[i][j-i])%mod;
}
}
int ans = 0;
for(int i =1; i <= 2*(int)sqrt(n); i++ )
{
ans += dp[i][n];
ans %= mod;
}
printf("%d\n",ans);
}
return 0;
}
那么当将n划分成若干正整数之和的划分数呢?
可以相同,那么上面那个方法就不行了
可以用5边形数来求
参考资料
https://en.wikipedia.org/wiki/Partition_(number_theory)
可以相同,那么上面那个方法就不行了
可以用5边形数来求
参考资料
https://en.wikipedia.org/wiki/Partition_(number_theory)
用一个公式就行
其中n-k*(3*k-1)/2>=0,n-k*(3*k+1)/2>=0;
注意两个条件要分开判断,有大于0的就加上相应的f,不是两个同时成立或者不成立
注意两个条件要分开判断,有大于0的就加上相应的f,不是两个同时成立或者不成立
这个公式的时间复杂度是O(n^1.5)
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
long long tar[100002];
const int MOD=1000000007;
void init()
{
memset(tar,0,sizeof(tar));
tar[0]=1;
for(int i=1;i<=50000;i++)
{
int nbit;
for(int j=1;;j++)
{
int element1,element2;
element1=i-j*(3*j-1)/2;
element2=i-j*(3*j+1)/2;
if(j&1)
nbit=1;
else if(j%2==0)
nbit=-1;
if(element2<0 && element1<0)
break;
if(element1>=0)
{
tar[i]=(tar[i]+nbit*tar[element1])%MOD;
}
if(element2>=0)
{
tar[i]=(tar[i]+nbit*tar[element2])%MOD;
}
}
tar[i]=(tar[i]+MOD)%MOD;
}
}
int main()
{
init();
int rat;
while(cin>>rat)
{
cout<<tar[rat]<<endl;
}
return 0;
}