`
ccjsjymg
  • 浏览: 62086 次
  • 性别: 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 写道


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



求快速的解法

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

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

“并打印可拆解情况”

相关推荐

    以和府捞面为例,拆解数字化【会员策略】.pdf

    以和府捞面为例,拆解数字化【会员策略】.pdf

    C经典算法之数字拆解

    根据给定的信息,本文将详细解析“C经典算法之数字拆解”这一主题,包括算法原理、代码解读以及实现思路。 ### 算法背景与原理 #### 数字拆解问题定义 数字拆解问题是一种经典的组合数学问题,其目标是求出一个正...

    行业分类-设备装置-利用三维数字化平台进行设备拆解模拟的方法和系统.zip

    "行业分类-设备装置-利用三维数字化平台进行设备拆解模拟的方法和系统"这一主题,揭示了现代工业如何借助先进的数字工具提高工作效率和精度。 三维数字化平台是一种集成化、智能化的技术平台,它能够将实体设备以...

    数字化改革v字模型-可编辑

    数字化改革v字模型-可编辑...数字化改革v字模型-可编辑是指一种基于任务分解和数据集成的数字化改革方法,该方法通过逐级拆解、确定协同关系、建立指标体系、确定数据需求等步骤,逐步构建起一个完整的数字化改革框架。

    GIF拆解&组合

    总的来说,GIF拆解与组合是数字图像处理的重要组成部分,它为内容创作者提供了更多的可能性。无论是为了编辑现有的GIF,还是创作新的动态内容,掌握这一技能都能大大提高效率和创新性。同时,随着技术的发展,越来越...

    三菱FX2N PLC 拆解图片

    4. **输入/输出接口**:FX2N PLC通常有多种类型的I/O接口,如数字量输入/输出、模拟量输入/输出,以适应不同的传感器和执行器。拆解过程中能看到这些接口的物理布局和连接方式。 5. **电源模块**:为PLC各部分提供...

    万字拆解珀莱雅的数字化战略.docx

    万字拆解珀莱雅的数字化战略.docx

    西师二年级下册数学一单元数数时PPT课件.pptx

    通过这样的练习,孩子们可以更好地理解和拆解数字。 5. 大数的认识:课件通过实例教授学生如何理解和表达大数,如一千零五十由1个千和5个十组成,二千零一十由2个千和10个十组成。这有助于培养孩子的数感,理解大数...

    2021-2025年中国废电拆解行业调研及数字营销战略研究报告.pdf

    在2021至2025年期间,中国废电拆解行业的发展和数字营销战略是当前经济与环保双重背景下受到关注的话题。这份报告深入分析了废电拆解行业的发展现状、政策环境、行业趋势以及数字营销战略的选择与实施。 在废电拆解...

    新北师大版一年级数学下册第一次月考卷.doc

    3. 15-9的思考过程:让学生理解如何拆解数字进行计算,如15-9可以通过10-5和5+4来完成。 4. 13-8的思考:引导学生通过加法逆向思维进行减法计算,例如8加5等于13,所以13减8等于5。 5. 符号比较:比较大小,训练学生...

    C程序算法大全

    数字拆解涉及到将一个整数分解为其各个位上的数字。 #### 31. 得分排行 得分排行涉及到排序和数据结构设计,以便快速更新和查询排名。 #### 32. 选择、插入、气泡排序 选择排序、插入排序和气泡排序是三种基本的...

    西门子S7-200拆解拍图

    文件中提到的数字量输入为14点,意味着该PLC具有14个数字量输入通道,可接受来自传感器的数字信号;数字量输出为10点,代表有10个数字量输出通道,可控制继电器等执行元件。 5. 存储器功能: 文件中提及的FLASH...

    元器件应用中的拆解安捷伦电源/测量单元(SMU)

    【元器件应用中的拆解安捷伦电源/测量单元(SMU)】 安捷伦电源/测量单元(SMU)是一种高度精密的测试设备,常用于半导体器件的测量和表征。Dave Jones在他的EEVblog中拆解了Agilent B2912A型号的SMU,揭示了其内部...

    华为主动降噪耳机3拆解

    华为2018年上市的一款采用数字芯片方案的主动降噪耳机拆解

    基于PLC的报废汽车拆解线作业控制系统.pdf

    首先,PLC(Programmable Logic Controller,可编程逻辑控制器)是一种用于自动化控制的电子设备,它采用可编程的存储器,用于其内部存储执行逻辑运算、顺序控制、定时、计数和算术运算等操作的指令,并通过数字或...

    数字拆解.zip

    算法是解决特定问题或执行特定任务的一系列步骤或规则的有序集合。在计算机科学中,算法通常用来指导计算机执行特定的任务或解决问题。良好设计的算法能够有效地解决问题,并且在给定的输入下能够产生正确的输出。...

    compaq系列笔记本拆解 教程

    - **键盘**: 标准全尺寸键盘,带有独立的数字小键盘区域。 - **触控板**: 支持多点触摸功能,便于实现手势操作。 - **音频**: 内置扬声器和支持麦克风输入。 - **摄像头**: 高清网络摄像头,方便视频通话和会议使用...

    天猫精灵M1智能音箱拆解

    - **数字功放**:采用了TI的TAS5733L数字功放芯片,支持I2S输入,最大输出功率可达10W,保证了良好的音质效果。 - **电源管理**:使用TI的TPS562208同步降压转换器进行电源管理,该芯片能够在4.5-17V的宽电压范围...

    flash文件拆解器

    在数字媒体领域,Flash曾是网页动画和交互设计的重要工具,而“Flash文件拆解器”则为开发者和设计师提供了深入探索SWF文件内容的窗口。本文将详细解析Flash文件拆解器的功能、工作原理以及其在实际应用中的价值。 ...

    蓝桥杯培训教程+逻辑推理+排序+ 图形(矩阵)+ 数字变幻+ 数字组合与拆解+字符串+ 数制转换+排列组合等

    蓝桥杯培训教程 一、 逻辑推理 二、排序 三、 图形(矩阵) 四、 数字变幻 五、 数字组合与拆解 六、 字符串 七、 数制转换 八、 排列组合 九、 其它 十、 数据结构

Global site tag (gtag.js) - Google Analytics