猜单词游戏
word.pas(exe)
【问题描述】
人与计算机做猜英文单词的游戏，这种游戏每猜一次叫一局，让你参与多少局由计算机决定。局数为N。在第一局开始之前，由计算机给出一个文件，文件名为dict.txt，该文件中给出的是在下面N局中让你猜的全部可能的英文单词列表（所有的单词都只由26个小写英文字母组成）。计算机选择其中的一个单词让你猜，而你则需要用尽可能少的次数将这个单词猜出来。这个单词在你猜的过程中不会改变。
对于你猜的每一个单词，假如猜测正确，则本局游戏结束；否则，计算机会给出下列两个反馈信息：
1.
被猜的单词中有x个字符包含在你猜的单词中，给出数字x。假如同一个字母在被猜的单词或你猜的单词中出现了不只一次，则按照出现次数较少者计算。举例来说，设被猜的单词为dracula，其中有两个字母a，如果你猜的单词为bag，其中有一个字母a，则返回x=1；如果你猜的单词为abracadabra，则返回x=5。
2.
在上述被猜中的字母中有y (y<=x) 个是处在正确位置上的，给出数字y。
根据上述提示信息，你可以继续你的猜测，直到得出正确的答案为止。此时计算机会记住这一局你猜了多少次才成功，在你N局都猜完后，计算机会给出你累计N局所用的总次数和平均每局猜测的次数。当然，平均次数越少越好。
【编程要求】
现在需要你编写一个程序来做这个游戏。你的程序要和一个库(GuessLib.tpu)进行通讯，交互的进行这个游戏。
GuessLib.tpu提供了以下几个过程和函数供调用：
1)
Procedure Initialize;
初始化过程，同时生成词典文件dict.txt。此过程必须在程序开始处首先被调用，而且只能被调用一次。
2)
Function GetRoundNum:
integer;
返回游戏要进行的局数N，每次调用的返回值都一样。
3)
Procedure StartRound;
开始一局游戏，确定被猜测的单词。此过程必须在每一局游戏开始前调用。
4)
Procedure Guess(s:
string);
给出你的程序所猜测的单词s。
5)
Function CorrectNumber:
byte;
返回猜测正确的字符个数，在两次调用Guess之间返回值不会改变。
6)
Function CorrectPosition:
byte;
返回猜测正确的位置个数，在两次调用Guess之间返回值不会改变。
7)
Function Correct: boolean;
判断猜测结果是否就是正确答案，返回true就表示最近一次猜测是正确的，在调用StartRound之后，返回值会自动变成false。
8)
Procedure Finish;
当全部N局游戏结束之后，必须调用此过程，结束程序，此过程也生成运行结果报告，作为评判你的程序的依据。
【输入输出】
你的程序除了和GuessLib.tpu交互之外，只能读取文件dict.txt，而不能进行任何其他的文件读写操作。
Dict.txt的格式为：第一行是一个正整数w，表示文件dict.txt中所含的单词的数目；以下w行每行包含一个单词，单词的顺序没有规定，任何两行的单词都不相同。
【样例】
设调用Initialize后，生成单词表dict.txt如下：
6
host
hour
our
book
double
copy
再调用GetRoundNum得到游戏总的局数N，假设N=2。
第一局，调用StartRound，计算机选中的单词是double。当然，你的程序此时无从获知这个单词。
假如你的程序猜了host，即调用Guess(‘host’)，则有下述的反馈：
1.
调用Correct，返回false。
2.
调用CorrectNumber，返回1；
3.
调用CorrectPosition，返回1；
然后，你的程序可以根据这些反馈信息，进行进一步的猜测，直到得出正确结果为止。
完成第一局后，再次调用StartRound，则进入第二局，仍是如前所述的猜测过程，直至得出第二局的正确结果。
此后，调用Finish给出评测结果，然后结束程序。
【数据说明】
游戏局数N<=20。
Dict.txt中所含的单词数不超过3000，单词的长度最小为1个字母，最大为9个字母。
【评分说明】
程序的运行过程和结果由GuessLib.tpu自动记录。如果一局游戏最终猜测正确，则记录本局的猜测次数；如果未能正确猜出答案，作为惩罚，本局猜测次数以w+1计（w是词典文件中单词的总数）。N局游戏的猜测次数平均值作为最终给分的最主要的依据，平均次数越少，则分数越高。
另外，如果在第N局游戏开始之前程序结束或出现其他非法操作，则该测试点得零分。
【解析】
容易看出，这是一道交互题。
此题最朴素的解法是逐一尝试每个单词，如果Correct()就结束，否则继续猜测下一个单词，但在最坏情况下，这样做需要遍历整个单词表，效率极低。
于是我们想到设法利用CorrectNumber和CorrectPosition提供的信息减少猜词的次数。玩过类似游戏的人会很自然地联想到自己的游戏经历，并试图发掘两个函数计算方法所包含的隐含条件，然后越思考越觉得毫无头绪。
其实我们完全不需要关心两个函数实现的细节的背后的隐含条件（也许根本就没有）。我们先定义两个函数：
correctn(string guess, string word)：返回假设word是被猜的单词，guess为猜测的单词，调用CorrectNumber将得到的结果。
correctp(string guess, string word)：返回假设word是被猜的单词，guess为猜测的单词，调用CorrectPosition将得到的结果。
考虑单词$s$可能称为被猜的单词的必要条件，设$g$为你猜测的单词（即你的程序执行了Guess(g)）,则correctn(g,s)=CorrectNumber()且correctp(g,s)=CorrectPosition。于是大致的思路得到了：用一个布尔数组possible[]表示某一个单词是否可能成为被猜的单词。按顺序尝试每一个possible[i]=true的单词$w_i$。调用Guess($w_i$)，如果Correct()则猜测过程结束；否则遍历未尝试过的且possible[j]=true单词$w_j$，如果correctn($w_i$,$w_j$)≠CorrectNumber()或correctp($w_i$,$w_j$)≠CorrectPosition()则令possible[j]=false。
我们再来考虑correctn和correctp两个函数的实现。correctp很容易实现，直接扫描一遍两个字符串即可：
int correctp(string guess,string word)
{
int len1=guess.length(),len2=word.length();
int len=min(len1,len2);
int ans=0;
for(int i=0;i<len;i++)
{
if(guess[i]==word[i])ans++;
}
return ans;
}
coorectn的实现稍微复杂一点。想法是用一个大小为26的桶cnt存放guess中每个字母的出现次数，然后扫描一遍word，对于word中的每一个字符c，如果cnt[c]大于零，则出项次数加一，同时令cnt[c]减一。
int correctn(string guess,string word)
{
memset(cnt,0,sizeof(cnt));
int ans=0;
int len1=guess.length(),len2=word.length();
for(int i=0;i<len1;i++)
{
cnt[guess[i]-'a']++;
}
for(int i=0;i<len2;i++)
{
if(cnt[word[i]-'a'])
{
ans++;
cnt[word[i]-'a']--;
}
}
return ans;
}
程序剩下的部分的实现就相对容易了。
【参考程序】
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
#include "GuessLib.h"
using namespace std;
string words[3001];
bool possible[3001];
int n;
int cnt[26];
int correctp(string guess,string word)
{
int len1=guess.length(),len2=word.length();
int len=min(len1,len2);
int ans=0;
for(int i=0;i<len;i++)
{
if(guess[i]==word[i])ans++;
}
return ans;
}
int correctn(string guess,string word)
{
memset(cnt,0,sizeof(cnt));
int ans=0;
int len1=guess.length(),len2=word.length();
for(int i=0;i<len1;i++)
{
cnt[guess[i]-'a']++;
}
for(int i=0;i<len2;i++)
{
if(cnt[word[i]-'a'])
{
ans++;
cnt[word[i]-'a']--;
}
}
return ans;
}
int main()
{
Initialize();
freopen("dict.txt","r",stdin);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>words[i];
}
int m=GetRoundNum();
while(m--)
{
StartRound();
fill(possible+1,possible+n+1,true);
for(int
i=1;i<=n;i++)
{
if(possible[i])
{
Guess(words[i]);
if(Correct())break;
int cp=CorrectPosition(),cn=CorrectNumber();
for(int
j=i+1;j<=n;j++)
{
if(possible[j]&&(cp!=correctp(words[i],words[j])
||cn!=correctn(words[i],words[j])))
possible[j]=false;
}
}
}
}
Finish();
return 0;
}
【性能测试】
测试结果显示，以上程序在实际运行时表现良好，所有测试点的平均猜测次数小于5次，具体如下表：
测试点
|
游戏轮数
|
单词表大小
|
平均猜测次数
|
最大猜测次数
|
1
|
2
|
6
|
2.5
|
3
|
2
|
1
|
400
|
4
|
4
|
3
|
10
|
1500
|
4.4
|
6
|
4
|
10
|
1000
|
3.9
|
5
|
5
|
20
|
3000
|
4.15
|
6
|
6
|
20
|
1600
|
4.8
|
7
|
【附加说明】
本题原题无时间、空间限制，笔者结合现在计算机的性能及算法竞赛的惯例，建议时间限制1s，空间限制512MiB。
本题原题的测试库为.tpu文件，笔者查得此为Pascal语言编译时的中间文件，难以使用，C++语言版本的测试库已附加在测试数据中。
考虑到交换题评测的困难性，笔者还额外编写了Windows系统下的测试程序，供读者使用：
//使用方法：将可执行文件word与测试数据INPUT*.IN放在同一目录下，
//运行本程序，编译时的语言标准必须在C++11及以上。
#include <stdlib.h>
#include <string>
using namespace std;
int System(string s)
{
return system(s.c_str());
}
int main()
{
for(int i=1;i<=6;i++)
{
System("ren INPUT"+to_string(i)+".TXT
INPUT.TXT");
System("word");
System("ren INPUT.TXT INPUT"+to_string(i)+".TXT");
System("ren result.txt result"+to_string(i)+".txt");
}
}