书名:算法超简单:趣味游戏带你轻松入门与实践
ISBN:978-7-115-63961-5
本书由人民邮电出版社发行数字版。版权所有,侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用,未经授权,不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟,与我们共同保护知识产权。
如果购买者有侵权行为,我们可能对该用户实施包括但不限于关闭该帐号等维权措施,并可能追究法律责任。
著 童 晶
责任编辑 龚昕岳
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线:(010)81055410
反盗版热线:(010)81055315
本书通过趣味游戏编程讲解算法,提升读者学习算法的兴趣,降低读者学习算法的难度,增强读者将算法应用于编程实践的能力。
本书共14章,通过猜数字、飞翔的小鸟、得分排行榜、汉诺塔、八皇后、消灭星星、贪吃蛇、走迷宫、连连看、吃豆人、滑动拼图、井字棋、垒积木、十步万度等游戏,讲解顺序查找算法、二分查找算法,图形库EasyX,插入排序算法、冒泡排序算法、选择排序算法、快速排序算法,递归算法,暴力搜索算法、回溯算法,FloodFill算法,常见的数据结构(数组、链表、队列、栈、图、树)、标准模板库(STL),十字分割算法、广度优先搜索算法、深度优先搜索算法,加权图上的迪杰斯特拉算法、贪婪最佳优先搜索算法、A*算法,状态空间上的搜索算法,博弈树的极大极小值搜索算法、α-β剪枝搜索算法,动态规划算法,遗传算法。
本书适合想要学习基础算法或练习编程实践的读者阅读,也可作为高等院校数据结构与算法相关课程或编程实践课程的指导用书。读者在阅读本书之前需要具备基础的C语言编程知识。
算法对于编程开发非常重要。然而,在学习算法的过程中,许多人看了大量的公式、伪代码、流程图后,还是很难真正理解算法的内涵,在具体编程时无从下手,甚至觉得算法枯燥、无聊、难以理解。
对于算法学习,如果读者能看到图形化的画面、编出好玩的游戏,自然会感到有趣、有成就感,进而就会自己钻研、与他人积极交流,学习效果也会得到显著提升。
因此,本书把趣味游戏应用于算法教学,并通过可视化的形式,帮助读者快速理解算法的核心思想,掌握算法在实际项目开发中的作用,使读者能够利用算法做出酷炫的图形交互式游戏。
本书中的游戏项目都经过了作者的精心设计,并且作者在高校授课时对这些游戏项目进行了反复验证和优化。本书详细讲解了这些游戏项目的分步骤实现过程,并提供对应的配套源代码和运行效果视频,适合初学者学习。
本书共14章,每章通过一个趣味游戏编程项目讲解算法、数据结构或库应用,提升读者学习算法的兴趣,降低读者学习算法的难度,增强读者将算法应用于编程实践的能力,并在一些章中提供拓展练习。本书的内容结构如下。
章 |
游戏项目 |
知识内容 |
拓展练习 |
---|---|---|---|
第1章 |
猜数字 |
顺序查找算法,二分查找算法,分析算法效率的大O表示法 |
|
第2章 |
飞翔的小鸟 |
图形库EasyX的安装与使用 |
|
第3章 |
得分排行榜 |
插入排序算法,冒泡排序算法,选择排序算法,快速排序算法 |
顺序查找、二分查找、堆排序、归并排序、计数排序、桶排序算法的可视化 |
第4章 |
汉诺塔 |
递归算法 |
绘制分形树 |
第5章 |
八皇后 |
暴力搜索算法,回溯算法 |
一笔画游戏、数独游戏 |
第6章 |
消灭星星 |
FloodFill算法 |
扫雷游戏 |
第7章 |
贪吃蛇 |
常见数据结构(数组、链表、队列、栈、图、树),标准模板库(Standard Template Library,STL)的使用方法 |
飞机大战 |
第8章 |
走迷宫 |
十字分割算法,图的广度优先搜索算法、深度优先搜索算法 |
|
第9章 |
连连看 |
图的广度优先搜索算法 |
围住神经猫 |
第10章 |
吃豆人 |
加权图上的迪杰斯特拉算法、贪婪最佳优先搜索算法、A*算法 |
|
第11章 |
滑动拼图 |
状态空间上的搜索算法 |
农夫过河游戏 |
第12章 |
井字棋 |
博弈树的极大极小值搜索算法,α-β剪枝搜索算法 |
人机对战五子棋 |
第13章 |
垒积木 |
递归回溯算法、动态规划算法 |
|
第14章 |
十步万度 |
遗传算法 |
本书每章的开头会介绍该章的游戏项目和将要学习的算法。读者可以先从配套资源中观看对应的视频、运行最终的游戏项目程序代码,直观地了解本章的学习目标。
本书中的算法教学和游戏项目会分成多个步骤,从零开始一步一步实现。书中会列出每个步骤的实现目标、实现思路、相应的参考代码,以及项目运行视频。读者可以先在前一个步骤代码的基础上,尝试自己写出下一个步骤的代码,碰到困难时可以参考本书配套资源中的示例代码。
书中提供了一些趣味拓展练习,读者可以先自己实践,再参考本书配套资源中给出的代码。读者也可以根据自己的兴趣进行拓展开发。
本书提供所有游戏项目的分步骤代码、拓展练习的参考代码、图片素材、演示视频、配套教学PPT,读者可以从异步社区官网的本书主页中下载。
本书适合有一定编程基础、想进一步学习算法的读者阅读。
本书也适合对计算机游戏感兴趣的读者阅读,学习多种类型游戏的开发方法。
本书可以作为程序设计、算法、数据结构、游戏开发等课程的实践指导用书,也可作为课程大作业或毕业设计的参考案例用书,还可以作为大学生ACM程序设计竞赛、中学生信息学奥林匹克竞赛的入门图书。
本书提供如下资源:
● 本书配套源代码;
● 本书示例视频演示;
● 本书配套教学PPT;
● 本书思维导图;
● 程序员面试手册电子书;
● 异步社区7天VIP会员。
要获得以上资源,您可以扫描下方二维码,根据指引领取。
作者和编辑尽最大努力来确保书中内容的准确性,但难免会存在疏漏。欢迎您将发现的问题反馈给我们,帮助我们提升图书的质量。
当您发现错误时,请登录异步社区(https://www.epubit.com),按书名搜索,进入本书页面,单击“发表勘误”按钮,输入错误信息,然后单击“提交勘误”按钮即可(见右图)。本书的作者和编辑会对您提交的勘误进行审核,确认并接受后,您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议,请您发邮件给我们,并请在邮件标题中注明本书书名,以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频,或者参与图书翻译、技术审校等工作,可以发邮件给我们。
如果您所在的学校、培训机构或企业想批量购买本书或异步社区出版的其他图书,也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为,包括对图书全部或部分内容的非授权传播,请您将怀疑有侵权行为的链接通过邮件发送给我们。您的这一举动是对作者权益的保护,也是我们持续为您提供有价值的内容的动力之源。
“异步社区”是由人民邮电出版社创办的IT专业图书社区,于2015年8月上线运营,致力于优质内容的出版和分享,为读者提供高品质的学习内容,为作译者提供专业的出版服务,实现作译者与读者的在线交流互动,以及传统出版与数字出版的融合发展。
“异步图书”是异步社区策划出版的精品IT图书的品牌,依托于人民邮电出版社在计算机图书领域30余年的发展与积淀。异步图书面向IT行业以及其他行业的IT用户。
在本章中,我们首先实现一个猜数字的小游戏,如图1-1所示。接着,我们将学习顺序查找算法、二分查找算法,并对使用这两种查找算法求解的过程进行可视化。最后,我们将这两种算法应用于猜数字游戏,观察它们的查找效率,初步体会算法的威力。
图1-1
下面我们用C语言实现一个小游戏。计算机随机生成1到100之间的一个整数,让用户来猜这个数字。当用户猜测的数字大于或小于计算机生成的数字时,计算机会输出提示信息;当猜对时,游戏胜利。
游戏的实现代码如1-1.cpp所示,运行效果参见图1-2,扫描右侧二维码观看视频效果“1.1实现猜数字游戏”。
1.1 实现猜数字游戏
1-1.cpp
1 #include <stdio.h>
2 #include <conio.h>
3 #include <stdlib.h>
4 #include <time.h>
5
6 int main() // 主函数
7 {
8 srand((unsigned)time(NULL)); // 初始化随机种子
9 int num = 1 + rand() % 100; // 生成1到100之间的随机整数
10 printf("计算机生成了一个1-100之间的随机整数,请猜猜是什么数字?\n");
11 int guess; // 存储用户猜的数字
12 scanf_s("%d", &guess); // 用户输入数字
13 while (guess != num) // 当用户没有猜对时,循环执行
14 {
15 if (guess > num)
16 printf("数字猜大了,请再猜一次吧。\n");
17 else if (guess < num)
18 printf("数字猜小了,请再猜一次吧。\n");
19 scanf_s("%d", &guess); // 用户再次输入数字
20 }
21 printf("恭喜你,猜对了!\n");
22 _getch();
23 return 0;
24 }
图1-2
提示 本书使用Visual Studio 2022社区版作为集成开发环境,读者可以在线搜索并免费下载安装。本书中游戏项目的工程文件和源代码可以从异步社区官网的本书主页中下载。
猜数字游戏的策略可以转换为不同的查找算法。首先,我们学习最简单的顺序查找算法。假设要在图1-3所示的数组中查找数字7。
图1-3
顺序查找算法首先检查数组中的第一个元素5,将之与待查找数字7进行比较,如图1-4所示。如果相等,则查找结束;如果不等,则继续向右查找。
图1-4
5不等于7,继续比对第二个元素,如图1-5所示。
图1-5
1不等于7,继续向右查找,直到找到数字7,查找结束,如图1-6所示。
图1-6
假设数组nums中存储了n个数字,变量key中存储要查找的数字。顺序查找算法从数组nums中的第一个元素开始,依次与变量key进行比较;直至找到相等的元素,循环停止。顺序查找算法的伪代码如下。
1 for i从0到n-1
2 if nums[i]==key
3 查找成功,结束for循环
4 if i==n
5 查找失败
顺序查找算法的完整代码如1-2-1.cpp所示。
1-2-1.cpp
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <conio.h>
4 #include <time.h>
5
6 int main() // 主函数
7 {
8 srand((unsigned)time(NULL)); // 初始化随机种子
9 int nums[100]; // 数组存储多个数字
10 int i;
11
12 // 数组元素初始化为1到100
13 for (i = 0; i < 100; i++)
14 nums[i] = 1 + i;
15
16 // 随机交换数组中元素的顺序
17 for (i = 0; i < 50; i++)
18 {
19 int ri = rand() % 100; // 第1个数字的索引
20 int rj = rand() % 100; // 第2个数字的索引
21 // 交换数组中这两个数字的顺序
22 int temp = nums[ri];
23 nums[ri] = nums[rj];
24 nums[rj] = temp;
25 }
26
27 printf("随机数组为:");
28 for (i = 0; i < 100; i++)
29 printf("%4d", nums[i]);
30 printf("\n");
31
32 // 生成要查找的数字,为1到100之间的随机整数
33 int key = 1 + rand() % 100;
34
35 // 以下开始顺序查找
36 for (i = 0; i < 100; i++)
37 {
38 if (key != nums[i])
39 {
40 printf("%d:%d不是要查找的数字\n", i, nums[i]);
41 }
42 else
43 {
44 printf("%d:查找到了,%d是要查找的数字\n", i, nums[i]);
45 break; // 终止for循环
46 }
47 }
48 if (i == 100)
49 printf("没有找到数字%d\n", key);
50 _getch();
51 return 0;
52 }
1-2-1.cpp的运行效果如图1-7所示。
图1-7
为了展示顺序查找算法的动态过程,可以利用Sleep()函数暂停若干毫秒,利用system("cls")清空画面,利用SetConsoleTextAttribute()设置字符显示不同的颜色,如代码1-2-2.cpp所示。
1-2-2.cpp
1 #include <stdio.h>
2 #include <windows.h>
3 #include <conio.h>
4 int main()
5 {
6 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 8);
7 printf("已查找过的显示为灰色\n");
8
9 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4);
10 printf("正在查找的显示为红色\n");
11
12 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
13 printf("未查找的显示为白色\n");
14
15 Sleep(5000); // 暂停
16 system("cls"); // 清空画面
17
18 _getch();
19 return 0;
20 }
运行代码1-2-2.cpp后,首先输出不同颜色的字符,如图1-8所示,5秒后清除所显示的内容。
图1-8
将1-2-2.cpp和1-2-1.cpp结合,即可实现对顺序查找算法的动态过程的可视化,如代码1-2-3.cpp所示,运行效果参见图1-9,扫描下方二维码观看视频效果“1.2 顺序查找”。
图1-9
1.2 顺序查找
1-2-3.cpp
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <conio.h>
4 #include <time.h>
5 #include <windows.h>
6
7 #define LEN 100
8
9 int main() // 主函数
10 {
11 srand((unsigned)time(NULL)); // 初始化随机种子
12 int nums[LEN]; // 数组存储多个数字
13 int i;
14
15 // 数组元素初始化为1到100
16 for (i = 0; i < LEN; i++)
17 nums[i] = 1 + i;
18
19 // 随机交换数组中元素的顺序
20 for (i = 0; i < 50; i++)
21 {
22 int ri = rand() % 100; // 第1个数字的索引
23 int rj = rand() % 100; // 第2个数字的索引
24 // 交换数组中这两个数字的顺序
25 int temp = nums[ri];
26 nums[ri] = nums[rj];
27 nums[rj] = temp;
28 }
29
30 // 生成要查找的数字,为1到100之间的随机整数
31 int key = 1 + rand() % LEN;
32 int id = 0; // 当前查找到的数组元素的索引
33
34 // 以下开始顺序查找
35 for (id = 0; id < LEN; id++)
36 {
37 Sleep(100); // 暂停100毫秒
38 system("cls"); // 清空画面
39 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); // 白色
40 printf("在数组中查找:%d\n", key);
41
42 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 8); // 灰色
43 // 已经查找过的元素显示为灰色
44 for (i = 0; i < id; i++)
45 printf("%4d", nums[i]);
46
47 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4); // 红色
48 // 正在被查找的元素显示为红色
49 printf("%4d", nums[id]);
50
51 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); // 白色
52 // 还没有被查找的元素显示为白色
53 for (i = id + 1; i < LEN; i++)
54 printf("%4d", nums[i]);
55 printf("\n查找次数:%d次\n", id);
56
57 if (key == nums[id])
58 break; // 查找到了,跳出for循环语句
59 }
60 _getch();
61 return 0;
62 }
对于有序数组,可以采用更高效的二分查找策略。假设要在图1-10所示的数组中查找数字6。
图1-10
首先,将所需查找的数字6和数组正中间位置的元素5进行比较,如图1-11所示。
图1-11
由于6大于5,因此5及其左边的数字均不需要再考虑,可以将查找范围缩减一半,如图1-12所示。
图1-12
继续将所需查找的数字6和剩余元素中正中间位置的8进行比较,如图1-13所示。
图1-13
由于8大于6,因此8及其右边的数字均不需要再考虑,如图1-14所示。
图1-14
继续和剩余元素中正中间位置的6进行比较,发现6即为所查数字,查找结束,如图1-15所示。
图1-15
假设有序数组nums中存储了n个数字,变量key存储要查找的数字。二分查找算法比较key和数组nums正中间位置的元素值,如果key更大,则只需在数组nums右边一半的元素中查找;如果key更小,则只需在数组nums左边一半的元素中查找。重复执行上述逻辑,即可很快查找到目标。二分查找算法的伪代码如下。
1 low = 0
2 high = n - 1
3 while low <= high
4 mid = (low + high)/2
5 if key == nums[mid]
6 查找成功,跳出循环
7 if key < nums[mid]
8 high = mid - 1
9 if key > nums[mid]
10 low = mid + 1
11 if low > high
12 查找失败
二分查找算法的完整代码如1-3-1.cpp所示。
1-3-1.cpp
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <conio.h>
4 #include <time.h>
5
6 int main() // 主函数
7 {
8 srand((unsigned)time(NULL)); // 初始化随机种子
9 int nums[100]; // 数组存储多个数字
10 int i;
11
12 // 数组元素初始化为1到100
13 for (i = 0; i < 100; i++)
14 nums[i] = 1 + i;
15
16 printf("有序数组为:");
17 for (i = 0; i < 100; i++)
18 printf("%4d", nums[i]);
19 printf("\n");
20
21 // 生成要查找的数字,为1到100之间的随机整数
22 int key = 1 + rand() % 100;
23 int searchNum = 0; // 查找的次数
24 // 定义变量:查找区域的下边界、上边界、正中间
25 int low = 0, high = 100 - 1, mid;
26
27 // 以下进行二分查找
28 while (low <= high)
29 {
30 searchNum++; // 查找次数加1
31 mid = (low + high) / 2; // 正中间元素的序号
32 if (key == nums[mid]) // 找到了
33 {
34 printf("%d:查找到了,%d是要查找的数字\n", searchNum, nums[mid]);
35 break; // 跳出while循环语句
36 }
37 else
38 {
39 printf("%d:%d不是要查找的数字\n", searchNum, nums[mid]);
40 // 更新查找区域,变成上一步的一半
41 if (key < nums[mid]) // 下一次查找较小的一半数组
42 high = mid - 1;
43 else // 下一次查找较大的一半数组
44 low = mid + 1;
45 }
46 }
47 if (low > high) // 没有找到要查找的数字
48 printf("没有找到要查找的数字%d\n", key);
49 _getch();
50 return 0;
51 }
1-3-1.cpp的运行效果如图1-16所示。
图1-16
将1-2-2.cpp和1-3-1.cpp结合,即可实现对二分查找算法的动态过程的可视化,如代码1-3-2.cpp所示,运行效果参见图1-17,扫描右侧二维码观看视频效果“1.3 二分查找”。
1.3 二分查找
(a)第一次查找,未找到
(b)第二次查找,未找到
(c)第三次查找,未找到
(d)第四次查找,未找到
(e)第五次查找,未找到
(f)第六次查找,找到了
图1-17
1-3-2.cpp
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <time.h>
4 #include <conio.h>
5 #include <windows.h>
6
7 #define LEN 100
8
9 // 自定义函数,输出显示当前查找状态
10 // nums为要查找的数组,statuses记录数组元素的颜色,searchNUM为查找次数,
key为要查找的数值
11 void showArrays(int nums[], int statuses[], int searchNUM, int key)
12 {
13 int i;
14 Sleep(1000); // 暂停
15 system("cls"); // 清空画面
16 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); // 设为白色
17 printf("在数组中查找:%d\n", key); // 输出白色提示文字
18
19 // 显示当前状态
20 for (i = 0; i < LEN; i++)
21 {
22 // 设为不同的颜色
23 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), statuses[i]);
24 printf("%4d", nums[i]); // 输出对应的数组元素
25 }
26 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); // 设为白色
27 printf("\n查找次数:%d次\n", searchNUM); // 输出白色提示文字
28 }
29
30 int main() // 主函数
31 {
32 srand((unsigned)time(NULL)); // 初始化随机种子
33 int nums[LEN]; // 要查找的数组
34 int i;
35
36 // 数组元素初始化为1到100
37 for (i = 0; i < LEN; i++)
38 nums[i] = 1 + i;
39
40 // 根据查找状态设定颜色,未查找的数字显示为白色(7),已查找过的数字
显示为灰色(8),正在查找的数字显示为红色(4)
41 int statuses[LEN];
42 for (i = 0; i < LEN; i++)
43 statuses[i] = 7; // 初始全是未查找的数字,显示为白色(7)
44
45 // 生成要查找的数字,为1到100之间的随机整数
46 int key = 1 + rand() % LEN;
47 int id = 0; // 当前查找到的数组元素的索引
48
49 // 定义变量:查找区域的下边界、上边界、正中间
50 int low = 0, high = LEN - 1, mid = (low + high) / 2;
51 int searchNUM = 0; // 查找的次数
52
53 // 以下开始二分查找
54 while (low <= high)
55 {
56 mid = (low + high) / 2; // 正中间元素的序号
57
58 if (key != nums[mid]) // 当前元素不是目标
59 {
60 if (key < nums[mid]) // 下一次查找较小的一半数组
61 high = mid - 1;
62 else // 下一次查找较大的一半数组
63 low = mid + 1;
64 }
65
66 searchNUM++; // 查找次数加1
67 statuses[mid] = 4; // 设置正在查找的元素为红色
68 showArrays(nums, statuses, searchNUM, key); // 显示当前查找状态
69
70 for (i = 0; i < LEN; i++)
71 statuses[i] = 8; // 将数组中所有元素设为灰色
72 for (i = low; i <= high; i++)
73 statuses[i] = 7; // 将下一步要查找范围中的元素设为白色
74
75 if (key != nums[mid]) // 如果没有找到
76 statuses[mid] = 8; // 当前元素设为灰色,表示查找过了
77 else // 如果找到了
78 statuses[mid] = 4; // 当前元素设为红色,表示找到了
79 showArrays(nums, statuses, searchNUM, key); // 显示当前查找状态
80
81 if (key == nums[mid]) // 如果找到了
82 break; // 跳出循环
83 }
84 _getch();
85 return 0;
86 }
回到猜数字游戏,要猜1到100之间的随机整数,可以采用顺序查找算法,即从小到大依次猜,直到猜对为止。最坏的情况下,要猜100次才能猜对。
如果采用二分查找算法,每次猜中间的数值,依次将查找范围减半,则对于长度为100的数组,最坏的情况下,查找范围依次为100、50、25、12、6、3、1,因此最多7次(log2100向上取整)就能猜对。
推广开来,如果数组大小为n,顺序查找最多需要猜n次,二分查找最多需要猜log2n次。表1-1列出了不同数据规模下,两种查找算法的效率。数据规模越大,二分查找算法的效率优势越明显。
表1-1
数据规模 |
10 |
100 |
1000 |
10000 |
100000 |
1000000 |
n |
---|---|---|---|---|---|---|---|
顺序查找算法的效率 |
10 |
100 |
1000 |
10000 |
100000 |
1000000 |
n |
二分查找算法的效率 |
4 |
7 |
10 |
14 |
17 |
20 |
log2n |
算法的效率通常使用大O表示法来描述。比如顺序查找算法的时间复杂度记为O(n),表示对规模为n的数据执行顺序查找算法的最长运行时间为n的常数倍。二分查找算法的效率可以记为O(log2n),表示对规模为n的数据执行二分查找算法的最长运行时间为n的对数函数。
还有一种比二分查找更快的查找算法,那就是哈希查找,也称为散列查找。哈希查找通过将关键字映射到哈希表中的索引位置来快速定位目标数据,其时间复杂度为O(1)。
本章主要讲解了顺序查找算法和二分查找算法,并将其应用于猜数字游戏中。对算法的执行过程进行可视化,有利于对算法的理解。
在第2章,我们将学习图形的绘制,并在第3章的拓展练习中实现查找算法的图形可视化。