文档章节

Project Euler Problem 76-整数分拆

BlackJoker
 BlackJoker
发布于 2015/10/13 13:24
字数 762
阅读 12
收藏 0
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

© 著作权归作者所有

共有 人打赏支持
BlackJoker
粉丝 1
博文 17
码字总数 9270
作品 0
深圳
高级程序员
Bad Coder(2011-01-04)

再优美的语言,如果你真的把它当作草稿来用,也还真是可以写出一些自惭形秽的-_-! 依然以奋斗在 Project Euler 界的我为例(这次的热情貌似久了一点)。 Problem 27 我们拿到的只是坐标,并非...

Pope怯懦懦地
2017/12/09
0
0
Euler Project Problem 6

The sum of the squares of the first ten natural numbers is, 12 + 22 + ... + 102 = 385 The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)2 = 552 = 3025......

长平狐
2012/10/16
51
0
2018 Multi-University Training Contest 3

1001:Problem A. Ascending Rating 首先可以通过单调栈维护出每个位置右边第一个大于自己的数所在的位置,记为rightmax[i],然后维护一个双端队列。双端队列里维护[L,L+m-1]中的最长上升子序...

Hetui
07/31
0
0
纸笔的力量(2011-01-01)

对 Mathematica 着迷了,虽然我知道这热情不会持续多久。还是喜欢在解决问题中学习,这次是 Project Euler 的第 38 问。 提问:一个数依次×1,×2,……把所得连接成一个 9 位数,如果这个 ...

Pope怯懦懦地
2017/12/09
0
0
[Data Structures and Algorithms - 1] Introduction & Mathematics

References: 1. Stanford University CS97SI by Jaehyun Park 2. Introduction to Algorithms 3. Kuangbin's ACM Template 4. Data Structures by Dayou Liu 5. Euler's Totient Function Ge......

~yzhu
01/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

RabbitMq异常处理

1.查找指定文件位置 find . -name "*erlang.cookie" 2.Rabbitmq异常 ===========根据提示,应该是Erlang的cookie出现问题 attempted to contact: ['rabbit@DESKTOP-RVK1IHE'] rabbit@DESKTO......

zhaochaochao
21分钟前
2
0
Java虚拟机学习笔记

jconsole的连接 JConsole的远程连接 JConsole远程连接配置(用VisualVM进行远程连接的配置和JConsole是一摸一样滴) JVM之jconsole远程连接配置...

OSC_fly
22分钟前
1
0
区块链教程以太坊源码分析downloader-peer源码分析

  兄弟连区块链教程以太坊源码分析downloader-peer源码分析,区块链行业正逐渐褪去发展之初的浮躁、回归理性,表面上看相关人才需求与身价似乎正在回落。但事实上,正是初期泡沫的渐退,让...

兄弟连区块链入门教程
24分钟前
2
0
ubuntu 自定义记录用户登录以及操作日志

root@ms:~# cd /etc#更改之前先备份,养成良好的习惯,否则肠子都要悔青了root@ms:/etc# cp profile profile.bakroot@ms:/etc# vi profile 在文章末尾加入下列shell脚本 history US...

Marhal
24分钟前
1
0
liunx 下使用rpm进行软件卸载

rpm -qa | grep php 列出所有的php相关的rpm包 rpm -e xxx 删除包

bengozhong
24分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部