It is possible to write five as a sum in exactly six different ways:
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
How many different ways can one hundred be written as a sum of at least two positive integers?
下面是解题代码:
public static void main(String[] args) {
System.out.println(f(100,99));
}
/**
* f(1,m)=1; f(n,1)=1; f(n,n)=1+f(n,n-1); f(n,m)=f(n-m,m)+f(n,m-1);
*
* @return
*/
public static int f(int n, int m) {
if (n == 1 || m == 1) {
return 1;
}
if (n < m) {
return f(n, n);
} else if (n == m) {
return 1 + f(n, n - 1);
} else {
return f(n - m, m) + f(n, m - 1);
}
}
整数分拆问题的递归方法思想:
所谓整数划分,是指把一个正整数n写成如下形式:n=m1+m2+...+mi; (其中mi为正整数,并且1 <= mi <= n),则{m1,m2,...,mi}为n的一个划分。
如果{m1,m2,...,mi}中的最大值不超过m,即max(m1,m2,...,mi)<=m,则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);
例如但n=4时,他有5个划分,{4},{3,1},{2,2},{2,1,1},{1,1,1,1};
注意4=1+3 和 4=3+1被认为是同一个划分。
该问题是求出n的所有划分个数,即f(n, n)。下面我们考虑求f(n,m)的方法;
根据n和m的关系,考虑以下几种情况:
(1)当n=1时,不论m的值为多少(m>0),只有一种划分即{1};
(2) 当m=1时,不论n的值为多少,只有一种划分即n个1,{1,1,1,...,1};
(3) 当n=m时,根据划分中是否包含n,可以分为两种情况:
(a). 划分中包含n的情况,只有一个即{n};
(b). 划分中不包含n的情况,这时划分中最大的数字也一定比n小,即n的所有(n-1)划分。
因此 f(n,n) =1 + f(n,n-1);
(4) 当n<m时,由于划分中不可能出现负数,因此就相当于f(n,n);
(5) 但n>m时,根据划分中是否包含最大值m,可以分为两种情况:
(a). 划分中包含m的情况,即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m,可能再次出现m,因此是(n-m)的m划分,因此这种划分
个数为f(n-m, m);
(b). 划分中不包含m的情况,则划分中所有值都比m小,即n的(m-1)划分,个数为f(n,m-1);
因此 f(n, m) = f(n-m, m)+f(n,m-1);
综合以上情况,我们可以看出,上面的结论具有递归定义特征,其中(1)和(2)属于回归条件,(3)和(4)属于特殊情况,将会转换为情况(5)。而情况(5)为通用情况,属于递推的方法,其本质主要是通过减小m以达到回归条件,从而解决问题。其递推表达式如下:
f(n, m)=
1; (n=1 or m=1)
f(n, n); (n<m)
1+ f(n, m-1); (n=m)
f(n-m,m)+f(n,m-1); (n>m)
参考:http://www.cnblogs.com/hoodlum1980/archive/2008/10/11/1308493.html
分享到:
相关推荐
基于openEuler20.03TLS版本编译openGauss源码时需要的软件包: 1. openeuler-lsb-5.0-1.oe2203.src.rpm 2. git-lfs-linux-arm64-v3.3.0.tar.gz 3. flex-2.5.39.tar.bz2
ProjectEuler题1-16题代码,直接引入Eclipse就可以用
GaussDB_100_1.0.1-DATABASE-EULER20SP8-64bit
计算流体力学基础中的二维欧拉方程求解程序
solution to problem 5
Project-Euler-Problem-8
华为欧拉系统 EulerOS-V2.0SP5-x86_64-dvd文件分割成 五个 压缩包,必须集齐 五个 文件后才能一起解压一起使用: EulerOS-V2.0SP5-x86_64-dvd.part5.rar ... EulerOS-V2.0SP5-x86_64-dvd.part4.rar ...
华为欧拉系统 EulerOS-V2.0SP5-x86_64-dvd文件分割成 五个 压缩包,必须集齐 五个 文件后才能一起解压一起使用: EulerOS-V2.0SP5-x86_64-dvd.part5.rar ... EulerOS-V2.0SP5-x86_64-dvd.part4.rar ...
二维欧拉
项目-euler-问题-下载器 将所有 projecteuler.net 问题下载到您的本地存储
RKDG-Euler-third-order-2d-accurary.f90
1.openEuler操作系统入门 2.命令行操作基础 3.使用VIM编辑器 4.用户和权限管理 5.安装软件并管理服务 6.管理文件系统及存储 7.日常系统管理 8.使用shell脚本 9.openEuler管理员综合实践——文件共享服务器管理
euler-search-components-源码.rar
Galerkin method,a numerical approximate method based on,commonly used in ordinary differential equation.
openEuler-22.03-LTS-SP2-x86_64-dvd.iso 适用于x86_64平台服务器,文件使用WinRAR分割成 4 个压缩包,必须一起下载使用: part1:https://download.csdn.net/download/weixin_43800734/88220955 part2:...
Arduino-PyTeapot-Quaternion-Euler-cube-rotation.zip,从四元数或欧拉角数据可视化旋转立方体pyteapot四元数欧拉立方体旋转,Arduino是一家开源软硬件公司和制造商社区。Arduino始于21世纪初,深受电子制造商的欢迎...
robogirl06-Euler_Solutions-archive-refs-heads-master.zip
目录openEuler 系统架构openEuler 构建环境openEuler 版本计划openEuler简介openEuler RISC-V 仓库介绍open
openEuler-20.03-LTS-SP2-x86_64-dvd支持鲲鹏及其它多种处理器,文件分割成 5个 压缩包,必须集齐5个 文件后才能一起解压一起使用: openEuler-20.03-LTS-SP2-x86_64-dvd.part5.rar ... openEuler-20.03-LTS-SP2-x86_...
华为欧拉系统 EulerOS-V2.0SP5-x86_64-dvd文件分割成 五个 压缩包,必须集齐 五个 文件后才能一起解压一起使用: EulerOS-V2.0SP5-x86_64-dvd.part5.rar ... EulerOS-V2.0SP5-x86_64-dvd.part4.rar ...