文档章节

Project Euler Problem 76-整数分拆

BlackJoker
 BlackJoker
发布于 2015/10/13 13:24
字数 762
阅读 15
收藏 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, 1 2 + 2 2 + ... + 10 2 = 385 The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10) 2 = 55 2 =......

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

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

Hetui
2018/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......

rgvb178
2018/01/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周三乱弹 —— 孤独到都和病毒发生了感情了

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @-冰冰棒- :#今日歌曲推荐# 逃跑计划《一万次悲伤 (Live)》 《一万次悲伤 (Live)》- 逃跑计划 手机党少年们想听歌,请使劲儿戳(这里) 现在...

小小编辑
今天
97
8
test

//// main.c// Test//// Created by 吕颖 on 2019/1/16.// Copyright © 2019年 carmen. All rights reserved.//#include <stdio.h>#include <stdlib.h>#include <t......

carmen-ly
今天
3
0
Android webview热门组件agentweb:4.0.2无法自适应的问题

Android webview热门组件agentweb:4.0.2无法自适应的问题 //设置自适应屏幕,两者合用mAgentWeb.getAgentWebSettings().getWebSettings().setUseWideViewPort(true); //将图片调整到适合w...

Gemini-Lin
今天
5
0
如何维护一个自己的 golang doc 服务

本文内容是如何维护一个golang 在线的doc 服务。 1 什么是godoc ? godoc 是 golang 官方提供的文档生成工具, 2 为什么要有godoc ? 我们经常遇到一个问题,就是代码和文档不一致,线上代码版...

鼎铭
今天
5
0
js中的对象创建的模式以及继承模式

对象创建模式: 工厂模式 构造函数模式 原型模式 继承模式 原型式继承 寄生式继承 构造函数 原型式和构造函数的组合式(缺点:运行两次超类类函数,积累函数的属性被挂载在原型对象上和实例对...

莫西摩西
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部