`
ccjsjymg
  • 浏览: 60669 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

拆解数字

阅读更多
将任一个数字进行拆解,例如:

3 = 2+1 = 1+1+1 所以3有三種拆法
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五種
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1 共七种


随便给一个数字,对其进行拆解,并打印可拆解情况和拆解结果数。
分享到:
评论
43 楼 zhsq_java 2011-04-18  
public class SplitNum {
	public static void main(String[] args) {
		System.out.println("一共有" + splitNumber(20) + "种分法");
	}

	public static int splitNumber(int a) {
		return splitNumberWithMax(a, a, 0, a+" = ");
	}

	private static int splitNumberWithMax(int max, int tag, int c, String s) {
		if (tag == 1 || tag == 0) {
			System.out.println(tag == 1 ? (s + tag ) : s.substring(0,s.length()-2));
			c++;
		} else {
			for (int i = (max >= tag ? tag : max); i > 0; i--) {
				c = splitNumberWithMax(i, tag - i, c, s + i + " + ");
			}
		}
		return c;
	}
}

10 = 10
10 = 9 + 1
10 = 8 + 2
10 = 8 + 1 + 1
10 = 7 + 3
10 = 7 + 2 + 1
10 = 7 + 1 + 1 + 1
10 = 6 + 4
10 = 6 + 3 + 1
10 = 6 + 2 + 2
10 = 6 + 2 + 1 + 1
10 = 6 + 1 + 1 + 1 + 1
10 = 5 + 5
10 = 5 + 4 + 1
10 = 5 + 3 + 2
10 = 5 + 3 + 1 + 1
10 = 5 + 2 + 2 + 1
10 = 5 + 2 + 1 + 1 + 1
10 = 5 + 1 + 1 + 1 + 1 + 1
10 = 4 + 4 + 2
10 = 4 + 4 + 1 + 1
10 = 4 + 3 + 3
10 = 4 + 3 + 2 + 1
10 = 4 + 3 + 1 + 1 + 1
10 = 4 + 2 + 2 + 2
10 = 4 + 2 + 2 + 1 + 1
10 = 4 + 2 + 1 + 1 + 1 + 1
10 = 4 + 1 + 1 + 1 + 1 + 1 + 1
10 = 3 + 3 + 3 + 1
10 = 3 + 3 + 2 + 2
10 = 3 + 3 + 2 + 1 + 1
10 = 3 + 3 + 1 + 1 + 1 + 1
10 = 3 + 2 + 2 + 2 + 1
10 = 3 + 2 + 2 + 1 + 1 + 1
10 = 3 + 2 + 1 + 1 + 1 + 1 + 1
10 = 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1
10 = 2 + 2 + 2 + 2 + 2
10 = 2 + 2 + 2 + 2 + 1 + 1
10 = 2 + 2 + 2 + 1 + 1 + 1 + 1
10 = 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
10 = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
一共有42种分法

42 楼 hubeen 2011-04-08  
来个清爽的,随手写的,不保证一定正确,简单测了一下,应该没有问题。

public class Test {

	public static LinkedList<Integer> stack = new LinkedList<Integer>();

	public static int num = 5;

	public static void main(String[] args) {
		stack.add(1);
		decompose(num);
	}

	// 为了避免重复,所以拆解以后后面的数据>=前面的数字:4=1+3或2+2,5=1+4或2+3...
	public static void decompose(int i) {
		for (int j = stack.getLast(); j <= i / 2; j++) {
			stack.add(j);
			// 首先拆解的第二个数是满足条件的,所以先打印出来,再递归拆解第二个数
			stack.add(i - j);
			print();
			stack.removeLast();
			decompose(i - j);
			stack.removeLast();
		}
	}

	public static void print() {
		System.out.print(num + "=");
		for (int i = 1; i < stack.size(); i++) {
			System.out.print(i < stack.size() - 1 ? stack.get(i) + "+" : stack.get(i));
		}
		System.out.println();
	}

}


5=1+4
5=1+1+3
5=1+1+1+2
5=1+1+1+1+1
5=1+2+2
5=2+3
41 楼 landy126 2011-04-02  
<p>C++版的: </p>
<pre name="code" class="cpp">/*
输入一个整数,如:整数7它的和为 N1+N2+...+Nk=7,且 N1&gt;=N2&gt;=..&gt;=Nk(k&gt;=1),
将其拆分,并打印出各种拆分.对于7有: 6+1=7..5+2=7....1+1+1+1+1+1+1=7共有14种拆分方法。
分解过程:
输入3:
      (对5分解)  5=4+1             5=3+2  
(用递归对4分解)    4=3+1     4=2+2
                (用递归对3分解)      3=2+1
(用递归对2分解) 2=1+1
*/

#include&lt;iostream&gt;
#include&lt;list&gt;

using namespace std;

int count=0;//记录总的分解方法
int temp=0;

list&lt;int&gt; ilist;  //保存分解过程中产生的每种分解方法

void divide(int num, int flag);
void print(list&lt;int&gt; ilist, int num) //打印每种分解方法
{
list&lt;int&gt;::iterator ibegin, iend;
ibegin=ilist.begin();
iend=ilist.end();
if(ibegin==iend)
{
cout&lt;&lt;"The list is empty!"&lt;&lt;endl;
exit(EXIT_FAILURE);
}
cout&lt;&lt;num&lt;&lt;" = "&lt;&lt;*ibegin;
ibegin++;
while(ibegin!=iend)
{
cout&lt;&lt;"+"&lt;&lt;*ibegin;
ibegin++;
}
cout&lt;&lt;endl;
}

int main()
{
cout&lt;&lt;"Please inpu the num:"&lt;&lt;endl;
int num;
while(cin&gt;&gt;num , num&lt;=0)
{
cout&lt;&lt;"请输入大于0的正整数!"&lt;&lt;endl;
}
temp=num;
divide(num,1);//第二个参数可以改变(&gt;0)
cout&lt;&lt;"共有: "&lt;&lt;count&lt;&lt;" 种分法!"&lt;&lt;endl;
return 0;
}

void divide(int num, int flag)
{

if(num==flag) //当num==flag时到了最底层的分解
{
if(!ilist.empty())
{
ilist.pop_front();
}
ilist.push_front(flag);

print(ilist,temp);
ilist.pop_front();  //当递归回退一层时删除list中的第一个元素
return;
}
if(!ilist.empty())
{
print(ilist,temp);//每次进入divide一次就产生了一种分法,将其打印输出
}
for(int i=flag; i&lt;=num/2; i++)
{
count++;

if(!ilist.empty())
{
ilist.pop_front(); //对于ilist.front()产生了一种分解方法,
}
ilist.push_front(i); //将ilist.front()取出并将两分解元素push到ilist头部
ilist.push_front(num-i);

divide(num-i,i);//递归
}
if(!ilist.empty())
{
ilist.pop_front();//当递归回退一层时删除list中的第一个元素
}
}</pre>
<p>  </p>
<p> </p>
40 楼 ymkyve 2011-03-28  
数学都不错啊 
39 楼 Sehoney 2011-03-22  
buptwhisper 写道
不考虑顺序问题,也可以改用组合方式,如下:
对于n = 1 + 1 + 1 + 1 + ... + 1这列组合加数,其中的 + 取任意个(大于等于1个),即从n-1个加号中任意取出m个 1<=m<=n-1,这就对应着一个拆数
所以拆数就是2^(n-1) - 1种。

这个会重复很多吧````
38 楼 backshadow 2011-03-22  
ggzwtj 写道
ggzwtj 写道
这个可以用动态规划来做:
状态:dp[x][y]表示将x拆分成的最大值为y的方法总数。
过程:dp[x][y] = dp[x-y][1] + dp[x-y][2] + … +dp[x-y][y];
结果:result = dp[n][1] + dp[n][2] + dp[n][3] + … + dp[n][n];

ps:过程中要小心数组越界(要是有代码需求我帮你写哈

import java.util.Scanner;

/**
* @author tianchi.gzt
*
* 求数字n的拆分的方法的总数(不考虑顺序)
*/
public class test {
int[][] dp;
int n;
public test(){
}
public void setN(int n){
this.n = n;
dp = new int[n+1][n+1];
dp[1][1] = dp[0][0] =1;

for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++){
for(int k = 0; k <= j; k++){
dp[i][j] += dp[i-j][k];
}
}
}
}
public int solve(){
int result = 0;
for(int i = 1; i <= n; i++){
result += dp[n][i];
}
return result;
}
public void show(){
for(int i = n; i >= 0; --i){
for(int j = 0; j <=n; j++){
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
test a = new test();
while(true){
a.setN(scanner.nextInt());
a.show();
System.out.println(a.solve());
}
}
}

现在补充代码,测试过了,可以算出来,可以看出具体的分法的大概。:) 休息吧。。。


顶,最喜欢动态规划了,虽然不太熟
37 楼 dongya1987 2011-03-21  
ccjsjymg 写道

LONG f(int x, int y
#ifdef PRINT_RESULT
	, int print
#endif
)
...
int main(int argc, char ** argv)
{
	int input;
	LONG n = 0;
	int print = 0;
	if(argc > 1 && 0 == strcmp(argv[1], "print"))
		print = 1;
	assert( sizeof(LONG) == 8);
	while(scanf("%d", &input)!=EOF)
	{
	 init();
     n = f(input, 1
#ifdef PRINT_RESULT
		 ,print
#endif
		 );
	 printf("%lld\n", n );
	}
	 return 0;
}




学习了,原来宏还可以这么用
36 楼 ccjsjymg 2011-03-20  
#include <stdio.h>
#include <assert.h>

typedef  long long LONG;
#define N 1000
LONG sr[N][N];

#ifdef _DEBUG
#define PRINT_RESULT
#endif

#ifdef PRINT_RESULT
int steps[N];
#endif 

LONG f(int x, int y
#ifdef PRINT_RESULT
	, int print
#endif
)
{
#ifdef PRINT_RESULT
	static int s = 0;
	int i =0;
	assert(s < N);
#endif 
	if(!print)
	    if(sr[x][y])
		  return sr[x][y];
	LONG n = 0;
	int original_y = y;
	assert(x >= y && y > 0);
	while(x - y >= y)
	{
#ifdef PRINT_RESULT
		if(print)
			steps[s++] = y;
#endif
		n += f(x-y, y
#ifdef PRINT_RESULT
			, print
#endif
			);
		assert( n > 0);	//avoid integer overflow

#ifdef PRINT_RESULT
		--s;
#endif
		++ y;
	}
#ifdef PRINT_RESULT
	if(print)
	{
		for (i=0; i<s ; i++ )
		{
			printf(" + %d", steps[i]);
		}
		printf(" + %d\n", x);
	}
#endif
	n += 1;
	assert( n > 0);

       if(!print)
	   return sr[x][original_y] = n;
       else
           return n;
}

void init()
{
	memset(sr, 0, sizeof(sr));
}
int main(int argc, char ** argv)
{
	int input;
	LONG n = 0;
	int print = 0;
	if(argc > 1 && 0 == strcmp(argv[1], "print"))
		print = 1;
	assert( sizeof(LONG) == 8);
	while(scanf("%d", &input)!=EOF)
	{
	 init();
     n = f(input, 1
#ifdef PRINT_RESULT
		 ,print
#endif
		 );
	 printf("%lld\n", n );
	}
	 return 0;
}


35 楼 ggzwtj 2011-03-18  
输出的话在50以内不是非常慢,不输出的话在90以内不是非常慢
34 楼 ggzwtj 2011-03-18  
import java.math.BigInteger;
import java.util.Scanner;

/**
* @author tianchi.gzt
*
* 求数字n的拆分的方法的总数(不考虑顺序)
*/
public class test{
static int[] a = new int[100];
static int result = 0;
public static void show(int n, int m, int big){
if(n == 0){
result++;
System.out.print("= " +a[0]);
for(int i = 1; i < m; i++){
System.out.print(" + " + a[i]);
}
System.out.println();
}
int i;
if(n > big){
i = big;
}else{
i = n;
}
for(; i > 0; i--){
a[m] = i;
show(n-i, m+1, i);
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(true){
result = 0;
int tmp = scanner.nextInt();
System.out.println(tmp);
show(tmp, 0, tmp);
System.out.println(result);
}
}
}
33 楼 ggzwtj 2011-03-18  
好吧,我觉得如果非得输出所有的情况反而使得问题变得简单,因为我们没有必要考虑优化了。下面是代码:
import java.math.BigInteger;
import java.util.Scanner;

/**
* @author tianchi.gzt
*
* 求数字n的拆分的方法的总数(不考虑顺序)
*/
public class test{
static int[] a = new int[100];
static int result = 0;
public static void show(int n, int m, int big){
if(n == 0){
result++;
System.out.print("= " +a[0]);
for(int i = 1; i < m; i++){
System.out.print(" + " + a[i]);
}
System.out.println();
}
int i;
if(n > big){
i = big;
}else{
i = n;
}
for(; i > 0; i--){
a[m] = i;
show(n-i, m+1, i);
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(true){
result = 0;
int tmp = scanner.nextInt();
System.out.println(tmp);
show(tmp, 0, tmp);
System.out.println(result);
}
}
}
这里说明一下啊,如果是非得输出的话,肯定是非常慢的,有那么多要输出的东西。如果把输出的部分去掉的话,速度还是很快的。
32 楼 ggzwtj 2011-03-18  
Excalibur 写道
ggzwtj 写道
悲催啊,要输出所有结果,再怎么弄都是浮云,快不起来了。200的分解方法应该是3972999029388种吧。。。。

我算到40就eclipse就挂了……

不至于吧,40的时候只有37338种分解。
31 楼 whimmy 2011-03-18  
dongya1987 写道
Excalibur 写道
ggzwtj 写道
悲催啊,要输出所有结果,再怎么弄都是浮云,快不起来了。200的分解方法应该是3972999029388种吧。。。。

我算到40就eclipse就挂了……

我的57还能抗住,58就OutOfMemoryError了。谁能帮我把我的递归修成循环啊 ,探索中...

你的速度如何?
30 楼 dongya1987 2011-03-18  
Excalibur 写道
ggzwtj 写道
悲催啊,要输出所有结果,再怎么弄都是浮云,快不起来了。200的分解方法应该是3972999029388种吧。。。。

我算到40就eclipse就挂了……

我的57还能抗住,58就OutOfMemoryError了。谁能帮我把我的递归修成循环啊 ,探索中...
29 楼 Excalibur 2011-03-18  
ggzwtj 写道
悲催啊,要输出所有结果,再怎么弄都是浮云,快不起来了。200的分解方法应该是3972999029388种吧。。。。

我算到40就eclipse就挂了……
28 楼 ggzwtj 2011-03-18  
悲催啊,要输出所有结果,再怎么弄都是浮云,快不起来了。200的分解方法应该是3972999029388种吧。。。。
27 楼 Excalibur 2011-03-18  
ggzwtj 写道
dongya1987 写道
ggzwtj 写道

你有没有测试过你代码的速度?


我测试了,你的速度是最快的。但你没有完全满足楼主的题目要求,楼主要的不只是个数


哎呀,没看清,丢人了。
不过我想了一下,其实这个也是可以用动态规划来实现了。可以用DFS生成具体的分解方法,另外可以用dp数组中的值做限制。

动态规划刚刚开始看,以前不关注算法的。这个公式找起来不容易
26 楼 ggzwtj 2011-03-18  
dongya1987 写道
ggzwtj 写道

你有没有测试过你代码的速度?


我测试了,你的速度是最快的。但你没有完全满足楼主的题目要求,楼主要的不只是个数


哎呀,没看清,丢人了。
不过我想了一下,其实这个也是可以用动态规划来实现了。可以用DFS生成具体的分解方法,另外可以用dp数组中的值做限制。
25 楼 dongya1987 2011-03-18  
ggzwtj 写道

你有没有测试过你代码的速度?


我测试了,你的速度是最快的。但你没有完全满足楼主的题目要求,楼主要的不只是个数
24 楼 Excalibur 2011-03-18  
ggzwtj 写道
Excalibur 写道
ggzwtj 写道


你有没有测试过你代码的速度?



求快速的解法

最快的方法是打表,其次就是求公式,再不行就动态规划,实在实在不行了,就模拟。

看了你那个动态规划,但题目里有这个要求

“并打印可拆解情况”

相关推荐

Global site tag (gtag.js) - Google Analytics