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语言程序百例里面的解法学习。
评论