我试图使用一种非常基本的程序化方法来创建一个字谜解算器。我发现我应该使用类来完成此操作,但是现在为时已晚,我的作业即将到期。关于如何解决这个问题的任何建议都很棒!
基本上,这就是算法应该做的:
获取字典中的所有单词;将它们存储在容器中
从用户那里获取信息;酌情退出
获取用户输入的单词的所有排列
从排列中去除用户输入的单词
除去排列集合中所有我在第1部分中收集的字典中没有的单词
现在,对于最后一步,我必须确保不显示重复的字谜(即包含相同字母的字谜,例如“循环”)。我似乎无法使该检查工作,这在下面的TODO注释块下已指出。
任何建议都很棒!
#include <iostream>
#include <fstream>
#include <string>
//
// Change size below to accomodate more anagrams and dictionary words
//
#define MAX_ANGM_SIZE 4096
#define MAX_WORD_SIZE 1048576
using namespace std;
//
// Determines whether anagram is valid or not; will not display word
// which user entered or words not contained in dictionary
//
bool isValidAnagram(string word, string userWord,
string dictionary[], unsigned int listIdx)
{
for(unsigned int idx = 0; idx < listIdx; ++idx)
{
if(word == userWord)
return false;
else if (word == dictionary[idx])
return true;
}
return false;
}
//
// Determines whether user's word is contained in the dictionary
// or not
//
bool isValidWord(string word, string dictionary[],
unsigned int listIdx)
{
for(unsigned int idx = 0; idx < listIdx; ++idx)
{
if(word == dictionary[idx])
return true;
}
return false;
}
//
// TODO:This function should test for duplicate anagrams and return
// true if duplicates are found.
//
bool isRepeated(string anagrams[], unsigned int anaIdx)
{
for(unsigned int idx = anaIdx; idx != 0; --idx)
{
if(anagrams[idx] == anagrams[anaIdx])
return true;
else
return false;
}
return false;
}
//
// Only display elements in array which aren't blank and don't
// display duplicate anagrams; notify user if no anagrams
// were found.
//
void displayAnagrams(string anagrams[], unsigned int next)
{
int flag = 0;
for (unsigned int idx = 0; idx < next; ++idx)
{
if((anagrams[idx] != "") || (!(isRepeated(anagrams, idx))))
{
if(idx == 1)
cout << " Anagrams: ";
if(idx > 0)
flag = 1;
cout << anagrams[idx] << " ";
}
else
continue;
}
if(flag == 0)
cout << " no anagrams found" << endl;
}
static void swap(char &c1, char &c2)
{
char temp = c1;
c1 = c2;
c2 = temp;
}
//
// Pass in word to be altered, the userWord for comparison, the array to store
// anagrams, the dictionary for comparison, the count for the number of anagrams
// and the count for number of dictionary words
//
static void permute(string word, string userWord, int k, string anagrams[],
string dictionary[], unsigned int &next, unsigned int listIdx)
{
if(k == word.length()-1)
{
if(isValidAnagram(word, userWord, dictionary, listIdx))
anagrams[next] = word;
++next;
}
else
{
for(int idx = k; idx < word.length(); ++idx)
{
swap(word[k], word[idx]);
permute(word, userWord, k+1, anagrams, dictionary, next, listIdx);
}
}
}
//
// Create container to store anagrams, validate user's word in dictionary, get all
// of the anagrams, then display all valid anagrams
//
void getAnagrams(string word, string dictionary[], unsigned int listIdx)
{
string anagrams[MAX_ANGM_SIZE];
unsigned int next = 0;
if(isValidWord(word, dictionary, listIdx))
{
permute(word, word, 0, anagrams, dictionary, next, listIdx);
}
else
{
cerr << " \"" << word << "\"" << " is not a valid word" << endl;
return;
}
displayAnagrams(anagrams, next);
}
//
// Read in dictionary file, store contents of file in a list, prompt
// the user to type in words to generate anagrams
//
int main()
{
string file;
string word;
string quit = "quit";
string dictionary[MAX_WORD_SIZE];
unsigned int idx = 0;
cout << "Enter a dictionary file: ";
cin >> file;
cout << "Reading file \"" << file << "\"" << endl;
cout << endl;
ifstream inFile(file.c_str());
if(!(inFile.is_open()))
{
cerr << "Can't open file \"" << file << "\""
<< endl;
exit(EXIT_FAILURE);
}
while(!inFile.eof())
{
inFile >> dictionary[idx];
++idx;
}
inFile.close();
while(true)
{
cout << "Enter a word: ";
cin >> word;
if(word == quit) break;
getAnagrams(word, dictionary, idx);
cout << endl;
}
return 0;
}
最佳答案
您可能需要重新考虑您的步骤(3)。如果用户输入一个12个字母的单词,那么您将有479,001,600个排列,一次不能全部组合起来(如果不是这样,那么将是16个字母的单词……)。
相反,尝试考虑如何存储单词并以不需要您这样做的方式查找可能的字谜。
编辑:我知道现在解决大词的能力可能不是您最关心的问题,但是如果您通过组合有效词集而不是从所有可能的方法开始并删除它们,实际上可能会使您的第四和第五步更容易所有不匹配的从数组中“删除”一个项目有点尴尬,因为您必须将以下所有项目重新整理以填补空白(这正是STL为您管理的事情)。
关于c++ - C++字谜生成器(不使用STL),我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/6567254/