微软挑战赛之传话游戏有关问题
时间：2014.01.26
地点：基地二楼
-------------------------------------------------------------------
一、简述
今天看到了微软编程之美全国挑战赛的题目，于是拿来试试，发现还是很基础的，只要基础牢固，我想写出来的程序应该还是很靠谱的。
-------------------------------------------------------------------
二、题目
描述
Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的：首先，所有游戏者按顺序站成一排，Alice站第一位，Bob站最后一位。然后，Alice想一句话悄悄告诉第二位游戏者，第二位游戏者又悄悄地告诉第三位，第三位又告诉第四位……以此类推，直到倒数第二位告诉Bob。两位游戏者在传话中，不能让其他人听到，也不能使用肢体动作来解释。最后，Bob把他所听到的话告诉大家，Alice也把她原本所想的话告诉大家。
由于传话过程中可能出现一些偏差，游戏者越多，Bob最后听到的话就与Alice所想的越不同。Bob听到的话往往会变成一些很搞笑的东西，所以大家玩得乐此不疲。经过几轮游戏后，Alice注意到在两人传话中，有些词汇往往会错误地变成其他特定的词汇。Alice已经收集到了这样的一个词汇转化的列表，她想知道她的话传到Bob时会变成什么样子，请你写个程序来帮助她。
输入
输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组数据第一行包括两个整数 N 和 M，分别表示游戏者的数量和单词转化列表长度。随后有 M 行，每行包含两个用空格隔开的单词 a 和 b，表示单词 a 在传话中一定会变成 b。输入数据保证没有重复的 a。最后一行包含若干个用单个空格隔开的单词，表示Alice所想的句子，句子总长不超过100个字符。所有单词都只包含小写字母，并且长度不超过20，同一个单词的不同时态被认为是不同的单词。你可以假定不在列表中的单词永远不会变化。
输出
对于每组测试数据，单独输出一行“Case #c: s”。其中，c 为测试数据编号，s 为Bob所听到的句子。s 的格式与输入数据中Alice所想的句子格式相同。
数据范围
1 ≤ T ≤ 100
小数据：2 ≤ N ≤ 10, 0 ≤ M ≤ 10
大数据：2 ≤ N ≤ 100, 0 ≤ M ≤ 100
样例输入
2
4 3
ship sheep
sinking thinking
thinking sinking
the ship is sinking
10 5
tidy tiny
tiger liar
tired tire
tire bear
liar bear
a tidy tiger is tired
样例输出
Case #1: the sheep is thinking
Case #2: a tiny bear is bear
-------------------------------------------------------------------
三、分析
题目虽简单，但涉及的基础知识还是很多的，有很多细节的地方需要注意，比如限制条件，检查输入字符串的合法性等等。下面逐一分析：
3.1 首先，我们要检查数据范围的合法性，我们将代表人数的参数N和代表转换列表行数的M放在一起检查，代码如下：
bool IsParameterLeagal(char n, char m){
//Postcondition: check the parameter's leagal and return the result
bool is_n_m_leagal = ((n <= 10 && n >= 2) && (m <= 10 && m >= 0))||
((n <= 100 && n >= 2) && (m <= 100 && m >= 0));
return is_n_m_leagal;
}
为什么要返回一个bool值呢，我是想到时还结合别的数据检验一起做个断言，而这里只是对输入合法性检测的一部分，所以这里检测后返回一个bool值，只表示对这两个参数的合法性做出判断。
3.2 其次，要求中有对输入语句的要求，所以这里也要检查：
bool IsInputStringLeagal(const string& input_str){
//Postcondition: check the input sttring's leagal and return the result
//Library facilities used: sstream
if (input_str.length() >100)
return false;
istringstream record(input_str);
string word;
while (record >> word){
if (word.length() > 20)
return false;
for (auto c : word)
if (!islower(c))
return false;
}
return true;
}
这里可用到一些短路求值方式，即一旦发现不合法了，及时返回为false3.3 这里是输入数据处理部分，包括基本信息，比如多少个测试样例。N表示参与传话的人数，涉及N-1次传话，所以要在一个N-1次循环中不断变化。
string InputDataProcess(){
//Postcondtion: Input information and data process
//Library facilities used: assert,map
unsigned N, M;
cin >> N >> M;
assert(IsParameterLeagal(N, M));
map<string, string> transfer_map;
while (M != 0){
string origin_word, transfer_word="";
cin >> origin_word >> transfer_word;
transfer_map.insert({ origin_word, transfer_word });
M--;
}
string transfer_words;
getchar();
getline(cin, transfer_words);
assert(IsInputStringLeagal(transfer_words));
while (N != 1){
transfer_words = TransferWords(transfer_words, transfer_map);
N--;
}
return transfer_words;
}
这里要说道的是转换列表的构建，我用了一个map容器，主要是为了后面的方便查找，提高效率。还一个需要注意的地方时getchar()的使用，这里是要吃掉回车，刚开始时在这地方纠结了好久，因为getline()函数一直读不进我想要的一行字符串，而是一个空字符串，而我单独测试getline函数的用法时又没有问题，好蹊跷，后来才晓得cin字符串的，它会将换行符依然放置在流中，所以getline紧接着还是读到换行符，而它一触碰到换行符就结束，所以得到的是一个空字符串，用getchar吃掉这个换行符就OK了。这段代码我觉得还可以优化下，使得代码看起来结构更简洁优雅，比如建立转化表的部分完全可独立出来成为一个模块，可读性就更高了。
3.4下面部分是字符串转换函数，模拟两个人之间的通话，在这个过程中有些词汇会按照转换列表指定的格式做相应的转换，我们用到了sstringstream流对象，将字符串与一个istringstream对象绑定，逐个查询每个单词，该转换的转换，不该转换的保留。
string TransferWords(const string& input_str,const map<string,string>& given_map)
{
//Postcontion: When a communicate occured between two persons,the words will transfer
// according the transfer list.
istringstream record(input_str);
string word, transfer_words="";
while (record >> word){
auto it = given_map.find(word);
if (it != given_map.end())
transfer_words += (" "+it->second);
else
transfer_words += (" " + word);
}
return transfer_words;
}
3.5 一下是主函数部分，在这一节中可以体现程序的整体结构，程序分别对每组测试进行处理，之后将结果存储在一个向量之后，最后再去变量向量容器，把结果按要求打印出来。
int main(){
unsigned T;
cin >> T;
assert(T <= 100 && T >= 0);
vector<string> transfer_vec;
while (T!=0){
string out_string =InputDataProcess();
transfer_vec.push_back(out_string);
T--;
}
unsigned count = 1;
for (auto str : transfer_vec)
{
cout << "Cade #" << count << ":" << str << endl;
count++;
}
return 0;
}
-------------------------------------------------------------------四、完整代码
#include<iostream>
#include<string>
#include<cassert>
#include<vector>
#include<map>
#include<sstream>
#include<cctype>
using namespace std;
bool IsParameterLeagal(char n, char m){
//Postcondition: check the parameter's leagal and return the result
bool is_n_m_leagal = ((n <= 10 && n >= 2) && (m <= 10 && m >= 0))||
((n <= 100 && n >= 2) && (m <= 100 && m >= 0));
return is_n_m_leagal;
}
bool IsInputStringLeagal(const string& input_str){
//Postcondition: check the input sttring's leagal and return the result
//Library facilities used: sstream
if (input_str.length() >100)
return false;
istringstream record(input_str);
string word;
while (record >> word){
if (word.length() > 20)
return false;
for (auto c : word)
if (!islower(c))
return false;
}
return true;
}
string TransferWords(const string& input_str,const map<string,string>& given_map)
{
//Postcontion: When a communicate occured between two persons,the words will transfer
// according the transfer list.
istringstream record(input_str);
string word, transfer_words="";
while (record >> word){
auto it = given_map.find(word);
if (it != given_map.end())
transfer_words += (" "+it->second);
else
transfer_words += (" " + word);
}
return transfer_words;
}
string InputDataProcess(){
//Postcondtion: Input information and data process
//Library facilities used: assert,map
unsigned N, M;
cin >> N >> M;
assert(IsParameterLeagal(N, M));
map<string, string> transfer_map;
while (M != 0){
string origin_word, transfer_word="";
cin >> origin_word >> transfer_word;
transfer_map.insert({ origin_word, transfer_word });
M--;
}
string transfer_words;
getchar();
getline(cin, transfer_words);
assert(IsInputStringLeagal(transfer_words));
while (N != 1){
transfer_words = TransferWords(transfer_words, transfer_map);
N--;
}
return transfer_words;
}
int main(){
unsigned T;
cin >> T;
assert(T <= 100 && T >= 0);
vector<string> transfer_vec;
while (T!=0){
string out_string =InputDataProcess();
transfer_vec.push_back(out_string);
T--;
}
unsigned count = 1;
for (auto str : transfer_vec)
{
cout << "Cade #" << count << ":" << str << endl;
count++;
}
return 0;
}