与えられた整数配列、与えられた整数値のすべてのサブセットを出力
2746 ワード
これは私が学校のフォーラムである同級生を見て、書いたツールです.しかし、当時、彼はpythonで書いたので、注釈や説明はなく、正直に言って、私は理解していませんでした.しかし、主な機能は、整数配列があり、それから数mがあり、整数配列の中で、すべての和がmに等しい組み合わせを見つけて出力することです.
例えば配列{1,5,3,7,6,4,2},m=7,
出力:1 6
3 4
7
1 2 4
2 5
このことは長い間考えていた.そして昨日の100-21のテーマをしていたとき、突然これに似ているような気がして、それから私は考えに沿って(具体的な考えは100-21を見ることができます)方法を見つけましたが、コードは複雑で、効率が悪いです.何かもっと最適化する方法があるのか分からない.
コードはやはり貼り付けましょう.
例えば配列{1,5,3,7,6,4,2},m=7,
出力:1 6
3 4
7
1 2 4
2 5
このことは長い間考えていた.そして昨日の100-21のテーマをしていたとき、突然これに似ているような気がして、それから私は考えに沿って(具体的な考えは100-21を見ることができます)方法を見つけましたが、コードは複雑で、効率が悪いです.何かもっと最適化する方法があるのか分からない.
コードはやはり貼り付けましょう.
/*==========================================*\
, 。
, python , ,
, 。 , ,
m, , m
, 。
{1,5,3,7,6,4,2},m = 7,
:1 6
3 4
7
1 2 4
2 5
\*==========================================*/
#include <iostream>
#include <vector>
using namespace std;
//
int partition(int *index,int begin,int end){
int i = begin;
int j = end;
int temp;
while(i<j){
while(index[i]<index[j]){
--j;
}
if(i<j){
temp = index[i];
index[i] = index[j];
index[j] = temp;
}
while(index[i]<index[j]){
++i;
}
if(i<j){
temp = index[i];
index[i] = index[j];
index[j] = temp;
}
}
return i;
}
void quickSort(int *index,int begin,int end){
if(begin < end){
int q = partition(index,begin,end);
quickSort(index,begin,q-1);
quickSort(index,q+1,end);
}
}
int binaryFind(int *index,int length,int n){//
int i = 0;
int j = length -1;
while(i <= j){
int pIndex = (i+j)/2;
if(index[pIndex] > n){
j = pIndex - 1;
}else if(index[pIndex] < n){
i = pIndex + 1;
}else if(index[pIndex] == n){
return pIndex;//
}
}
return -1;// -1
}
bool FindSum(int sum, int *index , int pIndex , vector<int> &vresult)
{
bool ret = false;
if (sum<=0||pIndex<0)
return ret;
if (sum<=index[pIndex]){
int flag = binaryFind(index,pIndex+1,sum);
if(flag >= 0){
pIndex = flag;
vresult.push_back(index[pIndex]);
for (int i=vresult.size()-1;i>=0;i--){
cout<<vresult[i]<<" ";
}
cout<<endl;
vresult.pop_back();
ret = true;
}
}
vresult.push_back(index[pIndex]);
bool res1=FindSum(sum-index[pIndex],index, pIndex-1, vresult);
vresult.pop_back();
//cout << "index : " << index[pIndex] << endl;
bool res2=FindSum(sum,index, pIndex-1,vresult);
return res1||res2||ret;
}
void Find(int sum, int *index,int length)
{
vector<int> vresult;
quickSort(index,0,length-1);// , , 100-21
if(!FindSum(sum,index, length-1 , vresult))
cout<<" can't get "<<sum<<endl;
}
int main(){
int index[] ={1,5,7,6,2,100};
Find(7,index,sizeof(index)/sizeof(int));
return 1;
}