【问题描述】输入自然数n,然后将其拆分成由若干数相加的形式,参与加法运算的数可以重复。
【输入】待拆分的自然数n。
【输出】若干数的加法式子。
【样例输入】7
【样例输出】
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
7
回溯法:
import java.util.ArrayList;
public class Ncaifen {
private static final int N = 7;
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<Integer>();//保存数字序列
go(N, arr);
}
static void go(int m, ArrayList<Integer> arr) {
if (m == 0 && arr.size() > 1) {
printArr(arr);
return;
}
for (Integer i = 1; i <= m; i++) {
if (!arr.isEmpty() && i < arr.get(arr.size() - 1))
continue;
arr.add(i);
go(m - i, arr);
arr.remove(i);
}
}
private static void printArr(ArrayList<Integer> arr) {
// TODO Auto-generated method stub
for (int i = 0; i < arr.size(); i++) {
System.out.print(arr.get(i));
if (i < arr.size() - 1)
System.out.print("+");
}
System.out.println();
}
}
==================================================================================================
作者:nash_ 欢迎转载,与人分享是进步的源泉!
转载请保留原文地址:http://blog.csdn.net/nash_/article/details/8223323
===================================================================================================
分享到:
相关推荐
整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分
正整数拆分的一个简单的例子,C++实现,结果输出拆分的方案数
能够给出任意正整数的所有拆分情况和种数,注释详细,只用了一个嵌套函数。
TIA博途-整数拆分到字节数组中-全局FC库文件-V15版本
整数拆分 #include void main() { int n,i=0,a[100],m=0; scanf("%d",&n); while(n!=0) {
整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧
Chap2-1母函数、整数拆分.ppt
一条野路子,避免多循环原题链接:343. 整数拆分解题思路本解法主要思路就是将当前数为N时的情况精简为:f(N-2) * 2 和 f(N-3) * 3谁大取谁为
本文实例讲述了Golang算法问题之整数拆分实现方法。分享给大家供大家参考,具体如下: 一个整数总可以拆分为2的幂的和,例如: 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有6种...
把5拆分成若干无序正整数的和(若干可以包含1),请问有多少种拆分方法? 直接用枚举法实现: 5 = 5 5 = 4+1 5 = 3+2 5 = 3+1+1 5 = 2+2+1 5 = 2+1+1+1 5 = 1+1+1+1+1 很显然,结果为7。注意这里5 = 4+1和5=1+4是...
大一课设,可对正整数进行全部情况的拆分及仅用奇数拆分等操作,全部用C语言编写,适合入门学生,简单易懂,注释清楚,
实现目标:输入一个数值x,输出x的拆分数p(x) 解题思路:拆分数的计算没有明晰的公式可以套用,通过查阅资料,我了解到具体的实现方法有:递归法、动态规划、母函数法、五边形数定理,我只实现了这四个方法。
令dp[i]表示整数i对应的最大乘积,那么dp[i]的值应是dp[j]*(i-j),j属于[1,i-1]的最大值,同时注意dp[i]对应的值是经过拆分了的,所以
示例1:输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1。示例2:输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3
将 j 从 1 遍历到 i - 1,通过两种方式得到 dp[i]:(i - j) * j ,直接将 i 拆分为 i - j 和 j,获取两者乘积。dp[i -
示例 1:输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 ×
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释: 10 = 3...
将一个整数S随机拆分为N个在min~max之间的整数