实验环境

Windows 11 专业版22H2 Feature Experience Pack 1000.22642.1000.0

Microsoft Visual Studio Code 1.78.1 with MingW-W64-builds 10.0.0 & GCC 12.1.0

Qt Creator 9.0.2 Based on Qt 6.4.2 (MSVC 2019, x86_64)

实验目的

练习递归编程方法.

Problem 1 Game 24

问题分析与算法设计

封装递归函数

Set<string> countTwentyFours(Vector<Card> & cards)接受牌组cards作为参数,其遍历牌组中所有手牌,依次抽取一张作为起始牌调用主递归函数，将返回值加入到结果中，最后返回结果.

主递归函数

Set<string> countTwentyFoursRec(const Card result,Vector<Card> remain_cards)接受两个参数,result为当前的运算结果,remain_cards为剩余的手牌,实现过程大致如下:

Set<string> countTwentyFoursRec(const Card result,Vector<Card> remain_cards)
{
    Set<string> solutionsStrings={};
    if(剩两张牌)
    {
        solutionsStrings+=对剩余两张手牌进行运算合并后调用递归;
    }
    if(剩一张牌)
    {
        solutionsStrings+=最后一张手牌可以与result运算后达到24点的方法;
        return solutionsStrings;
    }
    for(遍历remain_cards)
    {
        solutionsStrings+=依次抽走一张牌与result进行四则运算后调用递归;
    }
    return solutionsStrings;
}

测试数据与结果

实验小结

已知的问题有:

1. 目前算法无法排除加法/乘法因为交换律可能出现的重复情况(比如( ( ( 5C + 10S ) - 9C ) * 4H )和( ( ( 10S + 5C ) - 9C ) * 4H )将会被视为两种不同的结果);
2. 目前结果的输出形式只针对4张手牌进行了考虑,包含了两种可能的情况:3-1式(比如( ( ( 5C + 10S ) - 9C ) * 4H ))或者2-2式(比如( ( 9C - 5C ) * ( 10S - 4H ) )),在四张以上手牌的游戏情况下有可能出现漏解的可能性;

Problem 2 The Game of Boggle

问题分析与算法设计

Task 1—Dice reading, board drawing, dice shaking.

这一部分相关的类/函数声明与实现分别在dice.h与dice.cpp中.

1. 绘制面板使用gboggle.cpp中的drawBoard()函数来完成;
2. 单独设计Dice类来完成与骰子相关的基础操作:
3. 私有成员:string letters存储骰子六个面的字母(大写);
4. 构造函数:Dice(string str)接受一个长度为6的字符串str作为参数(如果长度小于6报错无效输入,大于6自动截取前6位),str的每一位对应letters中的每一面;
5. char diceShaking()方法,调用radom.h库辅助,返回letters中的随机一个字母;
6. string getLetters()方法,返回私有成员letters;
7. 基于Dice类设计函数来完成整体的与骰子相关操作:
8. Vector<Vector<Dice>> read_all_dices(ifstream& file,int n)函数从文件中读取信息,返回一个n阶的二维Dice容器;
9. Vector<Vector<char>> shake_all_dices(Vector<Vector<Dice>> dices)函数随机掷出所有骰子,并且将结果绘制在面板上,同时返回一个小写的字母容器方阵来记录结果;

Task 2—User’s turn (except for finding words on the board)

这一部分相关的类/函数声明与实现分别在user.h与user.cpp中.

1. 启动函数:Set<string> user_turn(Vector<Vector<char>> cubes)
2. 接受一个骰子的掷取结果方阵作为参数,用于构造类型
3. 输出启动提示词;
4. 构建一个User类(关于类的具体说明在后);
5. 调用User::input()方法,使用户持续输入
6. 返回用户最终的输入结果,供电脑的回合调用来避免重复;
7. 辅助函数:string str_tolower(string str),返回str的全小写形式,来消除大小写的区别对重复性的影响
8. User类的具体说明
9. 私有成员:
   1. Set<string> inputed来记录用户已经输入的单词;
   2. Vector<Vector<char>> cubes来记录当前用户需要处理的骰子掷取结果;
10. 构造函数User(Vector<Vector<char>> cubes)接受一个骰子的掷取结果方阵作为参数,并将其传入对应的私有成员;
11. void input()方法:向inputed成员输入单词,该方法在本任务的部分检查以下输入合法性:
    1. str的长度是否小于4,如果是则要求重新输入
    2. str的转换小写后结果是否已经在inputed中存在,如果是则要求重新输入;
12. Set<string> get_inputed()方法:返回私有成员inputed

Task 3—Find a given word on the board.

这一部分相关的类/函数声明与实现分别在user.h与user.cpp中.

1. 在本阶段User::input()方法检查以下输入的合法性:
2. 配合Lexicon类字典检查输入单词是否为有效存在的英语单词;
3. 通过递归函数findGivenWord()函数(具体说明在后)检查输入单词是否能在结果方阵上被找到;
4. 辅助函数bool ifValidIndex(int index,int upper)返回一个数组索引是否合法,用来避免递归时可能出现的数组越界问题;index代表目标索引,upper代表索引可以接受的最大上限(开区间);
5. 辅助函数void doHighlight(Vector<Vector<int>> findRes)配合gboggle.h中的highlightCube()函数对搜索到的结果进行单词高亮操作,接受一个递归的搜索结果findRes作为参数传入;
6. 封装递归函数Vector<Vector<int>> findGivenWord(string word,Vector<Vector<char>> cubes)接受一个目标单词word和结果方阵cubes作为参数,返回一个二维的整型数容器,用来记录搜索到的轨迹,实现思路如下:
7. 遍历搜索结果方阵,查找单词的首字母是否存在于首字母中;
8. 当出现首字母后,调用主递归函数findGivenWordRec()进一步搜索结果,如果找到结果则直接返回,否则继续搜索;
9. 如果遍历结束仍然未搜索到结果,返回空容器;
10. 主递归函数Vector<Vector<int>> findGivenWordRec(string word,Vector<Vector<char>> cubes,Vector<Vector<int>> way,int word_len)接受四个参数,前两个与findGivenWord()函数相同,way参数传入已经记录的轨迹,word_len参数传入目标单词的长度,实现思路如下:
11. 当way.size()==word_len,此时所有字母已经被全部找到,返回way作为最终结果;
12. 如果不符合递归结束条件,取way[way.size()-1]的值作为current_pos,即当前位置;
13. 配合ifValidIndex函数搜索当前位置周围一圈符合规则的字母,并且检查是否为当前word的首字母;
14. 如果找到了符合要求的字母,对word截去首字母作为new_word,对way加入字母坐标作为new_way,将该字母在cube中的值赋0来避免重复使用,用这些新的参数继续递归,直到找到结果;
15. 如果最终依然没有找到结果,返回空容器;
16. 最终User::input()方法的实现方法大致如下:

   void User::input()
   {
       while(true)
       {
           输入word并将其自动转换为小写形式
           /*检查合法性阶段*/
           if(word为空)
               break;
           if(word长度<4)
               continue;
           if(word已经被输入)
               continue;
           if(word不在字典中)
               continue;
           if(递归结果为空)
               continue;
           /*录入阶段*/
           inputed.add(word);                // 向inputed成员录入单词
           doHighlight(findRes);            // 高亮单词
           recordWordForPlayer(word,HUMAN);// 为玩家计分
       }
   }

Task 4—Find all the words on the board (computer’s turn)

这一部分相关的类/函数声明与实现分别在computer.h与computer.cpp中.

1. 启动函数void computer_turn(Vector<Vector<char>> cubes,Set<string> user_found)
2. 接受两个参数传入:结果方阵cubes和用户找到的单词user_found;
3. 使用传入的参数构造一个Computer类(类型说明在后);
4. 调用Computer::findAllWords()方法递归找到所有单词;
5. 为电脑记录单词与分数;
6. Computer类:
7. 私有成员:
   1. Set<string> user_found用户已经找到的单词;
   2. Set<string> computer_found电脑找到的单词;
   3. Vector<Vector<char>> cubes;需要处理的结果方阵;
8. 构造函数:Computer(Vector<Vector<char>> cubes,Set<string> user_found)接受两个参数并且传入到对应的私有成员;
9. 方法Set<string> get_user_found()&Set<string> findAllWords()返回对应的私有成员;
10. 方法Set<string> findAllWords()封装的递归函数,遍历cube中的每一个元素,将其作为首字母调用主递归函数findAllWordsRec()并将返回值加入到结果中,最后返回完整的结果;
11. 主递归函数:findAllWordsRec():
12. 完整形式为 Set<string> findAllWordsRec(Vector<Vector<char>> cubes, Set<string> user_found, string current_word, Vector<int> current_pos, Set<string> found); 参数说明:
    1. cubes:当前处理的结果方阵;
    2. user_found:用户已经找到的单词;
    3. current_word:目前搜索路径的对应单词;
    4. current_pos:目前的搜索位置;
    5. found:电脑已经找到的单词;
13. 实现过程:
    1. 将参数found拷贝到当前结果result中;
    2. 如果字典中已经不存在current_word开头的单词,则递归结束,返回result;
    3. 如果current_word满足:长度大于4且用户没找到且在字典中,则将其添加到result中;
    4. 配合isValidIndex()函数搜索current_pos周围一圈合法的cube元素,分别将新字母元素添加到new_word中,更新位置next_pos,最后使用新参数调用递归,将结果添加到result中;
    5. 遍历搜索完成后,返回result;

Boggle.cpp

最终实现的游戏流程函数调用如下:

void playBoggle() {

    GWindow gw(BOGGLE_WINDOW_WIDTH, BOGGLE_WINDOW_HEIGHT);
    gw.setLocation(50,50);
    initGBoggle(gw);

    while (true) 
    {
        /*Task 1 — Dice reading, board drawing, dice shaking.*/
        // 画板
        drawBoard(4,4);
        // 读取骰子
        ifstream dice_data("res/cubes16.txt");
        Vector<Vector<Dice>> dices=read_all_dices(dice_data,4);
        dice_data.close();         
        // 掷骰子
        Vector<Vector<char>> cubes=shake_all_dices(dices);
        /*Task 2&3 — User's turn*/
        auto user_found=user_turn(cubes);
        /*Task 4 — Find all the words on the board (computer's turn)*/
        computer_turn(cubes,user_found);

        if (!getYesOrNo("Would you like to play again? ")) break;
    }

    exitGraphics();
}

测试数据与结果

实验小结

In Task1

1. read_all_dices()函数逻辑上参数n对应的是列的数量(每行的数据量达到列数换行),但是考虑到题目给出的数据是4阶或5阶方阵,所以简记为n;
2. 当输入输出流作为参数传入函数时不能使用值传递,必须使用引用传递的方式,即ifstream&;

In Task2

1. 本来while循环是写在user_turn()函数中,而User::input()方法通过传入一个字符串参数进行单次输入,但是这种方式存在无法顺利跳出循环的可能性(比如先输入一个不符合的单词→程序要求重新输入→输入空字符串结束循环→程序认为输入小于4要求重新输入)于是最后决定将整个输入过程全部封装在User::input()方法中,且此时该方法不需要任何参数传入;

In Task3

1. 考虑到Words should be considered case insensitively: PEACE is the same as peace.的要求,所有的输入最后全部转换为小写形式,这和cubes均为小写形式保持了一致;

In Task4

1. 感觉实际的运行速度似乎比Demo程序慢上了一点?
2. 本来在findAllWordsRec()函数中用了和findGivenWordRec()函数中一样的way作为参数传入,但是在计算机搜索的过程中似乎没有记录完整路径的必要,只需要保留最后一个当前位置即可,于是最后修改参数为current_pos;