.
觉得这个童鞋的分析很劲道:
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语言的版本,并加上说明。 题目是这样的: 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 ...
行业分类-设备装置-利用三维数字化平台进行设备拆解模拟的方法和系统.zip
华为2018年上市的一款采用数字芯片方案的主动降噪耳机拆解
算法是解决特定问题或执行特定任务的一系列步骤或规则的有序集合。在计算机科学中,算法通常用来指导计算机执行特定的任务或解决问题。良好设计的算法能够有效地解决问题,并且在给定的输入下能够产生正确的输出。...
拆解:汽车金融数字化和直销转型的背后问题.docx
数字化改革v字模型-可编辑
这一周,Jones拆解了一台安捷伦Agilent B2912A 精密型电源/测量单元(SMU),它具备以下性能特性:10 fA/100 nV 最小电源分辨率(61/2 位),高分辨率的任意波形生成 (10μs最小间隔),高速数字转换能力 ( 采样...
2021-2025年中国废电拆解行业调研及数字营销战略研究报告.pdf
蓝桥杯培训教程 一、 逻辑推理 二、排序 三、 图形(矩阵) 四、 数字变幻 五、 数字组合与拆解 六、 字符串 七、 数制转换 八、 排列组合 九、 其它 十、 数据结构
DT890C+型数字万用表原理图 数字万用表 DT890C+型数字万用表原理图.pdf
戴尔T605塔式服务器拆解内容简介: 我们今天为大家展示的就是一款Dell PowerEdge T605 塔式服务器,从这款产品的型号我们就可以得到不少的配置信息,在戴尔的服务产品中,产品编号中的T 表示这是一款塔式服务器,而...
IEMENS下的一串数字,是西门子PLC的订货号,每一款产品,都有唯一的货号,就像每一个人有一个身份证一样。一人有4个身份证,但是西门子产品再多,也不会一款产品有几个订货号),下面是西门子手册内的产品订货号列表...
数字音频SPDIF转换AUX R/L , 可直接接小音箱,同轴输入,CODEC音频转换,DAC转换,前置音频放大
老乡鸡,餐饮数字化,门店数字化,门店运营 深度拆解老乡鸡,分析其战略定位、发展路径、市场营销、客服系统、融资策略、组织架构、总部运营、门店经营和数字化升级。
依靠系统支持库完成了对正整数完美分割,可将一个大的整数分割为多个数字!。 可将文本串拆解为单个文字,可方便用于字符统计!。 以上两个方法均采用数组方式实现!文字统计在非组件情况下统计 20万字左右 不到...
业务架构拆解(1).pdf
一端是对数字I/O隔离和保护所用的理想技术的争论,另一端则处于更高的架构层次,是对基于PLC的控制好还是基于PC/嵌入式计算机的控制好的争论。 鉴于工厂、工业和制造自动化的重要性越来越高,我们终于找到...
我们恰巧有机会拿到了这款产品进行拆解,一起来先睹为快! 亚马逊(Amazon)藉由其基于Alexa的Echo音箱,为支持语音控制的数字音频播放系统设定了新标准。从那时起,包括Bose与Sonos等老字号的音频公司,以及...
在传统PGC和UGC模式下,内容生成领域存在产能约束 和质量约束,PGC受制于人力资源... 根据《中国AI数字商业产业展望2021-2025》报告,预 测AI数字商业内容的市场规模将从2020年的40亿元,增 加到2025年的495亿元。