/*此文是译者出于自娱翻译的GotW(Guru of the Week:http://www.gotw.ca/gotw/index.htm)系列文章的一篇，原文的版权是属于Hub Sutter（著名的C++专家，《Exceptional C++》的作者）。此文的翻译没有征得原作者的同意，只供学习讨论。——译者:黄森堂*/
#41 使用标准库
难度:9/10
你知道使用标准库的算法吗？
问题
1.写一个简单的Mastermind程序，只能使用标准库里的容器，算法与流，它可以使你使用较少的"if","while","for"及其它内建功能的等等，且在程序里可能会使用变成只有少量的声明。
简单的规则
开始我们的游戏：在程序内部的若干顺序里随机选择的4个peg组成的串，每个peg使用三种颜色中的一种:red (R), green (G) 或 blue (B),例如：程序可以选用"RRBB" 、 "GGGG"与 "BGRG".
玩家开始制造连续的猜测直到它(像"RRBB")出现，在每一次猜测，程序告诉玩定两个数字：第一个Peg号是正确的颜色（不依赖于顺序）,第二个Peg号是正确的颜色位置。
这儿是示例，左边是猜想号，右边是哪个猜想会合并出来的"RRBB": 猜测--> rbrr
3 1
猜测--> rbgg
2 1
猜测--> bbrr
4 0
猜测--> rrbb
4 4 - solved!
(对于这个猜迷的更复杂的方法被Tom Holady在1997年11月提出：写一个高级、完整的Mastermind程序，只使用一个表达式，)
解决
1.写一个简单的Mastermind程序，只能使用标准库里的容器，算法与流，它可以使你使用较少的"if","while","for"及其它内建功能的等等，且在程序里可能会使用变成只有少量的声明。
这个解决方案不是最好的的答案，在实际上，它不需要清除，它简直是不可想象的，每一个放到新闻组里的解决方案有我喜欢的方面(例如：像使用cout<>与inner_product)与我不喜欢的方面(例如：像缺乏随机组合与在算法中硬编码peg颜色),所有的解决方案中，只有这个有包含这方面，但缺少错误检查.
这个解决方案中避免了硬编码peg颜色与在算法中限制了组合长度,peg颜色的扩展只需要简单的改变“color”串，组合长度的改变只需要简单地改变'4'来扩展，它没有使用到一个"while",然而，它使用了"find_if"(istream_iterator<string>(cin), ... )进行替换(成本比较清楚). string colors("BGR"), comb(4, '.'), l(comb), guess;
typedef map<int,int> M;
struct Color {
Color( M& cm, M& gm, int& color )
: cm_(cm), gm_(gm), color_(color=0) { }
void operator()( char c )
{ color_ += min( cm_[c], gm_[c] ); }
M &cm_, &gm_;
int& color_;
};
struct Count {
Count( int& color, int& exact )
: color_(color), exact_(exact=0) { }
char operator()( char c, char g )
{ return ++cm_[c], ++gm_[toupper(g)],
exact_ += c == toupper(g), '.'; }
~Count()
{ for_each( colors.begin(), colors.end(),
Color( cm_, gm_, color_ ) ); }
M cm_, gm_;
int &color_, &exact_;
};
char ChoosePeg()
{ return colors[rand() % colors.size()]; }
int main() {
int color, exact = 0;
srand( time(0) ),
generate( comb.begin(), comb.end(), ChoosePeg );
while( exact < comb.length() ) {
cout << "\n\nguess--> ", cin >> guess;
transform( comb.begin(), comb.end(),
guess.begin(), l.begin(),
Count( color, exact ) );
cout << color << ' ' << exact;
}
cout << " - solved!\n";
}
|
本类阅读TOP10