CS106x-Recusion

文章发布时间:

最后更新时间:

文章总字数:
3.4k

预计阅读时间:
13 分钟

作业,文档不长,但是感觉很复杂,不过感觉非常有意思!人机对战哎!

Before Coding

gboggle.h

起手读源码,因为又有图形接口,作业文档反而不是我最先看的,明明lifeGame那会儿一点源码不会读😂

这段代码是一个C++头文件,名为gboggle.h,它定义了一个名为GBoggle的游戏的相关接口和功能。下面是对代码的逐行解释:

  1. 文件开头的注释块提供了文件的基本信息,说明了这个头文件包含的是一个Boggle游戏界面的函数集合,这些函数包括绘制游戏板、管理单词列表和更新计分板。
  2. #ifndef#define预处理指令用来防止头文件被多次包含进同一个源文件中,这是一种常见的防止重复定义的宏定义方法。
  3. #include <string>#include "gwindow.h"是包含指令,分别引入了C++标准库中的字符串头文件和另一个名为gwindow.h的头文件,后者可能是一个自定义的图形窗口库。
  4. 定义了两个常量kBoggleWindowWidthkBoggleWindowHeight,分别代表Boggle游戏窗口的宽度和高度。
  5. 定义了一个枚举类型Player,用来区分人类玩家和电脑玩家。
  6. 函数initGBoggle(GWindow& gw)的声明,该函数用来初始化GBoggle包,并设置使用客户端提供的图形窗口。
  7. 函数shutdownGBoggle()的声明,该函数用来关闭图形窗口并释放与GBoggle包相关联的资源。
  8. 函数drawBoard(int numRows, int numCols)的声明,该函数用来绘制具有指定行数和列数的Boggle游戏板的空布局。
  9. 函数labelCube(int row, int col, char letter)的声明,该函数在指定位置的立方体上绘制一个字母。
  10. 函数highlightCube(int row, int col, bool flag)的声明,该函数根据标志flag的值来高亮或取消高亮指定的立方体。
  11. 函数recordWordForPlayer(const std::string& word, Player player)的声明,该函数记录玩家提交的单词,并更新显示和计分板。单词的得分根据单词的长度来计算。

整个头文件为GBoggle游戏提供了基本的框架和功能声明,具体的实现细节需要在对应的源文件中查看。这个头文件是游戏开发中的一部分,为游戏的界面显示和逻辑处理提供了接口。

懒了,抱一丝儿~
注意,enum Player { HUMAN, COMPUTER };枚举人类与计算机玩家类型,如何使用这个枚举?

1
2
3
4
5
6
7
Player current_player = HUMAN;
Player p1 = HUMAN;
Player p2 = COMPUTER;

if (current_player == HUMAN) {
// do something
}

WalkThrough

boggle.cpp

main中已经完成了GUI的初始化,只需完成playBoggle();部分。

coding

choose Letter Randomly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// 摇晃骰子并展示投掷结果
void chooseLetterRandomly() {
Vector<string> cube = cubeType;
for (int i = 0; i < cube.size(); i++) {
// 洗牌
int r = randomInteger(i, cube.size()-1);
string temp = cube[i];
cube[i] = cube[r];
cube[r] = temp;
}

int d = 4; // dimension
if (cube.size() % 5 == 0){
d = 5;
}

// 绘制
int count = 0;
for (int i = 0; i < cube.size(); i++) {
if (d == 4 && i % 4 == 0 && i != 0) {
count = 0;
} else if (d == 5 && i % 5 == 0 && i != 0) {
count = 0;
} else {
count++;
}
for (int j = 0; j < d; j++) {
int rr = randomInteger(0, 5);
string letter = cube[count][rr];
labelCube(count, j, letter);

}

}
}

// 找单词并高亮
static void playerFindWord(Player current_player) {
// do something no matter who is current player

if (current_player == HUMAN) {

} else {
// computer
}
}

/**
* Function: playBoggle
* --------------------
* Manages all details needed for the user to play one
* or more games of Boggle.
*/
static void playBoggle() {
int dimension = getPreferredBoardSize();
drawBoard(dimension, dimension);
cout << "This is where you'd play the game of Boggle" << endl;

/**
* seem should start at here
* -------------------------
* 画版
* 打乱所有的字符串骰子 Shuffle
* 递归的找出所有单词containWord(优化大小写
* 人类回合:输入并计分,空输入表示结束,单词高亮处理
* 计算机回合:输出所有未被人类发现的单词
*/
if (dimension == 4) {
chooseLetterRandomly(kStandardCubes);// kStand全局变量不用传参
} else {
chooseLetterRandomly(kBigBoggleCubes);
}

Set<string> wordSet = containWords();
Set<string> visited;

Player current_player = HUMAN;
bool flag = true;
while (flag) {
string input = getLine("input any possible words, enter [space] to end: "); // 全改成大写
if (input == " ") {
current_player = COMPUTER; // HUMAN to COMPUTER
} else if (wordSet.contains(input) && !visited.contains(input)){
// 计分,高亮,单词记为以找出
// 计算机找出所有未被人类找出的单词
} else {
cout << "WRONG WORDS! TRY AGAIN:";
}

// computer 完成后返回false
if (current_player == COMPUTER)
flag = false;
}

}

完成递归的课程之后重新写就轻松不少了,顺手达成成就:连续写一百行代码没有bug。

递归部分完成,就是有点小瑕疵,和lifegame那会儿访问越界类似,很好解决,然后顺序完成了搜索单词的工作,应该把?至少搜出来了

仔细检查了一下搜出来的结果,发现搜出了奇怪的单词,面板上并没有,😓,怎么回事捏?

Debug
第一次进入递归时传入了word = “”导致没有访问当前的第一个字母,小问题。
访问过的字母需要设置为visited,如果单词没有成立再撤回
大问题是会搜出不存在的单词,继续De

找到了,传参时将word 赋值为 word + board[i][j + 1] 之类的,并且传入了i,j
作为索引,然鹅i,j没有同步整张,导致每次word都连接了相同的字母;另外,三个方向的递归函数全放在了一起,导致纵向的执行了一次后又去执行向右侧访问的操作,导致非法词汇出现。

解决方案比较简单,在进入递归前确认方向即可,用int flag = 0确认,每次改变方向时+1,用flag的值选择方向。

不需要设置visited集合,因为你不知道用户会选择哪种单词组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void findWordsHelper(Set<string> &allWords, Grid<char> &board, string word, int i, int j, int dimension, int flag, Lexicon &DIC) {

// base case: 单词正确/访问出界
if (i + 1 >= dimension || j + 1 >= dimension) {
flag++; // 改变下轮递归方向
return;

} else if (!DIC.containsPrefix(word)) {
// 剪枝 Lexion containPrefix()
return;
} else {
// rec case
if (DIC.contains(word)) {
allWords.add(word);
}

// exploer
// [i][j] visited NO NEED
// board[i][j]

if (flag == 0) { // 向右侧递归
findWordsHelper(allWords, board, word + board[i][j + 1], i, j + 1, dimension, flag, DIC); // i, j 作为单词的下一字母索引同步增加
} else if (flag == 1) { // 向下
findWordsHelper(allWords, board, word + board[i + 1][j], i + 1, j, dimension, flag, DIC);
} else { // 斜向右下
findWordsHelper(allWords, board, word + board[i + 1][j + 1], i + 1, j + 1, dimension, flag, DIC);
}


// unchoose NO NEED
}
}

void findWords(Set<string> &allWords, Grid<char> &board, string word, int dimension,Lexicon &DIC) {
for (int i = 0; i < dimension; i++) {
for (int j = 0; j < dimension; j++) {
word = board[i][j];
int flag = 0;
findWordsHelper(allWords, board, word, i, j, dimension, flag, DIC);
}
}
}

// 递归列出单词
Set<string> getAllWords(Grid<char> &board, int dimension, Lexicon &DIC) {
Set<string> allWords;
string word = "";
findWords(allWords, board, word, dimension, DIC);
return allWords;
}

递归部分完成,剩下的不想做了,躺平……
没办法嘛,时间太少,后面的内容又很好玩,等不及了😋
好像还不太行,看了一下demo,差的太远了,再改改

4月末


以下为7月更新部分

改动一下代码展示风格

我个人不公开代码的另一个原因,是我认为我的代码实现并不那么优秀,虽然能够通过测试,但还是有很多不足,不敢放到大家面前。私底下我们可以对着题目分享思路,可以对着看看各自的实现方式;放到自己的博客上可以介绍自己对题目的理解,实现的技巧,部分代码的摘要;如果别人有疑问,尝试点出或者和他一起解决…

中途做web开发和备考耽搁太长时间,决定推倒重做,阅读start code 发现很多以前忽略的地方,尤其是接口部分。

分析功能,给出以下逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 根据用户选项生成随机词盘,并生成所有可能的词放入词典中 使用新函数
Grid<char> board = initBoard(dimension);
Set<string> words = initWords(board);
Set<string> visited;
// 当玩家为人类时,输入的单词在词典中且为合法新词,则高亮并积分,否则展示对应报错
// 当输入为空时切换玩家为计算机
// 计算机回合直接展示所有(#`O′)未被找出的单词
Player currentP = HUMAN;
while (currentP == HUMAN) {
string wordinput = getLine("Enter a word: ");
if (words.contains(wordinput) && !visited.contains(wordinput)) {
// highlight record visited
continue;
} else if (words.contains(wordinput) && visited.contains(wordinput)) {
// 重复输入
continue;
} else if (!words.contains(wordinput) && strlen(wordinput) > 3) {
// 不存在,错词
continue;
} else if (strlen(wordinput) < 4 && strlen(wordinput) > 0) {
// 长度小于4
continue;
} else {
// 空输入?
currentP = COMPUTER;
}
}

使用strlen时注意将string类型转为c语言支持的类型,使用.c_str()方法。
另外,如果右括号左有0会导致编译器(Qt)抽风ecpected token ) got 0

创建board

1
2
3
4
5
6
7
8
9
10
/**
* Function: initBoard
* -------------------
* 初始化board,设置字符并绘制
*/

static Grid<char> initBoard(int dimension) {
Grid<char> board(dimension, dimension);
return board;
}

这种返回值的方法为什么可行?根据大括号来看,board在这个函数结束的时候就已经被销毁了,如何将其传递到主函数?
GIthub copilot:你提到的 board 在函数结束时被销毁的问题是因为 board 是在栈上分配的局部变量。然而,initBoard 函数返回的是一个 Grid 对象的副本,而不是对局部变量的引用。因此,返回的副本在主函数中仍然是有效的。

真的每一步都有坑,给定的骰子是字符串常量,在洗牌前需要将其存入变量中。然后打乱骰子,见上。

递归找出所有单词

接下来就是最关键的初始化词典部分。需要使用递归。找出所有符合的单词。怎么办呢?我们先从一个字符出发:假设一个4乘4的字符格。每一个字符都应该向右寻找,向下寻找,向左下,右下方寻找。并且完成对应的剪枝操作。另外,当一个词成立的时候,还需要将其设置flag。并按照这个flag,使用递归进行高亮。

关键问题来了。怎么实现单词查找呢?先假设一个4x4的网格。然后我的意思是2x2的网格。然后里面的单词分别是”BOOK”。怎么样才能找到这个词呢?我们的递归函数传入这个矩阵。我们从第一个字母开始,它需要去找所有相邻的字母。我大概有思路了,因为我会用回溯法。不断地向左上角去找。当所有的左上角访问完,再访问上。当倒数第二层的左上角的字母都被遍历完以后,退回一级。再访问退回后的那个点的下一个字。
我悟了。单词需要向上不断查找,也需要向右不断查找。不,不对。这样只能查找到与其在同一行、同一列的单词,以及对角线上的单词,不能拐弯。
我又悟了。每一次递归函数都会向当前位置周围的八个方向去访问,这有点像广度优先搜索。不过我们这一次的精髓是深度优先搜索。因为每一次搜索都会向八个方向扩展,并且避免已经访问过的位置。那样的话,所有的可能情况都被覆盖了。是吗?假设是个2x2方格,分别是”BOOK”。B向左访问到O。向左上也访问到O。呃,向左上方访问到C。那这样一来,它只能生成”BO”和”BK”两个词。嗯,就这样。

backtracking

这里插入一些回溯法的练习,不然太懵了,什么都不知道。

给定两个整数 nk,返回范围 [1, n] 中所有可能的 k 个数的组合。

果然不懂还得回去看课,花半天时间跟着把递归的题练了一手,补习了不少思路。每次递归都向8个方向递归的思路是对的,比如上层是0,本层递归走向为0,1则下一层就有000,001,010,011.就能覆盖所有的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static void initWordsHelper(Lexicon &dic, Set<string> &words, Grid<char> &board, string formed,
int i, int j, Grid<int> &visited) {
for (int ni = -1; ni < 2; ni++) {
for (int nj = -1; nj < 2; nj++) {
int x = i + ni, y = j + nj;
if (x < 0 || x >= board.size() || y < 0 || y >= board.size()) {
continue;
}
if (dic.contains(formed)) {
words.add(formed);
} else if (dic.containsPrefix(formed)) {
continue;
}

if (visited[x][y] == 1) {
continue;
}
visited[x][y] = 1;
initWordsHelper(dic, words, board, formed + board[x][y], i, j, visited);
visited[x][y] = 0;

}
}
}

debug一整天,最后发现控制越界时获取数组宽度的函数调成获取元素总数的了… danm!

参考

最后总算搞明白回溯法递归的实现了,真的抽象。期间查阅了不少视频和文档:
代码随想录-回溯法
CodeStepByStep–backtracking
以及做主要的还是CS106x的lecture7~12,花了半天时间回顾了从最简单的阶乘到n皇后问题。