| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 | 
登录
注册
用户控制面板
搜索
道具
风格
短消息
论坛展区
帮助
编程论坛 → 开发语言 → C++论坛 → 『 VC++/MFC 』 → 做的出来我嫁给他
我的收件箱(0)
欢迎加入我们，一同切磋技术
用户名：   
 
密　码：  
共有 1174 人关注过本帖
标题：做的出来我嫁给他
只看楼主 加入收藏
myajax95
Rank: 16Rank: 16Rank: 16Rank: 16
等　级：版主
威　望：30
帖　子：2978
专家分：0
注　册：2006-3-5
第 11 楼
收藏
 得分: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
第 12 楼
收藏
 得分:0 
好像计算机比人聪明，竟然没用上“没有人有相同的宠物，抽相同牌子的香烟，喝相同的饮料 ”这条件，还没等我写那堆罗哩罗嗦的"unique","find"之类的东东就出唯一解了。

http://myajax95./
2006-03-26 17:38
踏魔狼
Rank: 6Rank: 6
等　级：贵宾
威　望：24
帖　子：1322
专家分：33
注　册：2005-9-22
第 13 楼
收藏
 得分: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
第 14 楼
收藏
 得分: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
第 15 楼
收藏
 得分:0 
用了将近一天的时间才得出结果，不想已经被别人占了先。
相同的结果就不重复了。

寻找同济的朋友的网络连接
2006-03-27 17:59
myajax95
Rank: 16Rank: 16Rank: 16Rank: 16
等　级：版主
威　望：30
帖　子：2978
专家分：0
注　册：2006-3-5
第 16 楼
收藏
 得分: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
第 17 楼
收藏
 得分:0 
佩服，向你学习!!
2006-03-28 15:01
云无心
Rank: 1
等　级：新手上路
帖　子：6
专家分：0
注　册：2006-3-29
第 18 楼
收藏
 得分:0 
其实我也知道...
以前好象就看到过的...
有人说拉...
我就不重复拉...

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

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


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

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

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


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



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

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