ccjsjymg
- 浏览: 60896 次
- 性别:
- 来自: 北京
-
最新评论
将任一个数字进行拆解，例如： 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 共七种 随便给一个数字，对其进行拆解，并打印可拆解情况和拆解结果数。
分享到：
评论
23 楼
ggzwtj
2011-03-18
Excalibur 写道
ggzwtj 写道
你有没有测试过你代码的速度？
求快速的解法
最快的方法是打表
，其次就是求公式，再不行就动态规划，实在实在不行了，就模拟。
22 楼
Excalibur
2011-03-18
ggzwtj 写道
你有没有测试过你代码的速度？
求快速的解法
21 楼
ggzwtj
2011-03-18
Excalibur 写道
dongya1987 写道
实验了一下，对6的拆分中少了2+2+2这种情况
import java.util.LinkedList;
/**
* 将任一个数字进行拆解，例如：
*
* 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 共七种
*
* 随便给一个数字，对其进行拆解，并打印可拆解情况和拆解结果数。
*/
public class Uncoil {
public static void main(String[] args) {
LinkedList<LinkedList<LinkedList<Integer>>> results = new LinkedList<LinkedList<LinkedList<Integer>>>();
LinkedList<LinkedList<Integer>> result = new LinkedList<LinkedList<Integer>>();
LinkedList<Integer> oneResult;
int input = 20;
for (int i = 1; i <= input; i++) {
result = new LinkedList<LinkedList<Integer>>();
oneResult = new LinkedList<Integer>();
oneResult.add(i);
result.add(oneResult);
for (int j = i / 2; j >=1 ; j--) {
LinkedList<LinkedList<Integer>> lefts = results.get(i - j - 1);
for (LinkedList<Integer> left : lefts) {
if (left.getLast() < j) {
break;
}
oneResult = new LinkedList<Integer>();
oneResult.addAll(left);
oneResult.add(j);
result.add(oneResult);
}
}
results.add(result);
}
for (LinkedList<LinkedList<Integer>> os : results) {
System.out.println("====================" + os.size());
// for (LinkedList<Integer> o : os) {
// System.out.println(o);
// }
}
}
}
你有没有测试过你代码的速度？
20 楼
Excalibur
2011-03-18
dongya1987 写道
实验了一下，对6的拆分中少了2+2+2这种情况
import java.util.LinkedList;
/**
* 将任一个数字进行拆解，例如：
*
* 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 共七种
*
* 随便给一个数字，对其进行拆解，并打印可拆解情况和拆解结果数。
*/
public class Uncoil {
public static void main(String[] args) {
LinkedList<LinkedList<LinkedList<Integer>>> results = new LinkedList<LinkedList<LinkedList<Integer>>>();
LinkedList<LinkedList<Integer>> result = new LinkedList<LinkedList<Integer>>();
LinkedList<Integer> oneResult;
int input = 20;
for (int i = 1; i <= input; i++) {
result = new LinkedList<LinkedList<Integer>>();
oneResult = new LinkedList<Integer>();
oneResult.add(i);
result.add(oneResult);
for (int j = i / 2; j >=1 ; j--) {
LinkedList<LinkedList<Integer>> lefts = results.get(i - j - 1);
for (LinkedList<Integer> left : lefts) {
if (left.getLast() < j) {
break;
}
oneResult = new LinkedList<Integer>();
oneResult.addAll(left);
oneResult.add(j);
result.add(oneResult);
}
}
results.add(result);
}
for (LinkedList<LinkedList<Integer>> os : results) {
System.out.println("====================" + os.size());
// for (LinkedList<Integer> o : os) {
// System.out.println(o);
// }
}
}
}
19 楼
ggzwtj
2011-03-18
1:1
2:2
3:3
4:5
5:7
6:11
7:15
8:22
9:30
10:42
11:56
12:77
13:101
14:135
15:176
16:231
17:297
18:385
19:490
20:627
21:792
22:1002
23:1255
24:1575
25:1958
26:2436
27:3010
28:3718
29:4565
30:5604
31:6842
32:8349
33:10143
34:12310
35:14883
36:17977
37:21637
38:26015
39:31185
40:37338
这个是1到40的分法的值，大家可以测试一下代码。
2:2
3:3
4:5
5:7
6:11
7:15
8:22
9:30
10:42
11:56
12:77
13:101
14:135
15:176
16:231
17:297
18:385
19:490
20:627
21:792
22:1002
23:1255
24:1575
25:1958
26:2436
27:3010
28:3718
29:4565
30:5604
31:6842
32:8349
33:10143
34:12310
35:14883
36:17977
37:21637
38:26015
39:31185
40:37338
这个是1到40的分法的值，大家可以测试一下代码。
18 楼
Excalibur
2011-03-18
不太会用这个
17 楼
ggzwtj
2011-03-18
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：过程中要小心数组越界（要是有代码需求我帮你写哈 ）
状态：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());
}
}
}
现在补充代码，测试过了，可以算出来，可以看出具体的分法的大概。:) 休息吧。。。
16 楼
dongya1987
2011-03-18
Excalibur 写道
import java.util.LinkedList;
/**
* 将任一个数字进行拆解，例如：
*
* 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 共七种
*
* 随便给一个数字，对其进行拆解，并打印可拆解情况和拆解结果数。
*/
public class Uncoil {
public static void main(String[] args) {
LinkedList<LinkedList<LinkedList<Integer>>> results = new LinkedList<LinkedList<LinkedList<Integer>>>();
LinkedList<LinkedList<Integer>> result = new LinkedList<LinkedList<Integer>>();
LinkedList<Integer> oneResult;
int input = 20;
for (int i = 1; i <= input; i++) {
result = new LinkedList<LinkedList<Integer>>();
oneResult = new LinkedList<Integer>();
oneResult.add(i);
result.add(oneResult);
for (int j = 1; j <= i / 2; j++) {
LinkedList<LinkedList<Integer>> lefts = results.get(i - j - 1);
for (LinkedList<Integer> left : lefts) {
if (left.getLast() < j) {
break;
}
oneResult = new LinkedList<Integer>();
oneResult.addAll(left);
oneResult.add(j);
result.add(oneResult);
}
}
results.add(result);
}
for (LinkedList<LinkedList<Integer>> os : results) {
System.out.println("====================" + os.size());
for (LinkedList<Integer> o : os) {
System.out.println(o);
}
}
}
}
实验了一下，对6的拆分中少了2+2+2这种情况
15 楼
Excalibur
2011-03-18
import java.util.LinkedList;
/**
* 将任一个数字进行拆解，例如：
*
* 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 共七种
*
* 随便给一个数字，对其进行拆解，并打印可拆解情况和拆解结果数。
*/
public class Uncoil {
public static void main(String[] args) {
LinkedList<LinkedList<LinkedList<Integer>>> results = new LinkedList<LinkedList<LinkedList<Integer>>>();
LinkedList<LinkedList<Integer>> result = new LinkedList<LinkedList<Integer>>();
LinkedList<Integer> oneResult;
int input = 20;
for (int i = 1; i <= input; i++) {
result = new LinkedList<LinkedList<Integer>>();
oneResult = new LinkedList<Integer>();
oneResult.add(i);
result.add(oneResult);
for (int j = 1; j <= i / 2; j++) {
LinkedList<LinkedList<Integer>> lefts = results.get(i - j - 1);
for (LinkedList<Integer> left : lefts) {
if (left.getLast() < j) {
break;
}
oneResult = new LinkedList<Integer>();
oneResult.addAll(left);
oneResult.add(j);
result.add(oneResult);
}
}
results.add(result);
}
for (LinkedList<LinkedList<Integer>> os : results) {
System.out.println("====================" + os.size());
for (LinkedList<Integer> o : os) {
System.out.println(o);
}
}
}
}
14 楼
ggzwtj
2011-03-18
nianien 写道
就是走楼梯算法:
给定n阶楼梯，可以一次跨1阶、2阶……k阶(k<=n,问共有多少走法，并记录每种走法
递归公式: f(n) = f(n-1) + f(n-2) + f(n-3)+……+f(n-k) n>=1
private void climb(int n, int step,List<int> steps)
{
if (step > n)
return;
steps.Add(step);
if (n == step)
{
//当剩余楼梯的阶数等于第一步所跨的阶数
//则到达最后一阶楼梯，此时为其中一种走法
//记录每次走法
this.count++;
print(steps);
}
else
{
//如果没有达到最后一层，则递归剩余楼梯的走法
//此时，第一可跨最大阶数由允许所跨最大阶数和剩余楼梯阶数的较小值决定
for (int i = 1; i <= stemp&& i <= n - step; i++)
{
//递归剩余楼梯第一步的每种走法
climb(n - step, i);
//退出递归时，清除剩余楼梯的走法
//以记录新的走法
list.RemoveAt(list.Count - 1);
}
}
}
测试结果 :n=5,step=5时,共有16种走法：
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
这是考虑顺序的,你上面的就更简单了,不考虑顺序,放进set对象里过滤一下就可以了
给定n阶楼梯，可以一次跨1阶、2阶……k阶(k<=n,问共有多少走法，并记录每种走法
递归公式: f(n) = f(n-1) + f(n-2) + f(n-3)+……+f(n-k) n>=1
private void climb(int n, int step,List<int> steps)
{
if (step > n)
return;
steps.Add(step);
if (n == step)
{
//当剩余楼梯的阶数等于第一步所跨的阶数
//则到达最后一阶楼梯，此时为其中一种走法
//记录每次走法
this.count++;
print(steps);
}
else
{
//如果没有达到最后一层，则递归剩余楼梯的走法
//此时，第一可跨最大阶数由允许所跨最大阶数和剩余楼梯阶数的较小值决定
for (int i = 1; i <= stemp&& i <= n - step; i++)
{
//递归剩余楼梯第一步的每种走法
climb(n - step, i);
//退出递归时，清除剩余楼梯的走法
//以记录新的走法
list.RemoveAt(list.Count - 1);
}
}
}
测试结果 :n=5,step=5时,共有16种走法：
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
这是考虑顺序的,你上面的就更简单了,不考虑顺序,放进set对象里过滤一下就可以了
晕，还用set那么麻烦
13 楼
ggzwtj
2011-03-18
buptwhisper 写道
ggzwtj 写道
buptwhisper 写道
这个可以用一个递归来实现，对于任意的整数n,记拆解方式为g, 且作以下假设：
1).最后一个拆数是1，则拆解方式为 g(n-1) + 1，这个+1表示在g(n-1)的末尾加上一个1
2).最后一个拆数是2，则拆解方式为 g(n-2) + 2.依次类推，直到最后一个拆解数为
n-1。
这样就完成了拆解，不过复杂度比较高，可以试着改善一下。
1).最后一个拆数是1，则拆解方式为 g(n-1) + 1，这个+1表示在g(n-1)的末尾加上一个1
2).最后一个拆数是2，则拆解方式为 g(n-2) + 2.依次类推，直到最后一个拆解数为
n-1。
这样就完成了拆解，不过复杂度比较高，可以试着改善一下。
g(n-2) + 2是什么意思？g(n)表示的是最后的结果吗？
是的。
那这个是不是会产生重复？
12 楼
dongya1987
2011-03-18
假设拆解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;
}
}
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;
}
}
11 楼
peter.e.king
2011-03-18
/**
* 递归，将上一个数字拆解的情况做一个二维数字
比喻3=2+1=2+1+1 可以存储为int[][] arr
arr[0]={3]
arr[1]={2，1}
arr[2]={1，1，1}
* @author peter.e.king
*
*/
public class SplitNumber {
public static void splitNumber(int x){
if(x<1){
System.out.println("请输入自然数！");
} else if (x==1){
System.out.println("数字『1』可以分解成的组合数为："+1);
System.out.println("数字『1』可以分解成的表达式为：1");
}else {
StringBuffer showStr = new StringBuffer("1");
for(int i=2;i<=x;i++){
getByPreArr(showStr);
}
System.out.println("数字『"+x+"』可以分解成的组合数为："+showStr.toString().split("=").length);
System.out.println("数字『"+x+"』可以分解成的表达式为："+showStr.toString());
}
}
/**
* 根据上一级的表达式得到当前表单式
* @param preString 上一级表达式
*/
public static void getByPreArr(StringBuffer preString){
String [] pre1Arr =preString.toString().split("=");
preString.delete(0, preString.length());
for(int i=0,len=pre1Arr.length;i<len;i++) {
String[] pre2Arr = pre1Arr[i].split("[+]");
int point=0;//出现的位置
for(int j=0,len2=pre2Arr.length;j<len2;j++) {
int temp = Integer.parseInt(pre2Arr[j]);
String pString = pre1Arr[i].substring(0,point);
String nString = pre1Arr[i].substring(point+pre2Arr[j].length());
point+=pre2Arr[j].length()+1;//多一个加号的位置
if(j>0&&temp==Integer.parseInt(pre2Arr[j-1])) continue;
/**
* 我写的算法不够完美，没有过滤掉结果完全相同的表达式。所以这里需要检查一下
*/
if(preString.toString().indexOf("="+pString+(temp+1)+nString+"=")==-1){
preString.append(pString+(temp+1)+nString+"=");
}
}
}
preString.append(pre1Arr[pre1Arr.length-1]+"+1");
}
public static void main(String[] a){
splitNumber(6);
}
}
* 递归，将上一个数字拆解的情况做一个二维数字
比喻3=2+1=2+1+1 可以存储为int[][] arr
arr[0]={3]
arr[1]={2，1}
arr[2]={1，1，1}
* @author peter.e.king
*
*/
public class SplitNumber {
public static void splitNumber(int x){
if(x<1){
System.out.println("请输入自然数！");
} else if (x==1){
System.out.println("数字『1』可以分解成的组合数为："+1);
System.out.println("数字『1』可以分解成的表达式为：1");
}else {
StringBuffer showStr = new StringBuffer("1");
for(int i=2;i<=x;i++){
getByPreArr(showStr);
}
System.out.println("数字『"+x+"』可以分解成的组合数为："+showStr.toString().split("=").length);
System.out.println("数字『"+x+"』可以分解成的表达式为："+showStr.toString());
}
}
/**
* 根据上一级的表达式得到当前表单式
* @param preString 上一级表达式
*/
public static void getByPreArr(StringBuffer preString){
String [] pre1Arr =preString.toString().split("=");
preString.delete(0, preString.length());
for(int i=0,len=pre1Arr.length;i<len;i++) {
String[] pre2Arr = pre1Arr[i].split("[+]");
int point=0;//出现的位置
for(int j=0,len2=pre2Arr.length;j<len2;j++) {
int temp = Integer.parseInt(pre2Arr[j]);
String pString = pre1Arr[i].substring(0,point);
String nString = pre1Arr[i].substring(point+pre2Arr[j].length());
point+=pre2Arr[j].length()+1;//多一个加号的位置
if(j>0&&temp==Integer.parseInt(pre2Arr[j-1])) continue;
/**
* 我写的算法不够完美，没有过滤掉结果完全相同的表达式。所以这里需要检查一下
*/
if(preString.toString().indexOf("="+pString+(temp+1)+nString+"=")==-1){
preString.append(pString+(temp+1)+nString+"=");
}
}
}
preString.append(pre1Arr[pre1Arr.length-1]+"+1");
}
public static void main(String[] a){
splitNumber(6);
}
}
10 楼
buptwhisper
2011-03-18
ggzwtj 写道
buptwhisper 写道
这个可以用一个递归来实现，对于任意的整数n,记拆解方式为g, 且作以下假设：
1).最后一个拆数是1，则拆解方式为 g(n-1) + 1，这个+1表示在g(n-1)的末尾加上一个1
2).最后一个拆数是2，则拆解方式为 g(n-2) + 2.依次类推，直到最后一个拆解数为
n-1。
这样就完成了拆解，不过复杂度比较高，可以试着改善一下。
1).最后一个拆数是1，则拆解方式为 g(n-1) + 1，这个+1表示在g(n-1)的末尾加上一个1
2).最后一个拆数是2，则拆解方式为 g(n-2) + 2.依次类推，直到最后一个拆解数为
n-1。
这样就完成了拆解，不过复杂度比较高，可以试着改善一下。
g(n-2) + 2是什么意思？g(n)表示的是最后的结果吗？
是的。
9 楼
nianien
2011-03-18
就是走楼梯算法:
给定n阶楼梯，可以一次跨1阶、2阶……k阶(k<=n,问共有多少走法，并记录每种走法
递归公式: f(n) = f(n-1) + f(n-2) + f(n-3)+……+f(n-k) n>=1
private void climb(int n, int step,List<int> steps)
{
if (step > n)
return;
steps.Add(step);
if (n == step)
{
//当剩余楼梯的阶数等于第一步所跨的阶数
//则到达最后一阶楼梯，此时为其中一种走法
//记录每次走法
this.count++;
print(steps);
}
else
{
//如果没有达到最后一层，则递归剩余楼梯的走法
//此时，第一可跨最大阶数由允许所跨最大阶数和剩余楼梯阶数的较小值决定
for (int i = 1; i <= stemp&& i <= n - step; i++)
{
//递归剩余楼梯第一步的每种走法
climb(n - step, i);
//退出递归时，清除剩余楼梯的走法
//以记录新的走法
list.RemoveAt(list.Count - 1);
}
}
}
测试结果 :n=5,step=5时,共有16种走法：
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
这是考虑顺序的,你上面的就更简单了,不考虑顺序,放进set对象里过滤一下就可以了
给定n阶楼梯，可以一次跨1阶、2阶……k阶(k<=n,问共有多少走法，并记录每种走法
递归公式: f(n) = f(n-1) + f(n-2) + f(n-3)+……+f(n-k) n>=1
private void climb(int n, int step,List<int> steps)
{
if (step > n)
return;
steps.Add(step);
if (n == step)
{
//当剩余楼梯的阶数等于第一步所跨的阶数
//则到达最后一阶楼梯，此时为其中一种走法
//记录每次走法
this.count++;
print(steps);
}
else
{
//如果没有达到最后一层，则递归剩余楼梯的走法
//此时，第一可跨最大阶数由允许所跨最大阶数和剩余楼梯阶数的较小值决定
for (int i = 1; i <= stemp&& i <= n - step; i++)
{
//递归剩余楼梯第一步的每种走法
climb(n - step, i);
//退出递归时，清除剩余楼梯的走法
//以记录新的走法
list.RemoveAt(list.Count - 1);
}
}
}
测试结果 :n=5,step=5时,共有16种走法：
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
这是考虑顺序的,你上面的就更简单了,不考虑顺序,放进set对象里过滤一下就可以了
8 楼
ggzwtj
2011-03-18
buptwhisper 写道
这个可以用一个递归来实现，对于任意的整数n,记拆解方式为g, 且作以下假设：
1).最后一个拆数是1，则拆解方式为 g(n-1) + 1，这个+1表示在g(n-1)的末尾加上一个1
2).最后一个拆数是2，则拆解方式为 g(n-2) + 2.依次类推，直到最后一个拆解数为
n-1。
这样就完成了拆解，不过复杂度比较高，可以试着改善一下。
1).最后一个拆数是1，则拆解方式为 g(n-1) + 1，这个+1表示在g(n-1)的末尾加上一个1
2).最后一个拆数是2，则拆解方式为 g(n-2) + 2.依次类推，直到最后一个拆解数为
n-1。
这样就完成了拆解，不过复杂度比较高，可以试着改善一下。
g(n-2) + 2是什么意思？g(n)表示的是最后的结果吗？
7 楼
ggzwtj
2011-03-18
buptwhisper 写道
再考虑一下这种想法：
最少拆解出只有一个加数的，最多拆出有n个加数。
假设已成功拆出有加数为m个的，现在考虑拆出m+1个的情况，即是可以看成是把已经成功拆出的m个中的某一个拆成两个，且如果这m个中有存在至少两个相等，只需要拆出其中一个为两个就行了。直到到最后的n个加数，对于把一个数拆成两个数的方式，这个很简单。这个方案也应该是可行的。
最少拆解出只有一个加数的，最多拆出有n个加数。
假设已成功拆出有加数为m个的，现在考虑拆出m+1个的情况，即是可以看成是把已经成功拆出的m个中的某一个拆成两个，且如果这m个中有存在至少两个相等，只需要拆出其中一个为两个就行了。直到到最后的n个加数，对于把一个数拆成两个数的方式，这个很简单。这个方案也应该是可行的。
如果从拆出的数量来控制状态还是比较麻烦的，不如用拆出来的值中的最大值来控制。
6 楼
ggzwtj
2011-03-18
这个可以用动态规划来做：
状态：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：过程中要小心数组越界（要是有代码需求我帮你写哈 ）
状态：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：过程中要小心数组越界（要是有代码需求我帮你写哈
）
5 楼
buptwhisper
2011-03-18
再考虑一下这种想法：
最少拆解出只有一个加数的，最多拆出有n个加数。
假设已成功拆出有加数为m个的，现在考虑拆出m+1个的情况，即是可以看成是把已经成功拆出的m个中的某一个拆成两个，且如果这m个中有存在至少两个相等，只需要拆出其中一个为两个就行了。直到到最后的n个加数，对于把一个数拆成两个数的方式，这个很简单。这个方案也应该是可行的。
最少拆解出只有一个加数的，最多拆出有n个加数。
假设已成功拆出有加数为m个的，现在考虑拆出m+1个的情况，即是可以看成是把已经成功拆出的m个中的某一个拆成两个，且如果这m个中有存在至少两个相等，只需要拆出其中一个为两个就行了。直到到最后的n个加数，对于把一个数拆成两个数的方式，这个很简单。这个方案也应该是可行的。
4 楼
buptwhisper
2011-03-18
不考虑顺序问题，也可以改用组合方式，如下：
对于n = 1 + 1 + 1 + 1 + ... + 1这列组合加数，其中的 + 取任意个（大于等于1个），即从n-1个加号中任意取出m个 1<=m<=n-1,这就对应着一个拆数
所以拆数就是2^(n-1) - 1种。
对于n = 1 + 1 + 1 + 1 + ... + 1这列组合加数，其中的 + 取任意个（大于等于1个），即从n-1个加号中任意取出m个 1<=m<=n-1,这就对应着一个拆数
所以拆数就是2^(n-1) - 1种。
发表评论
-
每日一篇
2013-12-24 10:27 552// 001.cpp : 定义控制台应用程序的入口 ... -
如何将java中负数转化为无符号类型32位的，与c中执行的结果不一样，请高手指点
2010-12-24 21:51 3123下面分别是两段java和c当中的代码，其中java代码是从c中 ... -
数据结构线性表顺序存储操作
2010-06-06 12:43 1641头文件： //********************** ... -
修改内存地址内容，可以修改游戏金币值
2010-04-04 15:16 5105实现修改内存内容核心代码： //进程列表信息 void ... -
输入一个数n，求出n的3次冥等于n个奇数
2010-02-25 01:59 1212#include <stdio.h> #in ... -
十进制转二进制
2009-11-02 23:44 1498好久没用java写了，真有点别扭。。。。。。。。。 pac ... -
c++实现的括号匹配，通过链栈方式
2009-06-24 22:54 2297/* 表达式中的括号是否匹配 */ bool C ... -
7道c练习题
2009-04-28 21:15 1203花了我将近两个小时的时间。。。。。。。。。 /* aut ... -
c++ 随机数rand()必须结合srand(time(NULL))
2009-04-16 00:11 8782引用 在c++中，使用c++ rand()获取随机数必须结合s ...
相关推荐
以和府捞面为例，拆解数字化【会员策略】.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
UT56优利德UT56数字万用表原理图
战略拆解核心会议（58页 PPT）.pptx
一端是对数字I/O隔离和保护所用的理想技术的争论，另一端则处于更高的架构层次，是对基于PLC的控制好还是基于PC/嵌入式计算机的控制好的争论。 鉴于工厂、工业和制造自动化的重要性越来越高，我们终于找到...