打印一个整数划分全部方案,该怎么解决

2013-01-25

打印一个整数划分全部方案整数划分就是将一个正整数表示成一系列正整数之和例如整数6可以划分成一下11中

打印一个整数划分全部方案
整数划分就是将一个正整数表示成一系列正整数之和例如整数6可以划分成一下11中方案：
        6
        5 + 1
        4 + 2, 4 + 1 + 1
        3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
        2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
        1 + 1 + 1 + 1 + 1 + 1

半成品代码：
public class Main
{
static int sum=0;
static int t[]=new int[10];
static void dfs(int n,int m)
{
if(sum==m)
{
//Arrays.sort(t,1,n-1);
System.out.print(m+"=    ");
for(int k=1;k<=n-1;k++)
System.out.print(t[k]);
System.out.println();
}
else
{
for(int i=1;i<=m;i++)//for(int i=m;i>=1;i--)
{
sum+=i;
if(sum<=m)
{
t[n]=i;
dfs(n+1,m);
sum-=i;
}else
{sum-=i;
return;
}
}
}
}
public static void main(String args[])
{
dfs(1,6);
}
}
正常打印：
6=    111111
6=    11112
6=    11121
6=    1113
6=    11211
6=    1122
6=    1131
6=    114
6=    12111
6=    1212
6=    1221
6=    123
6=    1311
6=    132
6=    141
6=    15....
但是去掉第一个注释想排下序
就打印这样的了：
........
6=    15
6=    11121
6=    1112
6=    1121
6=    113
6=    1121
6=    112
6=    131
6=    14
6=    1131
6=    112
6=    121
6=    13
6=    141
6=    12
6=    51
6=    6
很奇怪但是不知道什么原因。
我把第二行注释也去掉上面的for加上注释，却只打印一行：
6=    6

本来打算排好序，去掉相同的方案，现在出了这个问题，大家帮个忙，代码不长。
[解决办法]

引用:

C/C++ code
#include <stdio.h>

   int split(int n, int m)
   {
      if(n < 1
[解决办法]
m < 1) return 0;
      if(n == 1
[解决办法]
m == 1) return 1;
      if(n < m) return split(n, n);
      if(n == m) return (sp……

这个求的是划分方案个数吧。lZ问的是打印方案。

public class Main 
 
{
static int sum=0,num=0;
static int t[]=new int[121];
static void dfs(int n,int m)
{
if(sum==m)
{
System.out.print(m+"=");
for(int k=1;k<n-1;k++)
System.out.print(t[k]+"+");
System.out.println(t[n-1]);
num++;
}
else
{
for(int i=m-n+1;i>=1;i--)
{
sum+=i;
if(sum<=m)
{
if(i<=t[n-1])
{
t[n]=i;
dfs(n+1,m);
}
}
sum-=i;
}
}
}
public static void main(String args[])
{
Scanner cin=new Scanner(System.in);
while(cin.hasNext())
{
int n=cin.nextInt();
t[0]=120;
dfs(1,n);
System.out.println("一共有"+num+"方案.");
num=0;
}
}
}
6
6=6
6=5+1
6=4+2
6=4+1+1
6=3+3
6=3+2+1
6=3+1+1+1
6=2+2+2
6=2+2+1+1
6=2+1+1+1+1
6=1+1+1+1+1+1
一共有11方案.

热点排行

软件架构设计

打印一个整数划分全部方案,该怎么解决