4 CS 4551/10CS 455编程任务42024年春季[Bono]到期时间：4月10日星期三晚上11:59简介和背景在本次课业中，您将有机会使用我们的一些Collection类和方法最近进行了报道。这将使您能够用更少的精力编写运行速度更快的程序如果不是这样的话。在这项任务中，你也将有机会做自己的事情设计与过去的课业相比，我们为您提供的设计大纲没有那么受约束：您将决定大多数类的确切接口和表示方式。
你会还可以练习使用命令行参数和文本文件处理。这项任务涉及拼字游戏。你可能更了解拼字游戏作为与朋友的话语。如果你想自己尝试Words with Friends，你可以下载免费的智能手机应用程序。但是，编程任务不是创建游戏本身，但要编写一个基于控制台的程序，找到所有可能的单词由一架子拼字游戏瓷砖制成（这样可以帮助玩拼字游戏的人）。我们将详细说明关于本任务的确切要求，请参阅下面的任务部分。一架拼字游戏牌（小数字是玩该牌的分数）目录分配文件任务需求汇总错误检查方法AnagramDictionary类查找机架的所有子集课堂设计开发提示/测试数据分级标准自述文件/提交程序分配文件PA
4 CS 4552/10
注意：下面的简介并没有描述每一个类是什么，以及它们是如何适应的在一起有关详细信息，请参阅关于类设计的部分。这里列出了我们在Vocareum上为您提供的入门文件。下面用粗体显示的文件是您创建和/或修改并提交的。那些不粗体的是你会的使用，但不能修改。关于下面的java类的更多详细信息，请参阅class部分设计这些文件是：WordFinder.java这个类将包含main方法和任何其他辅助方法你设计的。（您创建了此文件。）AnagramDictionary.java字典中的所有变位符集。我们提供了界面。这节课在这里有更多的讨论。
Rack.java存储当前机架。你可以决定代表和公众方法。我们为您编写了私有静态allSubsets方法，讨论了后来ScoreTable.java这个类有关于每个拼字字母值多少钱的信息。（您创建了此文件。）IllegalDictionaryException.java用于报告非法词典的类。我们写这篇文章是为了你sowpods.txt我们将使用的拼字游戏词典。这里给出的版本都更低大写字母。到这里来解释一下它奇怪的名字。testFiles中包含一些数据文件和相应输出的子目录，以获取帮助测试。该目录中的README.txt文件解释了这些文件以及如何使用它们。自述文件请参阅“提交程序”一节，了解要放入的内容请阅读以下声明，您将在自述文件：“我保证为本次任务提交的作品没有违反南加州大学的学生行为准则。特别是，这项工作是我自己的，而不是合作，并且不涉及其他人或人工智能软件创建的代码CS 455课程大纲中明确提及的资源除外。我没有在课程"注意：您可能还有其他文件，请参阅类设计部分了解更多信息。任务您将实现一个名为WordFinder的程序，当给定可以包括一个拼字游戏架，创建一个可以由字母组成的所有法律单词的列表在那个架子上。为了解决这个问题，你还需要一本拼字词典（我们会提供为您）。拼字游戏词典的一些细节：它只有两个或两个以上长度的单词，它包括作为单独词条的单词的所有形式，例如单数加复数和动词结合。
例如，如果你的架子上有字母c m a l，你可以重新排列字母以形成单词calm或clam，但你也可以从字母的子集中形成较短的单词，例如lamPA4 CS 4553/10或者ma。通常很难计算出构成真正单词的所有字母序列（除非你是一个非常懂拼字游戏词典的比赛选手好对于您的程序，您将显示所有此类单词，以及相应的拼字游戏分数每个单词，按分数降序排列。每个字母都有一个与之相关的分数，分数因为一个单词是该单词中每个字母得分的总和。对于相同的单词拼字得分，单词必须按字母顺序出现。以下是机架的结果由输出格式中显示的“cmal”（使用sowpods字典）组成用于您的程序（用户输入以斜体显示）：支架cmal我们可以用“cmal”造11个单词所有单词及其分数（按分数排序）：8：冷静8：蛤蜊7：凸轮7:mac5:lac5:lam5:mal4:am4:ma2:al2:la我们将在本文档后面为您提供每个字母的拼字游戏分数。以下是关于如何运行程序以及会发生什么的详细信息：您的程序将为字典文件名使用一个可选的命令行参数。如果如果忽略该参数，它将使用拼字游戏词典文件sowpods.txt（请参阅赋值文件）在运行程序的同一目录中。（注意：需要进行错误检查与字典文件相关的内容将在以下部分中进行描述。）一旦程序启动，它将打印消息：类型退出。然后，程序将在控制台上循环运行，打印提示“Rack？”（如中所示前面的例子），并读取和处理您输入的每个机架，直到您告诉它退出。用户在提示处输入“.”（即一个句点），告诉程序退出。我们没有使用命令，如“退出”作为哨兵，因为这可能是一个合法的机架。我们为您提供了一些样本数据文件，以及相应的正确参考输出在testFiles中的sowpods.txt（给定的拼字游戏词典）上运行这些目录请参阅该目录中的README.txt，代 写CS 4551编程任务以获取示例文件的指南以及如何使用它们。您的输出必须与引用输出逐字符匹配。真正的拼字游戏在方块上只有大写字母，但对于我们的程序，我们将接受任何非空白字符序列作为合法的“支架”。但是，单词只会如果给定的字典中有实际的字母，那么它就可以由实际的字母组成。例如，如果机架如果是“abc@”，你会报告“cab”等单词，但不会有包含PA
4 CS 4554/10“@”，因为@不会出现在任何字典单词中。如果机架中有这样的字符，它们也会在显示的关于机架的初始消息中打印出来。例如？？我们可以做11“cm！a#l”中的单词该程序将同时适用于小写和大写版本的词典，但所有处理将区分大小写。例如，如果给定的词典只有大写版本的单词，它会从机架中找到单词，如“CMAL”，但无法从中找到任何单词机架“cmal”。这个程序和拼字游戏之间的一些其他区别：真正的拼字游戏也有两个空白的外卡牌。您的程序将没有此功能。在拼字游戏中，你几乎总是有整整七个字母的架子。对于此程序，您可以为机架输入任意数量的字符。如果机架具有超过七个字符，你还将报告字典中超过七个字符的单词。这个程序只处理从架子上的东西形成单词的问题，而不是考虑一下拼字游戏板上的任何方块。这显示了如何运行程序：java WordFinder[dictionaryFile]注意：在这种显示Unix命令行语法的通用格式中，方括号（即。，[]）不是键入的命令的一部分：它只是一个表示该命令的符号显示的行参数是可选的。其他程序要求在以下章节中进行了描述和总结在这里方法您需要使用下面讨论的第二种方法，在方法我们开始的课堂设计就是按照这种方法进行的。效率如果你有一个有效的解决方案，你会得到更多的信用。我们讨论方法和在AnagramDictionary类上紧随其后的一个。课堂设计。您需要设计和实现中讨论的类课堂设计部分。我错误检查。下一节将介绍您必须处理的两个错误。自述。和往常一样，您需要提交一个自述文件。见本文件末尾这项任务需要做些什么。样式/文档/设计。同样像往常一样，您的课程将根据风格进行评估和文件；但这次我们也将评估您的设计。请参阅章节有关分级标准的更多详细信息。错误检查下面列出了您的程序需要检查的唯一错误。对于这些错误中的每一个您的程序将打印示例所示的错误消息，然后打印PA
4 CS 4555/10正在退出程序。然后立即退出。1.字典文件不存在。假设给定的字典文件是testFiles/foobar.txt错误消息：错误：字典文件“testFiles/foobar.txt”不存在。2.字典文件中有重复的单词。假设字典文件在两个位置包含单词“cat”。例如，字典文件目录房屋猫这个狗猫小狗错误消息：错误：非法字典：字典文件有一个重复的单词：cat你的程序不必报告所有重复的单词，只需报告它检测到的第一个单词。上面给出的例子没有任何其他单词重复（“dog”和“doggy”是两个不同的词）。方法解决这个问题有两种不同的方法。一种是阅读字典，以及然后，对于给定的每个架子，将字典中的每个单词与该架子进行比较，找出答案该单词是否可以由该支架中的部分或全部字母组成，创建一个列表法律用语。这样处理字典更快，但处理每个字典更慢支架第二种方法是你将用于课业的方法，包括对字典进行预处理，以便按照每个字母的字母集来组织单词contains（这个集合实际上是一个多集合，因为字母在一个单词中可以出现不止一次；机架本身也是多集）。
然后，对于每个机架，您将生成其所有子集多个字母集，并为每个子集添加字典中的所有单词与该子集相同的元素。这处理字典的速度较慢，但一旦我们这样做了处理，处理每个机架比第一种方法更快。对这种方法进行了解释在以下两个部分中更详细地介绍。PA4 CS 4556/10用大O术语描述每种方法的时间有点复杂，但处理一个机架较慢的第一种方法是遍历整个字典（这将通常较大）。对于第二种方法，处理机架的较慢部分是创建所有子集。创建子集的最坏情况是没有重复机架中的字母（即创建的子集的最大数量）。即使生成子集因为这样一个支架需要O（n*2n)对于一个由n个唯一字符组成的机架（因为有2n个子集当没有重复字符时，n个步骤形成每个子集），n将通常较小：对于7块机架：27只有128，乘以7是896）。在仪器化解决方案中我们使用这种方法编写，处理sowpods词典只花了不到半秒的时间，以及处理一个7个字符的机架，其中没有重复的字符，并且包含最多英语中常见的字母耗时不到15毫秒（这是测试文件testFiles/aestnlr.in）。（常见的字母会产生更大的单词列表。）这些跑步是在Vocareum上完成的。
在第二种方法中，处理机架所花费的一些时间是获得每个子集的变位符；我们将在下一节中进一步讨论。处理一个架子的剩余时间是对结果单词列表进行排序。为了获得本次任务的全部学分，您需要使用第二种方法进行任务；我们将在下面的部分中进一步详细介绍它。AnagramDictionary类对于我们正在使用的方法，我们说您将按照一个单词包含的一组（多）字母。如果两个单词在不同的单词中包含完全相同的字母按照顺序，它们被称为彼此的变位词。如果一个机架（或该机架的子集）具有所有相同的字母（以及这些字母的多重性）作为字典中的一个特定单词，该单词，加上字典中的所有变位词都应该添加到我们报告的单词列表中WordFinder程序。您需要创建一个AnagramDictionary类来处理此问题。它将有一个getAnagramsOf方法，该方法可以有效地查找特定字符串的所有变位符。例如，假设我们AnagramDictionary类型的变量dictionary，包含来自sowpods字典的数据。如果我们打电话dictionary.getAnagramsOf（“rlee”）它将返回以下字典单词的ArrayList：[“leer”、“lere”、“reel”]（不是必须按该顺序）。注意，“rlee”不是一个真实的单词：该方法不需要给它一个字。但返回的字谜是真正的英语单词。如何有效地做到这一点？一个见解是，如果我们把两个词放在某种规范中形式，然后我们可以通过比较它们的规范版本以实现平等。此规范形式将是的排序版本单词中的字符。在前面给出的示例中，机架包含“cmal”。排序的这个机架的版本是“aclm”。输出中列出的前两个单词是“平静”和“蛤蜊”，“aclm”的变位词，或者换一种说法，前两个单词是字典中唯一的单词PA
4 CS 4557/10我们可以使用架子上的所有字母，列出的所有其他单词都是的字谜“cmal”的子集。为了获得全额积分，您的AnagramDictionary需要及时找到一个字符串的所有变位词输出集的大小是线性的（不包括对给定字符串中的字母进行排序的时间将其转化为规范形式。）查找机架的所有子集找到多集的所有子集本身就是一个有点困难的递归问题，因此为了简化此任务，我们为您编写了代码（中的静态方法allSubsetsRack.java）。该方法是静态的，因为与我们编写的其他一些递归方法一样，它将其所有数据作为显式参数；同时，这意味着所有子集都可以工作，无论发生什么您为机架对象选择的表示（所有子集将不会访问任何机架实例变量）。该解决方案在结构上与计算所有课本第13.4节中给出的字符串排列。你可能需要写一个包装器方法，该方法使用正确的起始参数调用allSubsets。allSubsets方法使用机架的特定表示，我们将用这里的例子。前面我们提到了一个架子是一组多字母（因为我们没有注意字母的顺序，并且multiset是因为字母可以出现多次）。假设我们的机架是：a b a d b b把类似的字母聚在一起，我们可以把它重写为“aabbbd”。
我们也可以这么说“a”出现在多重数2处，“b”出现在重数3处，而“d”出现在多重性1。allSubsets希望机架信息位于两个平行阵列中：其中一个具有唯一的字母，而另一个在相同的数组索引处具有该字母的多重性。这个唯一字母数组实际上是一个String，所以我们可以对它进行String操作举个例子，我们可以创建这个机架表示，如下所示：//为机架“aabbbd”创建变量字符串unique=“abd”；int〔〕mult＝｛2，3，1｝；//示例显示unique和mult中的值之间的关系：for（int i=0；i＜unique.length（）；i++）{System.out.prinn（unique.charAt（i）+“出现”+多[i]+“在机架中的次数”）；}与我们看到的其他数组递归示例一样，allSubsets将占用三分之一自变量，k，它是此递归调用将要执行的数组部分的起始位置过程因此，对于这段代码，它是查找子集的起始位置。所以，对于例如，如果我们调用allSubsets（unique，mult，1）；//从unique和mult中的位置1开始它会找到机架“bbbd”的所有子集（即，它不会考虑PA
4 CS 4558/10包括任何“a”）。课堂设计与本课程之前的程序不同，这次您将设计自己的程序课程，并提供一些指导。因此，你的部分风格得分将基于您的设计质量。在进行面向对象的设计时，首先要提出一组候选类，为每个选择一个名称，并在的上下文中确定每个的职责总体上更大的程序。我们已经为您完成了这一步。我们要求您在在您的解决方案中至少有以下五个类，以及所描述的职责。你是允许在您认为合适的时候向您的设计中添加更多的类。五个人，以及他们的整体所述职责包括：WordFinder这包含主要方法。这个类将有一个主要负责处理命令行参数，并处理任何错误处理。它会的可能还有主命令循环。大多数其他功能将委托给在main中创建的其他对象及其方法。