| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:谁能告诉我怎么样除去重复的In Reply To:谁能告诉我怎么样除去重复的 Posted by:6233843 at 2006-07-17 18:13:52 #include <iostream>
#include <fstream>
using namespace std;
int sum;
int sticknum;
int stick[20];
int mark[20];
int solution;
int sols[100][20]; //记录不重复的答案
int slen[100]; //记录第j组答案的长度
int solnum; //记录不重复的答案的数量
void compute(int start,int cursum){
for(int i=start;i<sticknum;i++){
if(mark[i]==0&&stick[i]<=cursum){
mark[i]=1;
int tmp=cursum-stick[i];
if(tmp==0){
int tt=0;
for(int j=0;j<sticknum;j++){
if(mark[j]==1){
sols[solnum][tt++]=stick[j];
}
}
if(solution==0){ //如果是第一组答案,就直接记录
slen[solnum]=tt;
solution++;
solnum++;
mark[i]=0;
}else{
bool test=false;
for(int k=0;k<solnum&&!test;k++){ //判断答案是否重复,如果重复就不对solnum加1,否则加1,
if(slen[k]==tt){ //先判断这两组组答案的长度是否相等,不等就直接判断下一组。
for(int m=0;m<tt;m++){
if(sols[k][m]!=sols[solnum][m]){
break;
}
}
if(m==tt)test=true; //表示答案完全匹配,这一组答案就可以舍掉了
}
}
if(!test){ //如果答案与前面的都不重复,就对solution+1,solnum+1,
solution++;
slen[solnum]=tt;
solnum++;
}
}
}else{
compute(i+1,tmp);
}
mark[i]=0;
}
}
}
void main(){
// ifstream cin("data.txt");
while(1){
cin>>sum>>sticknum;
if(sum==0)break;
memset(stick,0,sizeof(stick));
memset(mark,0,sizeof(mark));
memset(sols,0,sizeof(sols));
memset(slen,0,sizeof(slen));
solution=0;
solnum=0;
for(int i=0;i<sticknum;i++){
cin>>stick[i];
}
cout<<"Sums of "<<sum<<":"<<endl;
compute(0,sum);
if(solution==0){
cout<<"NONE"<<endl;
}else{
for(int i=0;i<solnum;i++){
for(int j=0;j<slen[i]-1;j++)
cout<<sols[i][j]<<"+";
cout<<sols[i][j]<<endl;
}
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator