ccjsjymg
- 浏览: 63243 次
- 性别:
- 来自: 北京
-
最新评论
将任一个数字进行拆解，例如： 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 619// 001.cpp : 定义控制台应用程序的入口 ... -
如何将java中负数转化为无符号类型32位的，与c中执行的结果不一样，请高手指点
2010-12-24 21:51 3171下面分别是两段java和c当中的代码，其中java代码是从c中 ... -
数据结构线性表顺序存储操作
2010-06-06 12:43 1700头文件： //********************** ... -
修改内存地址内容，可以修改游戏金币值
2010-04-04 15:16 5167实现修改内存内容核心代码： //进程列表信息 void ... -
输入一个数n，求出n的3次冥等于n个奇数
2010-02-25 01:59 1264#include <stdio.h> #in ... -
十进制转二进制
2009-11-02 23:44 1548好久没用java写了，真有点别扭。。。。。。。。。 pac ... -
c++实现的括号匹配，通过链栈方式
2009-06-24 22:54 2340/* 表达式中的括号是否匹配 */ bool C ... -
7道c练习题
2009-04-28 21:15 1264花了我将近两个小时的时间。。。。。。。。。 /* aut ... -
c++ 随机数rand()必须结合srand(time(NULL))
2009-04-16 00:11 8832引用 在c++中，使用c++ rand()获取随机数必须结合s ...
相关推荐
以和府捞面为例，拆解数字化【会员策略】.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，可编程逻辑控制器）是一种用于自动化控制的电子设备，它采用可编程的存储器，用于其内部存储执行逻辑运算、顺序控制、定时、计数和算术运算等操作的指令，并通过数字或...
算法是解决特定问题或执行特定任务的一系列步骤或规则的有序集合。在计算机科学中，算法通常用来指导计算机执行特定的任务或解决问题。良好设计的算法能够有效地解决问题，并且在给定的输入下能够产生正确的输出。...