.
觉得这个童鞋的分析很劲道:
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
根据给定的信息,本文将详细解析“C经典算法之数字拆解”这一主题,包括算法原理、代码解读以及实现思路。 ### 算法背景与原理 #### 数字拆解问题定义 数字拆解问题是一种经典的组合数学问题,其目标是求出一个正...
"行业分类-设备装置-利用三维数字化平台进行设备拆解模拟的方法和系统"这一主题,揭示了现代工业如何借助先进的数字工具提高工作效率和精度。 三维数字化平台是一种集成化、智能化的技术平台,它能够将实体设备以...
数字化改革v字模型-可编辑...数字化改革v字模型-可编辑是指一种基于任务分解和数据集成的数字化改革方法,该方法通过逐级拆解、确定协同关系、建立指标体系、确定数据需求等步骤,逐步构建起一个完整的数字化改革框架。
GIF拆解与组合在数字图像处理中的应用 在图像处理领域,GIF(Graphics Interchange Format)作为一种常见的图形交换格式,因其独特性在动态图像的网络传输与展示上占据了重要的地位。GIF通常由连续的帧组成,这些帧...
4. **输入/输出接口**:FX2N PLC通常有多种类型的I/O接口,如数字量输入/输出、模拟量输入/输出,以适应不同的传感器和执行器。拆解过程中能看到这些接口的物理布局和连接方式。 5. **电源模块**:为PLC各部分提供...
万字拆解珀莱雅的数字化战略.docx
例如,在计算25×16时,学生可能会错误地拆解数字,而非采用更加简便的组合方式。这种错误拆解的方法,不但降低了计算效率,也阻碍了学生对乘法运算律的正确应用。 为了解决上述问题,教师在教学过程中应当着重于...
通过这样的练习,孩子们可以更好地理解和拆解数字。 5. 大数的认识:课件通过实例教授学生如何理解和表达大数,如一千零五十由1个千和5个十组成,二千零一十由2个千和10个十组成。这有助于培养孩子的数感,理解大数...
在2021至2025年期间,中国废电拆解行业的发展和数字营销战略是当前经济与环保双重背景下受到关注的话题。这份报告深入分析了废电拆解行业的发展现状、政策环境、行业趋势以及数字营销战略的选择与实施。 在废电拆解...
验收入库是报废车处理流程的首要环节,系统通过数字化手段极大简化了这一过程。车辆身份验证、状态检查、价值评估等多个环节,过去往往依赖人工进行,不仅耗时长、效率低,而且容易受到主观因素的影响,导致评估结果...
3. 15-9的思考过程:让学生理解如何拆解数字进行计算,如15-9可以通过10-5和5+4来完成。 4. 13-8的思考:引导学生通过加法逆向思维进行减法计算,例如8加5等于13,所以13减8等于5。 5. 符号比较:比较大小,训练学生...
数字拆解涉及到将一个整数分解为其各个位上的数字。 #### 31. 得分排行 得分排行涉及到排序和数据结构设计,以便快速更新和查询排名。 #### 32. 选择、插入、气泡排序 选择排序、插入排序和气泡排序是三种基本的...
文件中提到的数字量输入为14点,意味着该PLC具有14个数字量输入通道,可接受来自传感器的数字信号;数字量输出为10点,代表有10个数字量输出通道,可控制继电器等执行元件。 5. 存储器功能: 文件中提及的FLASH...
老师在教学中,通过举例子、拆解数字、引导学生寻找规律等方式,帮助学生加深理解。而且,鼓励学生运用不同的计算策略,如拆分、组合、竖式计算等,可以更高效地完成计算任务。 总之,非整十数的两位数乘法是小学生...
这类题目要求孩子不仅能够快速计算,还要学会拆解数字,将大数拆分成易于计算的小数,然后将结果相加。在实际操作中,这不仅能提高孩子们的计算能力,还能锻炼他们的逻辑思维。 进位加法是加法中的另一个重要概念。...
【元器件应用中的拆解安捷伦电源/测量单元(SMU)】 安捷伦电源/测量单元(SMU)是一种高度精密的测试设备,常用于半导体器件的测量和表征。Dave Jones在他的EEVblog中拆解了Agilent B2912A型号的SMU,揭示了其内部...
华为2018年上市的一款采用数字芯片方案的主动降噪耳机拆解
首先,PLC(Programmable Logic Controller,可编程逻辑控制器)是一种用于自动化控制的电子设备,它采用可编程的存储器,用于其内部存储执行逻辑运算、顺序控制、定时、计数和算术运算等操作的指令,并通过数字或...
算法是解决特定问题或执行特定任务的一系列步骤或规则的有序集合。在计算机科学中,算法通常用来指导计算机执行特定的任务或解决问题。良好设计的算法能够有效地解决问题,并且在给定的输入下能够产生正确的输出。...