一个老题将正整数n分为若干num个不同的正整数之和

/*

http://www.newsmth.net/bbstcon.php?board=Algorithm&gid=33809 

发信人: firebugP (firefox), 信区: Algorithm
标  题: 一个老题
发信站: 水木社区 (Tue Nov  3 00:50:48 2009), 站内

将正整数n分为若干num个不同的正整数之和，给出所有可能的拆分结果（数字相同而顺序不同
的结果视为同一条结果，例如6=1+2+3和6=3+2+1是一回事，而6=2+4和6=1+5是符合条件
的结果）
/

#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>

typedef std::set<int> Container;
Container res;
std::vector<Container> allRes;

void printAll()
{
    for(int i=0; i<allRes.size(); i++)
    {
        for(Container::iterator it=allRes[i].begin(), end=allRes[i].end();
            it!=end; ++it)
        {
            printf(“%d “, *it);
        }
        printf(“\n”);
    }
}

bool operator==(Container const &a,Container const &b)
{
    if(a.size()!=b.size())
        return false;

    for(Container::const_iterator ita=a.begin(), enda=a.end(),itb=b.begin();
            ita!=enda; ++ita, ++itb)
    {
            if(ita != itb )return false;
    }

    return true;
}

void add()
{
    if(allRes.end()!=std::find(allRes.begin(), allRes.end(),res))
        return;
    allRes.push_back(res);
}

//将正整数n分为num个不同的正整数之和
//将结果放到全局变量allRes中
void split(int n, int num)
{
    if(num(num+1)/2>n)    //无解
        return;
    
    //只有一个数,结束
    if(num==1)
    {
        if(res.find(n)==res.end())
        {
            res.insert(n);
            add();
            res.erase(n);
        }
        return;
    }

    //否则,遍历所有可能的
    for(int i=1; i<=n-(num-1)num/2; i++)
    {
        if(res.find(i)==res.end())
        {
            res.insert(i);
            //if(n-i>=(num-1)num/2)
            split(n-i,num-1);
            res.erase(i);
        }
    }
}

void main()
{
    split(16,3);
    printAll();
}

• 上一篇 一道笔试题 多字串查找
• 下一篇 Web dev framework.