算法题——Cantor表

题目介绍

描述

现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的:

1/1, 1/2 , 1/3, 1/4, 1/5, …

2/1, 2/2, 2/3, 2/4, …

3/1, 3/2, 3/3, …

4/1, 4/2, …

5/1, …

我们以Z字形给表上每一项编号。第一项是1/1,然后是1/2, 2/1, 3/1, 2/2, …

输入格式

整数N(1<= N <=10^7)

输出格式

表中的第N项

样例

输入:

1
7

输出:

1
1/4

分析

规律

我们通过题目可知,在Cantor表中走法为Z字形

不妨将Cantor表转化为下图

Cantor

从左往右数

奇数行分母依次递增,分子依次递减

偶数行分母依次递减,分子依次递增

可知奇偶数行分子分母规律正好相反

所以为使奇偶数行变化规律一致并且符合题中所给的项数规律,我们可以规定

在上图中,奇数行从左往右数,偶数行从右往左数

找查

例如我们要找查第7项,前三行一共有6项,前4行一共有10项

很显然 6 < 7 < 10

所以我们可以很方便地确定第7项在第4行

前几行项数 - 所要找的项数 = 所要找的项所在行的最后一项分子 - 所找项分子

同理

前几行项数 - 所要找的项数 = 所找项分母 - 所找项所在行最后一项分母

这两个等式中我们分别知道任意三个量就可以求其中的第四个量

然后,我们继续根据规律确定第7项的具体的值为 1/4

最后,我们可以轻易得出求任意项的算法如下

解法

以下是笔者的解题方法

先上代码

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
#include <iostream>
using namespace std;

int main()
{
int n = 0, sum = 0, i = 1;
cin >> n;

while(sum < n)
{
++i; //这里一定要让i先自增再求和,否则求出来的和少一项(此处的项指的是等差数列的项)
sum = i*(i - 1)/2; //首项公差均为1的等差数列求和,此处的和为第i行为止的Cantor表的总项数
}

//总项数与所找项的项数的差
int dif = sum - n;

if((i - 1) % 2 != 0)
//如果i-1行为奇数,那么i行为偶数行,偶数行从右开始数(这里在写的时候绕了个弯)
cout << 1 + dif << "/" << i - 1 - dif;
else
//第i行为奇数行,从左边数
cout << i - 1 -dif << "/" << 1 + dif;

}

链表的定义

链表

链表的概念

定义链表是一种物理存储单元上非连续、非顺序的存储结构,由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。

在链表的储存上,每个结点不仅包含所存的元素信息,还包含元素间的逻辑信息

链表的特性

  • 不支持随机访问不能通过知道第一个元素的地址(即储存空间的首地址)可以轻松访问储存的所有数据。
  • 节点的储存空间利用率相对顺序表较低:链表中的每分一个结点需要划出一部分空间来储存指向下一个结点位置指针
  • 支持储存空间的动态分配:链表中当前结点的位置是由其前驱结点中的地址信息所指示的。其结点可以散落在内存中的任意位置,且不需要一次性地划分所有结点所需的空间给它。
  • 在链表中进行插入操作无需移动元素(而顺序表需要)

链表的形式

单链表

在每个结点除了包含的数据域外,还包含一个指针域,用以指向其后继结点。

  • 带头结点的单链表

带头结点的单链表中,头指针head指向头结点,头结点的值域不含任何信息,从头结点的后继结点开始储存信息。头指针head 始终不等于NULLhead->next等于NULL的时候,链表为空。

带头节点的单链表(图片来自网络)

  • 不带头结点的单链表

不带头结点的单链表中的头指针head直接指向开始结点,当head等于NULL时,链表为空。

不带头节点的单链表

双链表

双链表就是在单链表结点上增添了一个指针域,指向当前节点的前驱

相比于单链表,双链表能够从终端结点反向走到开始结点

双链表(图片源自网络)

循环链表

  • 循环单链表

只需要将单链表最后一个指针域(空指针)指向链表中的第一个结点即可。(如果循环单链表带头结点,则指向头结点;不带头结点,则指向开始结点)。

循环单链表可以实现从任何一个结点出发,访问链表中任何结点。(注意:此处应该区分与顺序表随机访问的特点。循环单链表指的是从一个结点出发,而不是知道一个结点从而迅速找到任何一个结点,因此循环单链表不具有随机访问特性。)

带头结点的循环单链表,当head等于head->next时,链表为空;不带头结点的循环单链表,当head等于NULL时,链表为空。

  • 循环双链表

双链表终端节点的next指针指向链表中第一个结点,将链表中的第一个结点的prior指针指向终端结点。

不带头结点的循环双链表,head等于NULL,链表为空

带头结点的循环双链表是没有空指针的,其为空状态下,head->nexthead->prior必然都等于head,故一下四种语句都可判断为空

1
2
3
4
head->next == head;
head->prior == head;
head->next == head && head->prior == head;
head->next == head || head->prior == head;

静态链表

静态链表借助一维数组表示。

静态链表结点空间来自于一个结构体数组(一般链表结点空间来自整个内存),数组中每个结点含两个分量:

  • 数据元素分量data
  • 指针分量(指示了当前结点直接后继节点在数组中的位置)

注意:静态链表的指针不是通常所说储存内存地址的指针型变量,而是储存数组下标的整型变量,其功能类似于指针,故在此称为指针

顺序表与链表区别

基于空间比较

  • 储存的分配方式

顺序表储存空间时一次性分配的,链表的是多次分配的

  • 存储密度

(注: 存储密度 = 结点值域所占存储量/结点结构所占存储总量

顺序表存储密度 = 1

链表存储密度 < 1

基于时间的比较

  • 存取方式

顺序表可以随机存取,也可以顺序存取

链表只能顺序存取

  • 插入/删除时移动元素个数

顺序表平均需要移动一半元素

链表不需要移动元素,仅需修改指针

顺序表的操作

顺序表的操作

这里先定义个顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>

using namespace std;

#define MAXSIZE 100

typedef struct{
int *elems;
int length;
int size;
}Sqlist;

Sqlist list;

顺序表初始化

  • 定义bool类型函数 initList() ,初始化成功为true,失败为false
1
2
3
4
5
6
7
8
9
10
11
//初始化顺序表,创建一个空表
bool initList(Sqlist &L) //L本身要改变所以为引用型
{
L.elems = new int[MAXSIZE]; //为顺序表分配内存空间
if(!L.elems) return false; //存储分配失败返回false

//分配成功则初始化
L.length = 0;
L.size = MAXSIZE;
return true; //成功并返回true
}
  • 定义函数 outputInfoList() 用于输出顺序表信息
1
2
3
4
5
6
7
8
9
//输出数据表信息
void outputInfoList(Sqlist &L)
{
cout << "顺序表储存空间" << L.size << ",已经保存元素个数" << L.length << endl;
for(int i = 0; i <= L.length - 1;i++){
cout << L.elems[i] << " ";
}
cout << endl;
}

找查元素

  • 定义函数 findElem() 在顺序表中找查一个等于e的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* 用于找查顺序表中的元素
* 参数e为要找查的元素
* 若找到则返回元素下标
* 若没找到则返回-1
*/
int findElem(Sqlist L, int e) //这里我们不改变L,所以不用引用类型
{
for(int i = 0; i < L.length; i++){
if(e == L.elems[i])
return i; //若找到则返回元素下标
}
return -1; //若没找到则返回-1
}

插入元素

尾部添加元素

在尾部添加元素要考虑以下几点

  • 顺序表是否已满
  • 添加成功后长度要加1
  • 故定义函数 listAppend()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* 在顺序表尾部插入元素
* 参数e为要插入到尾部的元素
* 若成功则返回true,失败(顺序表已经满了)则返回false
*/
bool listAppend(Sqlist &L, int e)
{
if(L.length == L.size)
//顺序表满了
return false;
//没满则尾部插入元素并返回true
L.elems[L.length] = e;
L.length++;
return true;
}

在特定位置插入元素

在特定位置插入要考虑以下几点

  • 顺序表是否已满
  • 添加成功后长度要加1
  • 要移动后面的元素而不能移动前面的元素,否则后面的元素会被前面的覆盖

定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//在顺序表p位置(0 <= p <= length)上插入元素e
bool insertElem(Sqlist &L, int p, int e)
{
if(p < 0 || p > L.length || L.length == MAXSIZE)
/*
* 如果位置错误
* 或者表长已经达到最大允许值
* 此时插入不成功并返回false
*/
return false;
for(int i = L.length - 1; i >= p; --i)
//从后往前将元素相后方移动一个位置
L.elems[i+1] = L.elems[i];
L.elems[p] = e; //插入元素e到p位置
L.length++;

return true; //成功返回true
}

删除元素

删除元素要考虑以下几点

  • 顺序表位置是否正确
  • 成功后长度要减去1
  • 后方元素向前移动一个位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//删除p位置的元素
bool delElem(Sqlist &L, int p, int &e)
{
//位置错误返回false
if(p < 0 || p > L.length - 1) return false;
e = L.elems[p]; //将被删除的元素赋值给e
for(int i = p; i < L.length - 1; i++)
{
//从p开始后方元素向前移动一个位置
L.elems[i] = L.elems[i+1];
}

L.length--; //长度减去1
return true; //成功返回true

}

顺序表的销毁

  • 在初始化函数中,用了new来分配内存,所以在销毁时要释放内存
1
2
3
4
5
6
7
void destroy(Sqlist &L)
{
//内存存在则释放内存
if(L.elems) delete []L.elems;
L.length = 0;
L.size = 0;
}

顺序表的概念及定义

顺序表

结点的概念

结点 :结点是内存中一片由用户分配的储存空间,只有一个地址来表示它的存在,没有显式名称。

在学习顺序表时,一般不会去特别强调结点的概念,此概念往往在链表学习中涉及,但并不代表结点与顺序表无关,所以我特意把结点的概念放在此处以加深对顺序表的理解。

顺序表的概念

定义:把逻辑上相邻的结点储存在物理位置上的相邻储存单元中,结点的逻辑关系由储存单元的邻接关系来体现

通俗来讲,顺序表就是把线性表中的所有元素按照其逻辑顺序,依次储存到从指定的储存位置开始的一块连续的储存空间中。

第一个元素的储存位置就是指定的储存位置,第 i+1 个元素的储存位置在第 i 个元素后面

顺序表的特性

  • 占用连续的储存空间:由定义可知顺序表的储存空间必然连续,并且存储分配只能预先进行,一旦分配完毕,在操作过程中始终不变。
  • 随机访问特性:因为储存空间是连续的,知道第一个元素的地址(即储存空间的首地址)可以轻松访问储存的所有数据。每一个结点对应一个序号,由该序号可以直接算出结点的储存地址。

顺序表三要素

  • 顺序表基地址
  • 顺序表长度
  • 顺序表总空间大小

顺序表结构体定义

1
2
3
4
5
6
typedef struct _Sqlist Sqlist;
struct _Sqlist {
int *elems; //顺序表基地址
int length; //顺序表长度
int size; //顺序表总空间大小
};

当然C语言提供了一种简单的写法(如下,以后以简单写法为例)。

1
2
3
4
5
6
typedef struct{
int *elems; //顺序表基地址
int length; //顺序表长度
int size; //顺序表总空间大小

}Sqlist;

在某些书籍上,有这样定义顺序表的

1
#define MAXSIZE 100
1
2
3
4
typedef struct {
int data[MAXSIZE]; //存放顺序表元素的数组
int length; //存放顺序表的长度
}Sqlist;
  • 实际上这种定义已经为顺序表开辟了一部分内存空间,而前者需要使用函数来顺序表初始化。
  • 但实际上两种代码本质上是一样的,因为前者在顺序表的操作——初始化顺序表中的函数定义中,我们仍需要分配一片储存空间并且定义一个存放顺序表元素的数组;而后者相当于把这一步合并到了定义中。
  • 在学习过程而非实际开发中,我更倾向于前者,因为这更能反应顺序表的三要素,并且与链表代码书写风格相似,有利于感受线性表思想的共性。

结束

我们现在已经成功定义顺序表了,但更重要的是它的操作,所以下一篇文章就来写这部分内容。

C语言结构体指针与结构体变量作形参的区别

区别

结构体变量

  • 结构体变量作为形参,传递的是结构体变量本身,是一种值传递
  • 形参结构体变量成员值的改变不影响对应的实参构体变量成员值的改变

结构体指针

  • 结构体指针作为函数参数,传递的是指向结构体变量的本身
  • 结构体指针指向的变量成员值的改变影响对应的实参构体变量成员值的改变

代码

直接说有些抽象难懂,敲代码演示一遍就很清楚了

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct stru{
int num;
};

//形参为结构体变量
void addNum(struct stru p, int num2)
{
p.num += num2;
}

//形参为结构体指针
void addNum2(struct stru *p, int num2)
{
if(!p) return; //确保指针不为空指针
p->num += num2;
}

int main(){

struct stru t;
t.num = 50;

addNum(t,5000);
printf("形参为结构体变量得到的结果为: %d\n", t.num);

addNum2(&t,5000);
printf("形参为结构体指针得到的结果为: %d\n", t.num);

return 0;

}

输出结果

1
2
形参为结构体变量得到的结果为: 50
形参为结构体指针得到的结果为: 5050

CuteBot智能小车

原因

近期,别人送了我一个CuteBot智能小车,拆开一看做工挺精致的,但是这东西是积木图形编程,显然不适合我这个年龄,所以打算给家里的小孩玩。

那么,你可能会问了,为什么要写这篇文章呢?答案当然是用来水的啊

其实在装的时候遇到了点坑,所以记录下来(说了半天还是水文章(滑稽)

部件

首先看下一个具有完整功能的 CuteBot小车(不算拓展)分为几个部分吧

  • MicroBit主板

这可以说是最核心的部件了,给小车烧录程序也是通过它。Microbit是由英国BBC公司推出的面向青少年编程教育的微型计算机,集成了加速度传感器,磁力传感器,两个可编程按钮,25个单色led,蓝牙等常用传感器设备,有一个micro usb接口用于连接数据线烧写程序和供电,可外接电池盒,底部有多个环孔连接器用于控制外接设备。这个板子不仅仅可以用于小车,官方还有许多套件,如智能家居等。当然也可以仅用这个板子跑程序,亮Led,放音乐等。总之它的功能非常强大。

MicroBit正面 MicroBit反面
  • 电池盒
电池盒
  • SR04超声波模块
超声波模块
  • 小车主体 (电池盒是粘上去的,实在是弄不下来了)
CuteBot Car

组装

  • 首先将电池盒的线接到小车主板上并将电池盒粘到小车上

  • 然后插入超声波模块(注意:超声波模块插槽为8Pin,要插入到插槽的前4个孔上,千万不要插入后四个插孔,否则小车无法跑起来,超声波模块会发烫

    如图:

SR04
  • 最后将MicroBit插入的小车上的蓝色插槽里(MicroBit背面朝电池盒)
  • 组装完成
CuteBotCar

编程

环境

新建项目
  • 输入项目名
  • “高级” -> “扩展”
扩展
  • 搜索CuteBot ,并点击
SearchCute
  • 返回页面你就会发现有了“酷比特小车”一行了
CuteBit
  • 点击“…” -> Connect 根据提示连接小车即可
Connect

Hello World

  • 现在开始编写第一个程序吧,你可以选择图形化的“方块”编程,也可以用JavaScriptPython编程(这里我用JS)
JS
  • 输入代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
这部分是开机执行
*/

//在MicroBit显示屏(Led)上显示字符串 Hello,World!
basic.showString("Hello,World!")

//显示完后,以50%的速度向前方行驶5秒
cuteBot.moveTime(cuteBot.Direction.forward,50,5)

basic.forever(function () {
/*
这里是无限循环的代码块
*/

})
  • 点击“下载” ,代码就开始执行了
  • (注意:如果该网站没有连接到MicroBit,那么你需要下载文件并右键手动发送到MicroBit里)

结束

该小车的优点是不需要焊接电路,并且无需搭配环境,仅需要组装好小车并通过在线编程即可运行

由于篇幅有限,关于API使用可以参考官方文档

使用Visual Studio 2019开发Qt程序

安装Qt

  • 如标题,你首先需要到 http://download.qt.io/ 去下载并安装Qt,并在引导下安装MSVC组件(这里不做过多解释)
QtDownload

Visual Studio 2019 配置

  • 打开VS2019
  • 点击“继续但无需代码”
VS2019
  • “扩展(X)” -> “管理扩展”
VS2019
  • 搜索“Qt”
SearchQt
  • 找到“Qt Visual Studio Tools”,点击“下载”按钮(图中是已经安装好的所以不显示下载)

  • 安装过程中会弹出 VSIX Installer窗口,依据引导安装即可

检查

  • 当我们再次打开 Visual Studio 2019 -> “创建新项目” -> 搜索“Qt”,发现已经能够创建Qt项目了
VS_Qt
  • 但是这还没有完,因为我们还没有添加 Qt Version

添加 Qt Version

  • 点击“上一步” -> “继续但无需代码” -> “扩展(X)” -> “Qt VS Tools” -> “Qt Versions”
  • 点击“add new Qt version”,然后点击Path列下的类似于文件夹的图标
Options
  • 找到你的Qt安装目录,在里面找MSVCqmake.exe (例如我的的Qt安装在D盘根目录,Qt版本是5.14.2,那么对应的就应该为 D:\Qt\Qt5.14.2\5.14.2\msvc2017_64\bin\qmake.exe)
  • 最后点击“确定”按钮保存即可
  • 注:图片中第一行显示的版本是我之前已经配置好的Qt版本,如果你是第一次配置,是不会自动添加Qt版本的

C++五子棋(七)——main函数以及项目总结

main函数

  • main.cpp 代码如下
    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
    int main(void){
    init();

    while(1){
    //一直检测鼠标点击
    MOUSEMSG msg == GetMouseMsg();
    if(msg.uMsg == WM_LBUTTONDOWN){
    manGo();
    if(checkOver()){
    init();
    continue;
    }

    AI_GO();
    if(checkOver()){
    init();
    continue;
    }

    }

    }

    closegraph();
    return 0;

    }

项目总结

  • 学习了c语言模块化开发
  • 设计了判断鼠标点击的算法
  • 掌握了AI走棋的写法
  • ……

不足之处

  • 代码缺乏优化,vector没有充分使用
  • 玩家不能选择棋子颜色
  • 无法进行玩家对战
  • AI算法效率不够高

进阶

  • 继续学习数据结构与算法对AI进行优化
  • 尝试建立服务器实现网络对战等

C++五子棋(六)——游戏结束

规则原理

如图

1 2 3 4 5

判断游戏结束

  • chessData.h
1
2
//row,col	表示当前落子
bool checkWin(ChessData* game, int row, int col);
  • 横、竖、斜(斜有两种)共四种情况,每种情况根据当前落子往后遍历5个子,有一种符合就胜利
  • chessData.cpp
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
bool checkWin(ChessData* game, int row, int col){
//横
for(int i = 0; i < 5; i++){
if(col - i >= 0 &&
col - i + 4 < BOARD_GRAD_SIZE &&
game->chessMap[row][col-i] == game->chessMap[row][col-i+1] &&
game->chessMap[row][col-i] == game->chessMap[row][col-i+2] &&
game->chessMap[row][col-i] == game->chessMap[row][col-i+3] &&
game->chessMap[row][col-i] == game->chessMap[row][col-i+4]){return true;}
}

//竖
for(int i = 0; i < 5; i++){
if(row - i >= 0 &&
row - i + 4 < BOARD_GRAD_SIZE &&
game->chessMap[row-i][col] == game->chessMap[row-i+1][col] &&
game->chessMap[row-i][col] == game->chessMap[row-i+2][col] &&
game->chessMap[row-i][col] == game->chessMap[row-i+3][col] &&
game->chessMap[row-i][col] == game->chessMap[row-i+4][col]){return true;}
}

// “/”方向
for(int i = 0; i < 5; i++){
if(row + i < BOARD_GRAD_SIZE &&
row + i - 4 >= 0 &&
col - i >= 0 &&
col - i + 4 < BOARD_GRAD_SIZE &&
game->chessMap[row+i][col-i] == game->chessMap[row+i-1][col-i+1] &&
game->chessMap[row+i][col-i] == game->chessMap[row+i-2][col-i+2] &&
game->chessMap[row+i][col-i] == game->chessMap[row+i-3][col-i+3] &&
game->chessMap[row+i][col-i] == game->chessMap[row+i-4][col-i+4]){return true;}
}

// “\”方向
for(int i = 0; i < 5; i++){
if(row - i >= 0 &&
row - i - 4 < BOARD_GRAD_SIZE &&
col - i >= 0 &&
col - i + 4 < BOARD_GRAD_SIZE &&
game->chessMap[row-i][col-i] == game->chessMap[row-i+1][col-i+1] &&
game->chessMap[row-i][col-i] == game->chessMap[row-i+2][col-i+2] &&
game->chessMap[row-i][col-i] == game->chessMap[row-i+3][col-i+3] &&
game->chessMap[row-i][col-i] == game->chessMap[row-i+4][col-i+4]){return true;}
}

return false;

}

调用接口

  • main.cpp
1
#include <stdio.h>
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
bool checkOver(){
if(checkWin(&game, clickPosRow, clickPosCol)){
Sleep(1500);
if(game.playFlag = false){
//黑棋胜利,此时标记已经转为白棋落子
mciSendString("play res/不错.mp3", 0, 0, 0);
loadimage(0, "res/胜利.jpg");
score += 100; //更新分数
}else{
mciSendString("play res/失败.mp3", 0, 0, 0);
loadimage(0, "res/失败.jpg");
score -= 100; //同理
}


//用于显示分数
char scoreText[64];
sprintf(scoreText, "当前分数:%d", score);
outtextxy(310, 800, scoreText);

//记录分数
FILE* fp = fopen("score.data", "wb");
fwrite(&score, sizeof(score), 1, fp);
fclose(fp);


getch();
return true;

}

return false;

}

显示分数

  • main.cpp
1
2
#define INIT_SCORE 1000
int score; //全局变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void initScore(){
//分数字体设置
settextcolor(WHITE); //color
settextstyle(50, 0, "微软雅黑"); //style

FILE *fp = fopen("score.data", "rb");
if(fp == NULL){
score = INIT_SCORE;
}else{
fread(&score, sizeof(score), 1, fp);
}
if (fp)fclose(fp);

}
  • 然后在main.cpp文件的 init() 函数定义中 继续 添加代码
1
initScore();	//这一行添加到init()函数定义中

结束

到这里五子棋的全部功能已经实现了,但是你会发现程序无法运行。这是理所当然的,因为我们的main函数还没有写,在下一篇文章(也就是本项目的最后一章)我们将完善main函数并做该项目的总结。

C++五子棋(五)——实现AI落子

AI思考落子点

在之前我们已经实现计算权值了,现在要想让AI落子,应根据之前的计算结果使棋子落在分值最大点上。当然可能会出现多个分值相同的最大点,这时在其中随机取一个点落下即可。

  • chessData.h
1
2
3
4
5
6
7
typedef struct point{
int row;
int col;
} point_t;

//机器下棋
point_t actionAI(ChessData* data);
  • chessData.cpp
1
2
3
#include <time.h>
#include <stdlib.h>
#include <vector>
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
point_t actionAI(ChessData* data){
//计算评分
calcScore(data);

//找出最大分数位置
int maxScore = 0;
std::vector<std::pair<int, int>> maxPoints;

int k = 0;

for(int row = 0; row < BOARD_GRAD_SIZE; row++){
for(int col = 0; col < BOARD_GRAD_SIZE; col++){

//若该坐标为空
if(data->chessMap[row][col] == 0){
//找出最大数和坐标
if(data->scoreMap[row][col] > maxScore){
maxScore.clear();
k = 0;
maxScore.push_back(std::make_pair(row, col));
k++;

}else if(data->scoreMap[row][col] == maxScore){
maxPoints.push_back(std::make_pair(row, col));
k++;
}
}

}
}

//如果有多个点随机落子
srand((unsigned)time(0));
int index = rend() % k;
return maxPoints[index];

}

实现AI落子

  • main.cpp
1
2
3
4
5
6
7
8
9
10
void AI_GO(){
point_t point = actionAI(&game);
clickPosRow = point.row;
clickPosCol = point.col;

Sleep(1000);
chessDown(clickPosRow, clickPosCol, CHESS_WHITE);
updateGameMap(&game, clickPosRow, clickPosCol);

}