八数码问题是一个经典的搜索问题，本文将介绍如何使用启发式搜索—— AStar 算法来求解八数码问题。 使用AStar算法解决八数码问题问题描述 八数码问题的A星搜索算法实现 要求：设计估价函数，并采用c或python编程实现，以八数码为例演示A星算法的搜索过程，争取做到直观、清晰地演示算法，代码要适当加注释。 八数码难题：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0可自己随机设定，使用的操作有：空格上移，空格左移，空格右移，空格下移。试采用A*算法编一程序实现这一搜索过程。 算法描述预估值的设计A* 算法的花费为 f(n) = g(n) + h(n)，其中 g(n) 为搜索深度，定义为状态单元 state 的成员变量，在每次生成子节点时将其加一。h(n) 为不对位的将牌数，将该部分的计算重载于 state 的小于运算符中，并将 f(n) = g(n) + h(n) 的值作为状态单元的比较值。 数据结构设计 每个状态用一个结构体表示，其中 depth 为状态深度，str 为该状态字符串，并重载小于运算符用于计算最优。 open 表使用优先 ...

本文将继续介绍一些常见的 C++ 代码优化技巧，本文为该系列的第二章，未来不定期更新。 非必要时使用常量引用在上一章我们介绍了在进行函数的参数传递时，尤其对于所占内存空间较大的参数的传递，为了避免拷贝所带来的不必要的性能开销，应当尽量使用引用传递。并且，当该函数不需要对传入的参数进行更改时，应当在参数类型前添加 const 关键字表示这是一个常量引用。 可能有朋友认为这里的 const 关键字的添加并不是必要的，但这样会带来两个问题：首先便是程序的可读性的下降，如果不添加 const 关键字，用户可能会认为该函数的变量是可更改的。其次它还将导致字面值将无法作为该函数的参数进行传递。所谓字面值，就是指代码中用数字或字符直接表示出来的常量（例如 1, "hello world"），这部分数据嵌入在程序中，当程序运行时被复制到内存的常量区，该区域为只读区域。示例如下： int findChar(std::string& s, char target) { for (int i = 0; i < s.size(); ++i) { if ...

最近在写人工智能作业的时候遇到了一点问题，就是在循环语句中对指针类型赋值出现错误，导致所有的结点的前驱指针最终指向自身。 问题描述以下使用一个简单的示例来模拟当时出现的问题。 MyStruct 为一个自定义结构体类型，包含数据成员 val 和前驱结点 pre。首先将初始结点(0，nullptr)加入队列 Q，随后在每次循环中，用变量 fs 接收队列 Q 的队首元素并将其出队，并根据该结点生成一个新结点，该新结点 val = fs.val + 1，且将其前驱结点设为 fs 并加入到队列 Q 中。直到 fs.val >= 5 时退出循环。 struct MyStruct { int val; MyStruct* pre; MyStruct(int v = 0, MyStruct* p = nullptr) : val(v), pre(p) {} }; int main() { std::queue<MyStruct> Q; Q.emplace(0, nullptr); MyStruct target; while ...

本文介绍如何使用矩阵堆栈原理实现简单的行星运行系统。 原理有时我们需要在一个场景中绘制不同的模型，如果这些模型彼此间没有联系，即各模型的位置不会相互影响，那我们只需要单独为每个模型创建合适的变换矩阵，并经过渲染管线将其渲染即可。而对于一个位置会相互影响的系统而言，例如行星运行系统，地球围绕太阳公转，而月球围绕地球公转。处理这样问题的关键在于如何确定各物体变换矩阵，准确来说是模型-视图矩阵。而矩阵堆栈可以很好地将这问题简化。所谓矩阵堆栈，就一个用来存储变换矩阵的堆栈结构，栈顶矩阵为栈底矩阵乘上另一个矩阵变换而来，由此，栈底到栈顶形成一个逐步复杂的结构。通常来说，栈底的矩阵为视图矩阵，因为对于一个场景中的每个物体，它们都要经过视图矩阵的变换。逐步往上，由父物体的变换矩阵先入栈，利用栈顶矩阵作为该物体的模型-视图矩阵绘制物体后，再进入其子物体的管线，依次逐步进行。同时，对于不希望由父物体继承给子物体的变换矩阵可以在绘制完父物体后将其出栈。 实现代码实现对于本文所要研究的行星运行系统，共有三个物体：太阳、地球、月球，它们的依赖关系是：地球围绕太阳公转，而月球围绕地球公转。矩阵堆栈的变换情况如下 ...

本文介绍生成一个集合子集的两种常见算法，借此从中深入理解搜索问题中常见的两种思路。 递归回溯思路对于集合中的每个元素，我们都有选择和不选择两种处理方式，这种思路类似于二叉树的遍历，每种情况都向下衍生出两种情况，最终当遍历到下标 index = nums.size() 时，将生成的子集保存。 由于此处我们使用一个数组的引用来保存子集元素，因此在递归回溯时，我们需要手动将上一步中加入添加的元素去除，来回溯到该元素未被选择的状态。 代码class Solution { private: std::vector<std::vector<int>> Sets; void search(std::vector<int>& subset, std::vector<int>& nums, int index) { if (index == nums.size()) { Sets.emplace_back(subset); return; } subset.emplace_back(nums[i ...

本文将介绍一些常见的 C++ 代码优化技巧，本文为该系列的第一章，未来不定期更新。 使用前置递增（递减）运算符可能很多从 C 语言开始学习的朋友会对此感到困惑，觉得这两者在适用的情况下可以任意选择，如 for 循环语句写作 for (int i = 0; i < n; i++) 。这样做当然没错，但会造成一定程度上的资源浪费，因为后置递增运算符需要先将原本的变量值保存下来，再对其进行递增操作，而在此 for 循环中，我们并不需要使用原本的 i 值。并且 ++i 的写法相对来说更符合我们的意愿。 当然对于基本数据类型来讲，在经过编译器的优化之后，两者的效率可能并没有什么差别，但对于 STL 中的模板容器，或是自定义数据结构的迭代器来讲，前置运算符的效率显然要更高，因为单个对象所占的内存空间更大，使得拷贝暂存的开销也越大。 因此，除非必要情况，应该尽可能使用前置递增（递减）运算符。 使用引用传递引用类型变量并不是一个对象，它只是一个已存在对象的别名，因此在作为变量传递时不会经过拷贝构造的过程，能够显著地提升效率，以下为值传递的情况。 struct myStruct { ...

声明语句的构成 在 C++ 中，一条声明语句由一个基本数据类型（base type）和紧随其后的一个声明符（declarator）列表组成。 复合类型的声明定义多个变量对于基本数据类型变量的声明，声明符就是变量名。但对于复合类型来讲，例如指针类型和引用类型，变量名却只是声明符的一部分。例如 int *b; 需要注意的是， “*”运算符修饰的对象是变量名，而不是基本类型名。例如 int *a, b;，此处变量 b 的数据类型为 int，而非 int *。 指针的引用指针引用的正确定义形式如下： int a = 1, * b = &a; int*& c = b; // c为指针b的引用 int&* d = b; // 错误，d表示指向引用的指针，而引用本身并不是一个对象，无法使用指针进行指向 要想正确理解一个复杂的复合类型，可以从右向左进行阅读，离变量名最近的符号越接近该变量的真实类型，如上例中的引用符。

本次周赛没想到比上周还要简单，前三题都可以用非常简单的方法快速解决，第四题如果想对了方向其实也比较简单。 元素计数题目链接元素计数 解题思路相当基础的题目，要同时具有一个严格较小元素和一个严格较大元素，只需要保证这个数 num 满足 num > minVal && num < maxVal即可。 解题代码class Solution { public: int countElements(vector<int>& nums) { int minVal = INT32_MAX, maxVal = INT32_MIN; for (int i = 0; i < nums.size(); i++) { minVal = min(minVal, nums[i]); maxVal = max(maxVal, nums[i]); } int res = 0; for (int ...

本文将介绍如何使用最为常用的图形 API —— OpenGL 来渲染一个立方体，代码部分来自于《Computer Graphics Programming in OpenGL with C++》，并加入了自己的理解。 基本过程环境配置在编写程序之前，需要先配置好一些有助于程序编写的第三方库，本次实验需要用到的库有三个：用于窗口管理的 GLFW 库，扩展功能的 GLEW 库，以及用于数学运算的 GLM 库。 IDE 使用的是 Visual Studio 2019，并安装了 GLSL Language Integration 插件来实现 glsl 语言的代码高亮和自动补全。 具体的环境配置过程在此不过多赘述，本文主要聚焦于代码的实现。 窗口的创建要将渲染的图像显示出来，就需要创建一个特定的显示窗口，首先通过 glfwWindowHint() 指定 OpenGL 的版本号，再使用 glfwCreateWindow() 创建 GLFW 窗口。由于创建 GLFW 窗口并不会自动将它与当前 OpenGL 上下文关联起来，因此还需要调用 glfwMakeContextCurrent(). 为了防止 ...

本次周赛相对比较简单，前三题花的时间比较短，但无奈最后一题还是没思路。。。 将字符串拆分成若干长度为 k 的组题目链接将字符串拆分成若干长度为 k 的组 解题思路遍历字符串 s 的每个字符并加入到一个临时字符串中，当此临时字符串长度为 k 时，加入到结果数组中并清空此字符串。若此时遍历到字符串的最后一个字符且此时临时字符串长度没有达到 k 时，则向其末尾填入字符 fill 直到临时字符串长度达到 k，再加入到结果数组中。 解题代码class Solution { public: vector<string> divideString(string s, int k, char fill) { vector<string> res; string newStr; for (int i = 0; i < s.size(); i++) { newStr += s[i]; if (newStr.size() == k) { ...