Algorithm 版 (精华区)

发信人: yahoo (yahoo), 信区: Algorithm
标  题: Re: 请ACM队员做一下这个题...
发信站: 哈工大紫丁香 (2001年08月07日10:48:38 星期二), 站内信件

一个比较快的枚举方法，可以得到每个拆分方法,如果不显示拆分结果会快很多。
#include "stdio.h"
int m=0,n;
out(int* path)
{
    printf("%d=",n);
    for(int i=0;i<n;i++)
    {
        if(path[i]==0)
            break;
        printf("%d+",path[i]);
    }
    printf("\b \n");
    return 0;
}
search(int* path,int pos,int left,int prv)
{
    int i;
    if(left==0)
    {
        m++;
        out(path);
        return 0;
    }
    for(i=prv>left?left:prv;i>0;i--)
    {   
        path[pos]=i;
        search(path,pos+1,left-i,i);
    }
    return 0;
}
main(void)
{
    int i;
    scanf("%d",&n);
    int* path=new int[n*sizeof(int)];
    for(i=0;i<n;i++) *(path+i)=0;
    search(path,0,n,n);
    printf("Total:%d\n",m);
    return 0;
}


【 在 sino (茶水先生) 的大作中提到: 】
: 整数拆分：将一个正整数n,拆分成一组小于n的正整数的和（不考虑排列）。求
:     共有多少组可能的拆分。
: 请谈谈思路。


--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.226.245]
※ 修改:·yahoo 於 08月07日10:50:46 修改本文·[FROM: 202.118.226.245]