|
锁定老帖子 主题：拆解数字
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-03-18
Excalibur 写道 ggzwtj 写道 悲催啊，要输出所有结果，再怎么弄都是浮云，快不起来了。200的分解方法应该是3972999029388种吧。。。。
我算到40就eclipse就挂了…… 我的57还能抗住，58就OutOfMemoryError了。谁能帮我把我的递归修成循环啊  ，探索中...
|
| 返回顶楼 | |
|
发表时间：2011-03-18
dongya1987 写道 Excalibur 写道 ggzwtj 写道 悲催啊，要输出所有结果，再怎么弄都是浮云，快不起来了。200的分解方法应该是3972999029388种吧。。。。
我算到40就eclipse就挂了…… 我的57还能抗住，58就OutOfMemoryError了。谁能帮我把我的递归修成循环啊 ，探索中...
你的速度如何？ |
| 返回顶楼 | |
|
发表时间：2011-03-18
Excalibur 写道 ggzwtj 写道 悲催啊，要输出所有结果，再怎么弄都是浮云，快不起来了。200的分解方法应该是3972999029388种吧。。。。
我算到40就eclipse就挂了…… 不至于吧，40的时候只有37338种分解。 |
| 返回顶楼 | |
|
发表时间：2011-03-18
好吧，我觉得如果非得输出所有的情况反而使得问题变得简单，因为我们没有必要考虑优化了。下面是代码：
import java.math.BigInteger; import java.util.Scanner; /** * @author tianchi.gzt * * 求数字n的拆分的方法的总数（不考虑顺序） */ public class test{ static int[] a = new int[100]; static int result = 0; public static void show(int n, int m, int big){ if(n == 0){ result++; System.out.print("= " +a[0]); for(int i = 1; i < m; i++){ System.out.print(" + " + a[i]); } System.out.println(); } int i; if(n > big){ i = big; }else{ i = n; } for(; i > 0; i--){ a[m] = i; show(n-i, m+1, i); } } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); while(true){ result = 0; int tmp = scanner.nextInt(); System.out.println(tmp); show(tmp, 0, tmp); System.out.println(result); } } } 这里说明一下啊，如果是非得输出的话，肯定是非常慢的，有那么多要输出的东西。如果把输出的部分去掉的话，速度还是很快的。 |
| 返回顶楼 | |
|
发表时间：2011-03-18
import java.math.BigInteger;
import java.util.Scanner; /** * @author tianchi.gzt * * 求数字n的拆分的方法的总数（不考虑顺序） */ public class test{ static int[] a = new int[100]; static int result = 0; public static void show(int n, int m, int big){ if(n == 0){ result++; System.out.print("= " +a[0]); for(int i = 1; i < m; i++){ System.out.print(" + " + a[i]); } System.out.println(); } int i; if(n > big){ i = big; }else{ i = n; } for(; i > 0; i--){ a[m] = i; show(n-i, m+1, i); } } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); while(true){ result = 0; int tmp = scanner.nextInt(); System.out.println(tmp); show(tmp, 0, tmp); System.out.println(result); } } } |
| 返回顶楼 | |
|
发表时间：2011-03-18
输出的话在50以内不是非常慢，不输出的话在90以内不是非常慢
|
| 返回顶楼 | |
|
发表时间：2011-03-20
最后修改：2011-03-24
#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;
}
|
| 返回顶楼 | |
|
发表时间：2011-03-21
ccjsjymg 写道
LONG f(int x, int y
#ifdef PRINT_RESULT
, int print
#endif
)
...
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;
}
学习了，原来宏还可以这么用 |
| 返回顶楼 | |
|
发表时间：2011-03-22
ggzwtj 写道 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：过程中要小心数组越界（要是有代码需求我帮你写哈  ） 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()); } } } 现在补充代码，测试过了，可以算出来，可以看出具体的分法的大概。:) 休息吧。。。 顶,最喜欢动态规划了,虽然不太熟 |
| 返回顶楼 | |
|
发表时间：2011-03-22
buptwhisper 写道 不考虑顺序问题，也可以改用组合方式，如下：
对于n = 1 + 1 + 1 + 1 + ... + 1这列组合加数，其中的 + 取任意个（大于等于1个），即从n-1个加号中任意取出m个 1<=m<=n-1,这就对应着一个拆数 所以拆数就是2^(n-1) - 1种。 这个会重复很多吧```` |
| 返回顶楼 | |
