重大难题,算法牛人进来!!!!!!

Question

/*
 * 一个数m分成n组数有多少种f(m,n)
 * (网易笔试题)
 */#include<stdio.h>static int num=0;void main()
{
void divide(int,int,int,int); int m=10;
int n=4;
int count=0;
int sum=0; divide(m,n,count,sum); printf("num=%d\n",num);
}void divide(int m,int n,int count,int sum)
{
if(n==count)
{
if(m==sum)
{
num++;
}
}
else
{
for(int i=1;i<=m-n+1;i++)
{
sum+=i;
count++;
divide(m,n,count,sum);
sum-=i;
count--;
}
}
}
我出现的问题是 例如当m=10 n=4时 采用上序算法 1,2,3,4     4,2,1,3都是其解,但是我应该过滤掉重复的解,而它不是一个数字,是一个集合,请问该如何处理? 我采用的是C语言 所以请不要用容器类辅助解决

Answer 1

发到c区吧，不用现成的容器java很不好搞的。

Answer 2

int m =10;
int n=4;
for(int i=1;i<=m-n+1;i++){
for(int j=i;j<=m-n-i+2;j++){
for(int k=j;k<=m-n-i-j+3;k++){
int num =10-i-j-k;
if(num>=k){
System.out.println(m+"="+i+"+"+j+"+"+k+"+"+num);
}
}
}
}
输出结果：
10=1+1+1+7
10=1+1+2+6
10=1+1+3+5
10=1+1+4+4
10=1+2+2+5
10=1+2+3+4
10=1+3+3+3
10=2+2+2+4
10=2+2+3+3

Answer 3

对你的代码改了一下，仅仅求数量还是可以实现的，如果想求所有的排列就无能为力了
#include<stdio.h>static int num=0;void main()
{
void divide(int,int,int,int,int);int m=10;
int n=4;
int count=0;
int sum=0;
int startId=1;divide(startId,m,n,count,sum);printf("num=%d\n",num);
}void divide(int startId,int m,int n,int count,int sum)
{
if(n==count)
{
if(m==sum)
{
num++;
}
}
else
{
for(int i=startId;i<=m-n+1;i++)
{
sum+=i;
count++;
divide(i,m,n,count,sum);
sum-=i;
count--;
}
}
}输出结果：9
思路：在递归函数中加一个变量，要求下一次递归的起始位置比上一个数字大

Answer 4

/**
 * 把当前num切分成两个数据之和(A+B),且满足A不小于B。
 * @param num 当前切分的数据
 * @param splited 存储切分后的数据
 */
public void division(int num, int[] splited){

int[] temp=new int[splited.length+1];
System.arraycopy(splited,0,temp,1,splited.length); 

//比如当前num=10，则切分成9+1，并将后面的数据B=1存储进切分数组中用于下一次显示
//而前面的数据A=9在下一次切分时还需要分开，因此就不存储在切分数组中了
for(int i=num-1; i>=1;i--){
//保证A不小于B，且B不小于上一次切分的B
if(i<num-i||(num-i)<splited[0]) break;  
temp[0]=(num-i);
println(i,temp);
division(i,temp);
}


}
//打印
public void println(int i, int[] temp){
String s=i+"";
for(int j=0;j<temp.length;j++)
s=s+"+"+temp[j];
System.out.println(s);
}
        //测试
        division(10,new int[1]);

Answer 5

再给你修改下#include<stdio.h>static int num=0;
static int s = 10;
void main()
{
void divide(int,int,int,int);

int m=s;
int n=4;
int count=0;
int sum=0;
int startId=1;

divide(startId,m,n,sum);

printf("num=%d\n",num);
}void divide(int startId,int m,int n,int sum)
{
if(n==1)
{
if(sum==(s-m) &&  m >= startId)
{
num++;
}
}
else
{
for(int i=startId;i<=m-n+1;i++)
{
sum+=i;
divide(i,m-i,n-1,sum);
sum-=i;
}
}
}