33 选 7
程序如下, 没有用读文件的方法, 只是将vector中的数据类型设置为char, 这样就节省了3/4的空间符合 33 选 7 的题意的解仅有31组,程序运行完毕会生成一个 result.dat 文件。
我用学校给我的笔记本电脑运行, 运行时间大约为4分钟,没有超过5分钟
当然那台笔记本电脑的性能是很好的。
那台笔记本电脑的配置为:
Prozessor x86 Family 6 Model 13 Stepping 6 GenuineIntel 1600MHz
总共 real memory 512MB
可使用的 real memory 225.79MB
总共 virtuell memory 2.00GB
可使用的 virtuell memory 1.96GB
我本来想上传那个 exe 文件的,可惜没有成功,如果要,可以通过Email 发给你。
题目详情请见下面的连接
http://bbs.
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
class ChooseNums;
class Item
{
friend class ChooseNums;
private:
vector<char> item;
public:
Item(char c)
{
item.push_back(c);
}
vector<char> getMe()
{
return item;
}
bool add(char c)
{
if( find(item.begin(), item.end(), c) == item.end())
{
item.push_back(c);
return true;
}
return false;
}
void sortItem()
{
sort(item.begin(), item.end());
}
bool equals(const Item & i)
{
return equal(item.begin(), item.end(), i.item.begin());
}
void display()
{
for(int i = 0; i<item.size(); i++)
{
cout<<(int)item[i]<<" ";
}
cout<<endl;
}
};
class ChooseNums
{
private:
char * source;
int size;
int amount;
vector<Item> temp;
vector<Item> result;
public:
ChooseNums(int top, int amount)
{
size = top;
source = new char[size];
for(int i = 0; i<size; i++)
{
source[i] = (char)(i+1);
Item item(source[i]);
result.push_back(item);
}
this->amount = amount;
}
void addIntoTemp(Item & item)
{
bool alreadyExist = false;
for(int i = 0; i<temp.size(); i++)
{
if(item.equals((Item)temp[i]))
{
alreadyExist = true;
break;
}
}
if(!alreadyExist)
temp.push_back(item);
}
bool inclusive(const Item & it)
{
int cnt = 0;
bool included = false;
for(int i = 0; i<temp.size(); i++)
{
Item itemTemp = temp[i];
cnt = 0;
for(int j = 0; j<it.item.size(); j++)
{
char c = it.item[j];
for(int k = 0; k<itemTemp.item.size(); k++)
{
if(c == itemTemp.item[k])
cnt++;
if(cnt == 3)
{
included = true;
break;
}
}
if(included == true)
break;
}
if(included == true)
break;
}
return included;
}
void chooseNums()
{
for(int i = 0; i<amount-1; i++)
{
if(i>=2) //ab level 3
{
for(int j = 0; j<result.size(); j++)
{
// get a item from item
Item item = result[j];
// check whether it is already inclusive in
the temp vector
// if not inclusive
if(!inclusive(item))
{
// then we try add an new
element
for(int k = 0; k<size;
k++)
{
Item
tempItem = item;
if(tempItem.add(source[k]))
{
// we must check it again, whether there are
three
// same numbers
// if this is really a new item
if(!inclusive(tempItem))
{
// then we sort it
tempItem.sortItem();
// and add it into the temp
vector
addIntoTemp(tempItem);
break;
}
}
}
}
}
}
else
{
for(int j = 0; j<result.size(); j++)
{
Item item = result[j];
for(int k = 0; k<size; k++)
{
Item tempItem = item;
if(tempItem.add(source[k]))
{
tempItem.sortItem();
addIntoTemp(tempItem);
}
}
}
}
result = temp;
temp.clear();
}
}
void writeToFile(char * filename)
{
ofstream fout(filename);
if(!fout.is_open())
{
cerr<<"File Open Error\n";
exit(EXIT_FAILURE);
}
int sizeofResult = result.size();
for(int i = 0; i<sizeofResult; i++)
{
Item itemR = result[i];
vector<char> item = itemR.getMe();
for(int j = 0; j<item.size(); j++)
{
fout<<(int)(item[j])<<" ";
}
fout<<endl;
}
fout<<"There are total "<<sizeofResult<<" items"<<endl;
fout.clear();
fout.close();
}
~ChooseNums()
{
delete [] source;
size = 0;
amount = 0;
}
void displayResult()
{
for(int i =0; i<result.size(); i++)
{
Item item = result[i];
item.display();
}
}
};
int main()
{
// 如果设置参数为6 4 的话,只有3组解:<1 2 3 4> <1 2 5 6> <3 4 5 6>
ChooseNums cn(33, 7);
cn.chooseNums();
cn.displayResult();
cn.writeToFile("result.dat");
system("pause");
return 0;
}