`

拆解数字

阅读更多
.
觉得这个童鞋的分析很劲道:
http://www.iteye.com/topic/963980?page=2



假设拆解10,那么我们有一下几种分法
   10 =9 + 1
=8 + 2 =8 + 1 + 1
=7 + 3 =7 + 2 + 1 =7 + 1 + 1 + 1
=6 + 4 =...(到这里的时候,我们看一下前面的3行,第1行是9+1,第2行是8+(2的两种拆分),第3行是7+(3的3种拆分拆分),到本行就是6+(4的各种拆分))
=5 + 5的各种拆分
=4 + ...(到这里我们不能用6的各种拆分,因为这样会与前面的数据有所重合,要保证这里每行的数据与其他行的数据不重合,我采用的方法是第一行每种拆分的最大值都是9,第二行的拆分的最大值都是8,到本行拆分的最大值应该是。所以,应该是4+小于等于4的书对6的拆分)
=3 + 小于等于3的数对7的各种拆分
=2 + 小于等于2的数对8的各种拆分
=1 + 小于等于1的数对9的各种拆分

如果,我们把小于等于x的数对于y的拆分表示成f(x,y),则上面的式子可以表示为:
  10 =9 + f(1,1)
=8 + f(2,2)
=7 + f(3,3)
=6 + f(4,4)
=5 + f(5,5)
=4 + f(4,6)
=3 + f(3,7)
=2 + f(2,8)
=1 + f(1,9)
看上面的式子能得出一个规律,1-5行实际上是1的拆分、2的拆分、3的拆分、4的拆分、5的拆分;
4-9行是f(n,10-n), n<5

这就需要研究f(x,y)的递归规律,
举例: f(3,5) = 3 + f(3, 2)
= 2 + f(2, 3)
= 1 + f(1, 4)

不难得出其中的循环规律。代码为:
import java.util.ArrayList;
import java.util.List;

public class TestHello {

    public static void main(String[] args) {
        final int NUM = 10;
        List<String> list = f(NUM, NUM);
        int total = list.size();
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        System.out.println("数字"+NUM+"共有" + total + "种拆法");

    }

    /**
     * 小于等于x的数对y的拆分
     * 
     * @return List的每一个元素为一种拆分情况
     */
    static List<String> f(int x, int y) {
        if (x < 1 || y < 1)
            return null;
        if (x > y) {
            return f(y, y); // 小于等于3的数对2的拆分,跟小于等于2的数对2的拆分实际上是一样的
        }
        List<String> result = new ArrayList<String>();
        if (x == 1) {
            StringBuilder sb = new StringBuilder("1");
            for (int i = 1; i < y; i++) {
                sb.append("+1");
            }
            result.add(sb.toString());
            return result;
        }else if (x == 2 && y == 2) {
            result.add("1+1");
            result.add("2");
            return result;
        }else{
            if (x == y) {
                result.add("" + x);
            }
            for (int i = x; i > 0; i--) {
                List<String> l = f(i, y - i);
                if(l==null){
                    continue;
                }
                for (int j = 0; j < l.size(); j++) {
                    String s = i + "+" + l.get(j);
                    result.add(s);
                }
            }
        }
        return result;
    }
}




.


还在一起探索:

Excalibur 写道
ggzwtj 写道
悲催啊,要输出所有结果,再怎么弄都是浮云,快不起来了。200的分解方法应该是3972999029388种吧。。。。

我算到40就eclipse就挂了……

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

http://www.iteye.com/topic/963980?page=4
#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;
}





.
分享到:
评论

相关推荐

    以和府捞面为例,拆解数字化【会员策略】.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