| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1174 人关注过本帖
标题:做的出来我嫁给他
只看楼主 加入收藏
myajax95
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:30
帖 子:2978
专家分:0
注 册:2006-3-5
收藏
得分:0 

整整作了两个多小时,越写越乱,没作任何exception handling,程序混乱的一塌糊涂。凑合着看吧,排排序应该会快一些,不过已经很快乐。以后有时间再整理。

输入:
CCondition("ENG", "Red", "", "", ""),
CCondition("SWE", "", "Dog", "", ""),
CCondition("DAN", "", "", "Tea", ""),
CCondition("", "Green|White", "", "", "", CONDITION_TYPE_NEIGHBOR_LEFTATTR),
CCondition("", "Green", "", "Coffee", ""),
CCondition("", "", "Bird", "", "PaulMall"),
CCondition("", "Yellow", "", "", "DunHill"),
CCondition("", "", "", "Milk", "", CONDITION_TYPE_LOCATION, 2),
CCondition("NOR", "", "", "", "", CONDITION_TYPE_LOCATION, 0),
CCondition("", "", "Cat", "", "Mix", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition("", "", "Horse", "", "DunHill", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition("", "", "", "Beer", "BueMaster"),
CCondition("GER", "", "", "", "Prince"),
CCondition("NOR", "Blue", "", "", "", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition("", "", "", "Water", "Mix", CONDITION_TYPE_NEIGHBOR_DIFFATTR),

输出:
*********Posibility*************0
Nation=NOR, HouseColor=Yellow, Pet=Cat, Drink=Water, Cigarette=DunHill.
Nation=DAN, HouseColor=Blue, Pet=Horse, Drink=Tea, Cigarette=Mix.
Nation=ENG, HouseColor=Red, Pet=Bird, Drink=Milk, Cigarette=PaulMall.
Nation=GER, HouseColor=Green, Pet=, Drink=Coffee, Cigarette=Prince.
Nation=SWE, HouseColor=White, Pet=Dog, Drink=Beer, Cigarette=BueMaster.
Press any key to continue

程序代码:

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

enum CONDITION_TYPE
{
CONDITION_TYPE_NEIGHBOR_DIFFATTR = 0,
CONDITION_TYPE_EXACT,
CONDITION_TYPE_NEIGHBOR_LEFTATTR,
CONDITION_TYPE_LOCATION,
END_PLUS_ONE_CONDITION_TYPE
};

class CCondition
{
public:
CCondition(string sNation, string sHouseColor, string sPet, string sDrink, string sCigarette, int intType=CONDITION_TYPE_EXACT, int intLocation = -1)
: m_intType(intType), m_intLocation(intLocation)
{
m_sAttr[0]=sNation, m_sAttr[1]=sHouseColor, m_sAttr[2]=sPet, m_sAttr[3]=sDrink, m_sAttr[4]=sCigarette;
}
CCondition() : m_intType(-1), m_intLocation(-1) {}
void SeparateNeighbor(CCondition &cd1, CCondition &cd2);
void SeparateLeft(CCondition &cd1, CCondition &cd2);

private:
string m_sAttr[5];
int m_intType;
int m_intLocation;

friend class CApartment;
friend class CSolution;
};

void CCondition::SeparateNeighbor(CCondition &cd1, CCondition &cd2)
{
int intCount;
cd1 = *this;
cd2 = *this;
for (intCount = 0; intCount < 5; intCount++)
{
if (!m_sAttr[intCount].empty())
{
cd1.m_sAttr[intCount] = \"\";
break;
}
}
for (++intCount;intCount < 5; intCount++)
{
if (!m_sAttr[intCount].empty())
{
cd2.m_sAttr[intCount] = \"\";
break;
}
}
}

void CCondition::SeparateLeft(CCondition &cd1, CCondition &cd2)
{
int intCount, intPos;
cd1 = *this;
cd2 = *this;
for (intCount = 0; intCount < 5; intCount++)
{
if (!m_sAttr[intCount].empty() && (intPos = m_sAttr[intCount].find('|')) > 0)
{
cd1.m_sAttr[intCount].erase(intPos, cd1.m_sAttr[intCount].size());
cd2.m_sAttr[intCount].erase(0, intPos+1);
break;
}
}
}

class CApartment
{
public:
CApartment() {}
void Clear() {for (int intCount=0; intCount < 5; intCount++) m_sAttr[intCount]=\"\";}
bool IsComplete() {for (int intCount=0; intCount < 5; intCount++)
if (!m_sAttr[intCount].empty()) return false; return true;}
bool InsertCondition(CCondition &cd);
string ToString() const;
private:
string m_sAttr[5];
};

string CApartment::ToString() const
{
stringstream ssOutput;
ssOutput << \"Nation=\" << m_sAttr[0] << \", HouseColor=\" << m_sAttr[1] << \", Pet=\" << m_sAttr[2]
<< \", Drink=\" << m_sAttr[3] << \", Cigarette=\" << m_sAttr[4] << \".\" << endl;
return ssOutput.str();
};

bool CApartment::InsertCondition(CCondition &cd)
{
CApartment aptResult = *this;

for (int intCount = 0; intCount < 5; intCount++)
{
if (!m_sAttr[intCount].empty() && !cd.m_sAttr[intCount].empty()
&& m_sAttr[intCount] != cd.m_sAttr[intCount])
return false;
else if (!cd.m_sAttr[intCount].empty())
aptResult.m_sAttr[intCount] = cd.m_sAttr[intCount];
}

*this = aptResult;
return true;
};

ostream& operator << (ostream &o, const CApartment &apt)
{
return o << apt.ToString();
}


class CSolution
{
public:
bool IsComplete() {for (int intAptCount=0; intAptCount < 5; intAptCount++)
if (!m_apt[intAptCount].IsComplete()) return false; return true;}
void Clear() {for (int intAptCount=0; intAptCount < 5; intAptCount++) m_apt[intAptCount].Clear();}
int CSolution::InsertCondition(CCondition &cd, vector<CSolution> &vecSolution);
string ToString() const;
private:
CApartment m_apt[5];
};

string CSolution::ToString() const
{
stringstream ssOutput;
for (int intAptCount = 0; intAptCount < 5; intAptCount++)
ssOutput << m_apt[intAptCount].ToString();
return ssOutput.str();
}

int CSolution::InsertCondition(CCondition &cd, vector<CSolution> &vecSolution)
{
int intCount;
CCondition cd1, cd2;
CSolution sol;

switch (cd.m_intType)
{
case CONDITION_TYPE_EXACT:
for (intCount = 0; intCount < 5; intCount++)
{
sol = *this;
if (sol.m_apt[intCount].InsertCondition(cd))
vecSolution.push_back(sol);
}
break;
case CONDITION_TYPE_NEIGHBOR_DIFFATTR:
cd.SeparateNeighbor(cd1, cd2);
for (intCount = 0; intCount < 4; intCount++)
{
sol = *this;
if (sol.m_apt[intCount].InsertCondition(cd1) && sol.m_apt[intCount+1].InsertCondition(cd2))
vecSolution.push_back(sol);

sol = *this;
if (sol.m_apt[intCount].InsertCondition(cd2) && sol.m_apt[intCount+1].InsertCondition(cd1))
vecSolution.push_back(sol);
}
break;
case CONDITION_TYPE_NEIGHBOR_LEFTATTR:
cd.SeparateLeft(cd1, cd2);
for (intCount = 0; intCount < 4; intCount++)
{
sol = *this;
if (sol.m_apt[intCount].InsertCondition(cd1) && sol.m_apt[intCount+1].InsertCondition(cd2))
vecSolution.push_back(sol);
}
break;
case CONDITION_TYPE_LOCATION:
if (cd.m_intLocation < 0 || cd.m_intLocation >= 5)
break;
sol = *this;
if (sol.m_apt[cd.m_intLocation].InsertCondition(cd))
vecSolution.push_back(sol);
break;
default:
break;
}
return vecSolution.size();
}

ostream& operator << (ostream &o, const CSolution &sol)
{
return o << sol.ToString();
}

int main(int argc, char* argv[])
{ int intCount, intSource;

CCondition cdlist[] =
{
CCondition(\"ENG\", \"Red\", \"\", \"\", \"\"),
CCondition(\"SWE\", \"\", \"Dog\", \"\", \"\"),
CCondition(\"DAN\", \"\", \"\", \"Tea\", \"\"),
CCondition(\"\", \"Green|White\", \"\", \"\", \"\", CONDITION_TYPE_NEIGHBOR_LEFTATTR),
CCondition(\"\", \"Green\", \"\", \"Coffee\", \"\"),
CCondition(\"\", \"\", \"Bird\", \"\", \"PaulMall\"),
CCondition(\"\", \"Yellow\", \"\", \"\", \"DunHill\"),
CCondition(\"\", \"\", \"\", \"Milk\", \"\", CONDITION_TYPE_LOCATION, 2),
CCondition(\"NOR\", \"\", \"\", \"\", \"\", CONDITION_TYPE_LOCATION, 0),
CCondition(\"\", \"\", \"Cat\", \"\", \"Mix\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition(\"\", \"\", \"Horse\", \"\", \"DunHill\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition(\"\", \"\", \"\", \"Beer\", \"BueMaster\"),
CCondition(\"GER\", \"\", \"\", \"\", \"Prince\"),
CCondition(\"NOR\", \"Blue\", \"\", \"\", \"\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition(\"\", \"\", \"\", \"Water\", \"Mix\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
};
CSolution sol;
vector<CSolution> vecResult1, vecResult2, *pvecSource = &vecResult1, *pvecResult = &vecResult2, *pvecTmp = NULL;

pvecSource->push_back(sol);

for (intCount = 0; intCount < sizeof(cdlist)/sizeof(CCondition); intCount++)
{
for (intSource = 0; intSource < (*pvecSource).size(); intSource++)
(*pvecSource)[intSource].InsertCondition(cdlist[intCount], *pvecResult);
pvecSource->clear();
pvecTmp = pvecSource;
pvecSource = pvecResult;
pvecResult = pvecTmp;
}

for (intCount = 0; intCount < (*pvecSource).size(); intCount++)
{
cout << \"*********Posibility*************\" << intCount << endl << (*pvecSource)[intCount];
}

return 0;
}


http://myajax95./
2006-03-26 17:34
myajax95
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:30
帖 子:2978
专家分:0
注 册:2006-3-5
收藏
得分:0 
好像计算机比人聪明,竟然没用上“没有人有相同的宠物,抽相同牌子的香烟,喝相同的饮料 ”这条件,还没等我写那堆罗哩罗嗦的"unique","find"之类的东东就出唯一解了。

http://myajax95./
2006-03-26 17:38
踏魔狼
Rank: 6Rank: 6
等 级:贵宾
威 望:24
帖 子:1322
专家分:33
注 册:2005-9-22
收藏
得分:0 
你以为她真的会嫁给你吗!别做白日大头梦了!

=×&D o I p R e E n C g T l X&×=
2006-03-26 17:43
燃烧
Rank: 1
等 级:新手上路
帖 子:3267
专家分:1
注 册:2006-2-6
收藏
得分:0 
黄 蓝 红 绿 白
挪威 丹麦 英国 德国 瑞典
矿 茶 牛奶 咖啡 啤酒
DULL|混合|PALL| price|bluemaster
猫 马 鸟 ** 狗



一个群里朋友 kalrt 想出来的答案~~


佩服他的智慧 !


与11楼的答案一样!

[此贴子已经被作者于2006-3-26 21:02:14编辑过]


Give me a world !   A beautiful world !
2006-03-26 20:07
钢燃
Rank: 1
等 级:新手上路
帖 子:80
专家分:0
注 册:2005-5-19
收藏
得分:0 
用了将近一天的时间才得出结果,不想已经被别人占了先。
相同的结果就不重复了。

寻找同济的朋友的网络连接
2006-03-27 17:59
myajax95
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:30
帖 子:2978
专家分:0
注 册:2006-3-5
收藏
得分:0 

优化了一下算法,快了三倍,现在在我的机器上部到一秒钟就算完了。

程序代码:

#include <ctime>

#include <iostream>

#include <sstream>

#include <vector>

#include <algorithm>

using namespace std;

enum CONDITION_TYPE

{

CONDITION_TYPE_LOCATION = 0,

CONDITION_TYPE_NEIGHBOR_LEFTATTR,

CONDITION_TYPE_EXACT,

CONDITION_TYPE_NEIGHBOR_DIFFATTR,

END_PLUS_ONE_CONDITION_TYPE

};

class CCondition

{

public:

CCondition(string sNation, string sHouseColor, string sPet, string sDrink, string sCigarette, int intType=CONDITION_TYPE_EXACT, int intLocation = -1);

CCondition() : m_intType(-1), m_intLocation(-1) {}

void SeparateNeighbor(CCondition &cd1, CCondition &cd2);

void SeparateLeft(CCondition &cd1, CCondition &cd2);

int GetType() {return m_intType;}

int GetLocation() {return m_intLocation;}

private:

string m_sAttr[5];

int m_intType;

int m_intLocation;

friend class CApartment;

};

CCondition::CCondition(string sNation, string sHouseColor, string sPet, string sDrink, string sCigarette, int intType, int intLocation)

: m_intType(intType), m_intLocation(intLocation)

{

m_sAttr[0]=sNation, m_sAttr[1]=sHouseColor, m_sAttr[2]=sPet, m_sAttr[3]=sDrink, m_sAttr[4]=sCigarette;

}

void CCondition::SeparateNeighbor(CCondition &cd1, CCondition &cd2)

{

int intCount;

cd1 = *this;

cd2 = *this;

for (intCount = 0; intCount < 5; intCount++)

{

if (!m_sAttr[intCount].empty())

{

cd1.m_sAttr[intCount] = \"\";

break;

}

}

for (++intCount;intCount < 5; intCount++)

{

if (!m_sAttr[intCount].empty())

{

cd2.m_sAttr[intCount] = \"\";

break;

}

}

}

void CCondition::SeparateLeft(CCondition &cd1, CCondition &cd2)

{

int intCount, intPos;

cd1 = *this;

cd2 = *this;

for (intCount = 0; intCount < 5; intCount++)

{

if (!m_sAttr[intCount].empty() && (intPos = (int)m_sAttr[intCount].find('|')) > 0)

{

cd1.m_sAttr[intCount].erase(intPos, cd1.m_sAttr[intCount].size());

cd2.m_sAttr[intCount].erase(0, intPos+1);

break;

}

}

}

bool CompareConditionPriorities(CCondition cd1, CCondition cd2)

{

return cd1.GetType() < cd2.GetType();

}

class CApartment

{

public:

CApartment() {}

void Clear() {for (int intCount=0; intCount < 5; intCount++) m_sAttr[intCount]=\"\";}

bool IsComplete() {for (int intCount=0; intCount < 5; intCount++)

if (!m_sAttr[intCount].empty()) return false; return true;}

bool InsertCondition(CCondition &cd);

string ToString() const;

private:

string m_sAttr[5];

};

string CApartment::ToString() const

{

stringstream ssOutput;

ssOutput << \"Nation=\" << m_sAttr[0] << \", HouseColor=\" << m_sAttr[1] << \", Pet=\" << m_sAttr[2]

<< \", Drink=\" << m_sAttr[3] << \", Cigarette=\" << m_sAttr[4] << \".\" << endl;

return ssOutput.str();

};

bool CApartment::InsertCondition(CCondition &cd)

{

CApartment aptResult = *this;

for (int intCount = 0; intCount < 5; intCount++)

{

if (!m_sAttr[intCount].empty() && !cd.m_sAttr[intCount].empty()

&& m_sAttr[intCount] != cd.m_sAttr[intCount])

return false;

else if (!cd.m_sAttr[intCount].empty())

aptResult.m_sAttr[intCount] = cd.m_sAttr[intCount];

}

*this = aptResult;

return true;

};

ostream& operator << (ostream &o, const CApartment &apt)

{

return o << apt.ToString();

}

class CSolution

{

public:

void Clear() {for (int intAptCount=0; intAptCount < 5; intAptCount++) m_apt[intAptCount].Clear();}

int CSolution::InsertCondition(CCondition &cd, vector<CSolution> &vecSolution);

string ToString() const;

private:

CApartment m_apt[5];

};

string CSolution::ToString() const

{

stringstream ssOutput;

for (int intAptCount = 0; intAptCount < 5; intAptCount++)

ssOutput << m_apt[intAptCount].ToString();

return ssOutput.str();

}

int CSolution::InsertCondition(CCondition &cd, vector<CSolution> &vecSolution)

{

int intCount;

CCondition cd1, cd2;

CSolution sol;

switch (cd.GetType())

{

case CONDITION_TYPE_EXACT:

for (intCount = 0; intCount < 5; intCount++)

{

sol = *this;

if (sol.m_apt[intCount].InsertCondition(cd))

vecSolution.push_back(sol);

}

break;

case CONDITION_TYPE_NEIGHBOR_DIFFATTR:

cd.SeparateNeighbor(cd1, cd2);

for (intCount = 0; intCount < 4; intCount++)

{

sol = *this;

if (sol.m_apt[intCount].InsertCondition(cd1) && sol.m_apt[intCount+1].InsertCondition(cd2))

vecSolution.push_back(sol);

sol = *this;

if (sol.m_apt[intCount].InsertCondition(cd2) && sol.m_apt[intCount+1].InsertCondition(cd1))

vecSolution.push_back(sol);

}

break;

case CONDITION_TYPE_NEIGHBOR_LEFTATTR:

cd.SeparateLeft(cd1, cd2);

for (intCount = 0; intCount < 4; intCount++)

{

sol = *this;

if (sol.m_apt[intCount].InsertCondition(cd1) && sol.m_apt[intCount+1].InsertCondition(cd2))

vecSolution.push_back(sol);

}

break;

case CONDITION_TYPE_LOCATION:

if (cd.GetLocation() < 0 || cd.GetLocation() >= 5)

break;

sol = *this;

if (sol.m_apt[cd.GetLocation()].InsertCondition(cd))

vecSolution.push_back(sol);

break;

default:

break;

}

return (int)vecSolution.size();

}

ostream& operator << (ostream &o, const CSolution &sol)

{

return o << sol.ToString();

}

int main(int argc, char* argv[])

{

int intCount, intSource;

time_t tStart, tEnd;

CCondition cdlist[] =

{

CCondition(\"ENG\", \"Red\", \"\", \"\", \"\"),

CCondition(\"SWE\", \"\", \"Dog\", \"\", \"\"),

CCondition(\"DAN\", \"\", \"\", \"Tea\", \"\"),

CCondition(\"\", \"Green|White\", \"\", \"\", \"\", CONDITION_TYPE_NEIGHBOR_LEFTATTR),

CCondition(\"\", \"Green\", \"\", \"Coffee\", \"\"),

CCondition(\"\", \"\", \"Bird\", \"\", \"PaulMall\"),

CCondition(\"\", \"Yellow\", \"\", \"\", \"DunHill\"),

CCondition(\"\", \"\", \"\", \"Milk\", \"\", CONDITION_TYPE_LOCATION, 2),

CCondition(\"NOR\", \"\", \"\", \"\", \"\", CONDITION_TYPE_LOCATION, 0),

CCondition(\"\", \"\", \"Cat\", \"\", \"Mix\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),

CCondition(\"\", \"\", \"Horse\", \"\", \"DunHill\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),

CCondition(\"\", \"\", \"\", \"Beer\", \"BueMaster\"),

CCondition(\"GER\", \"\", \"\", \"\", \"Prince\"),

CCondition(\"NOR\", \"Blue\", \"\", \"\", \"\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),

CCondition(\"\", \"\", \"\", \"Water\", \"Mix\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),

CCondition(\"\", \"\", \"Fish\", \"\", \"\")

};

sort(&cdlist[0], &cdlist[15], CompareConditionPriorities);

CSolution sol;

vector<CSolution> vecResult1, vecResult2, *pvecSource = &vecResult1, *pvecResult = &vecResult2, *pvecTmp = NULL;

// bench mark for performance.

time(&tStart);

pvecSource->push_back(sol);

for (intCount = 0; intCount < sizeof(cdlist)/sizeof(CCondition); intCount++)

{

for (intSource = 0; intSource < (int)(*pvecSource).size(); intSource++)

(*pvecSource)[intSource].InsertCondition(cdlist[intCount], *pvecResult);

pvecSource->clear();

swap(pvecSource, pvecResult);

}

for (intCount = 0; intCount < (int)(*pvecSource).size(); intCount++)

cout << \"*********Posibility \" << intCount+1 << \" **********\" << endl << (*pvecSource)[intCount];

time(&tEnd);

cout << \"Processing time :\" << (long)(tEnd - tStart) << \" second\" << endl;

return 0;

}


http://myajax95./
2006-03-28 04:39
激情梦想
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2006-3-28
收藏
得分:0 
佩服,向你学习!!
2006-03-28 15:01
云无心
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2006-3-29
收藏
得分:0 
其实我也知道...
以前好象就看到过的...
有人说拉...
我就不重复拉...

菜鸟也学C++
2006-03-29 16:59
maoguoqing
Rank: 6Rank: 6
来 自:重庆
等 级:贵宾
威 望:28
帖 子:2980
专家分:19
注 册:2005-12-5
收藏
得分:0 

这题不难啊,我只做了10分钟,用了两次假设就出来了。


天行健,君子以自强不息!!QQ:68660681
2006-03-30 21:21
myajax95
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:30
帖 子:2978
专家分:0
注 册:2006-3-5
收藏
得分:0 

题目我少copy过来一行,引起不少误会。这题是让拿C或C++编程。

如果要保证程序写的不太难看,而且比较容易扩展,例如随便改几个条件后程序还能算出来,就稍微费点劲了。


http://myajax95./
2006-03-31 11:20
快速回复:做的出来我嫁给他
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.025414 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved