2005年7月18日 第28期电脑报 编程点将

上周的电脑报不知怎么回事竟然没有编程点将。可不是我忘记做了哦。

题目：已知五个互不相同的正整数之和为23，且从这五个数中挑选若干个加起来可以表示从1到23之内的全部自然数。问这五个数是什么？

这题在我的C程序设计百例的第73题，我做的结果和里面的不一样。我现在还不知道是不是我错的。我的程序并不是很简便，主要问题是验证能否组合出1到23数的那个函数上面，我现在还没有找到简便的解决方法。请给意见和建议。
我的程序：
/*算法：因为五个数互不相同且之和为23，故其中最大值不会超过13，
又因为要表示1到23之内的自然数，故必含有1和2（否则1和2无法组合出来），
因此可以假设五个数从小到大分别为：1，2，i(3－11之间),j(i+1－12之间),k(j+1—13之间).循环取得范围之内的所有可能的值，当1+2+i+j+k==23时，调用函数AA(int i,int j,int k)判断是否可以组合出1到23之内的全部自然数,是则输出。
使用C++编程，在VC++6.0中通过运行。
结果是：
第1组:1,2,3,5,12
第2组:1,2,3,6,11
第3组:1,2,3,7,10
第4组:1,2,4,5,11
第5组:1,2,4,6,10
第6组:1,2,4,7,9
*
#include<iostream>
using namespace std;
bool AA(int i,int j,int k);//函数原型，用来验证是不是可以组合出1——23的值
void main()
{    int i,j,k,count=0;
    bool a=false;

    for(i=3;i<=11;i++)
        for(j=i+1;j<=12;j++)
            for(k=j+1;k<=13;k++)
            {
                if(1+2+i+j+k==23)
                    a=AA(i,j,k);
                if(a==true)
                {
                    count++;
                    cout<<"第"<<count<<"组:"<<1<<","<<2<<","
                        <<i<<","<<j<<","<<k<<endl;
                    a=false;//重新初始化
                }
            }

}

/*今天对这个组合算法重新想了一下，找出了一种自己的解法，这种解法的时间复杂度是指数级的，感觉也不是太好，但是是一种通用的算法，而且对于数值低的组合看起来很明了，虽然我希望找到一种更好的算法。

下面是改进的组合函数的程序（加上上面的主函数就是一个完整的程序，从这个程序中我看到以前自己做的是错的（虽然是一个一个算仍然错^_^））。

*/
bool AA(int i,int j,int k)
{
    int ii,jj,n,BB[24],CC[]={1,2,i,j,k};
    for(n=0;n<24;n++)
        BB[n]=0;
    
    //对所有组合验证，若出现所组合的值则另相应的数组为1
    //先组合一个数、四个数和五个数
    BB[1+2+i+j+k]=1;
    for(ii=0;ii<5;ii++)
    {
        BB[CC[ii]]=1;
        BB[23-CC[ii]]=1;
    }

    //组合两个数和三个数
    for(ii=0;ii<5;ii++)
        for(jj=0;jj<5;jj++)
            if(ii!=jj)
            {
                BB[CC[ii]+CC[jj]]=1;
                BB[23-CC[ii]-CC[jj]]=1;
            }


    for(n=4;n<24;n++)
        if(BB[n]==0)return false;

        return true;
}

以前那个函数是错的，这里就给删除了bool AA(int i,int j,int k)

    这道题我的原来的程序是有错误的，主要在那个组合的部分，我现在已经找到了一种通用的组合的算法，不过复杂度太大，希望以后有更好的方法。这期获奖程序网址是：www.cpcw.com/xz/28qihuojiang.rar，解法很一般的，这种做法不通用，大家可以再结合我c语言程序百例里面的解法学习。

评论