NOIP学习小站循环枚举——P3392 涂国旗
来看例题：P3392 涂国旗 国旗从上到下分成三个颜色区域，可以使用双重循环枚举白色区域的高度和蓝色区域的高度，那么剩下的就是红色区域，高度为。可知，： 双重循环的最内层就对应了一个方案。接下来需要计算：1～行全部格子涂成白色需要涂改的格子...
基础算法 第2页
循环枚举——P2241 统计方形（数据加强版）
来看例题：P2241 统计方形（数据加强版） 首先来考虑棋盘中正方形和长方形的特征，可以得出一个明显的结论：棋盘中不同行不同列的两个点能够确定一个正方形或者长方形。 但是究竟是正方形还是长方形需要进一步考查两点的坐标关系（通过坐标计算两条边...
子集枚举
先来看一个问题，从 1～ 中选择 4 个数，有多少种选择方法？输出具体的选择方案。 这是一个数学的组合问题，组合不讲顺序（选出来的数不考虑它们位置关系），例如 {1,2,3,4} 和 {1,2,4,3}、{1,3,2,4}、{1,3,4,2...
排列枚举
排列枚举，就是枚举所有元素的排列（要考虑元素的先后顺序）情况。例如三个数 {1,2,3} 的所有排列情况有：{1,2,3}，{1,3,2}，{2,1,3}，{2,3,1}，{3,1,2}，{3,2,1}一共 6 种情况。 四个数{1,2,3...
递推算法（1）——基础
递推算法是一种重要的数学方法，在数学领域广泛应用，也是计算机领域用于数值计算的一种重要算法。递推算法的特点是：一个问题的求解需要一系列的计算，在已知条件和所求问题之间存在着某种相互联系的关系，在计算时，如果能够找到前后过程之间的数量关系（也...
递推算法（2）——几种常见的递推关系
本文通过几个经典的例题介绍几种典型的递推关系。在实际做题时，如果找不出递推关系，那么可以尝试笔算得出前几项结果，通过寻找规律来发现递推关系。严格情况下，通过寻找规律得出的递推关系需要进一步理论论证。 1.斐波那契数列 来看兔子繁殖问题：一般...
递推算法（3）——经典例题
本文通过例题来进一步帮助读者学习掌握递推算法。 一、位数问题 问题：在所有的 位数中，有多少个数中有偶数个数字 3？注意：如果一个数字没有出现 3，那么就有 0 个 3，也算有偶数个 3。由于结果很大，只需要输出答案对 12345 取余的值...
递归算法（1）
在函数学习时，已经初步学习了 递归函数 的使用，借助递归函数编写程序解决问题是一种重要的方法，能够使一些复杂的问题变得简单，对应地编写的程序也简洁。递归的特点是函数体中又调用自己。如果是直接调用自己称为直接递归；如果是函数 中调用函数 ，函...
递归算法（2）
如果能够将一个大的任务分解成若干个规模较小的任务，而且这些任务的形式与结构与原问题一致，这个时候就可以考虑使用递归。当问题规模足够小或者达到了边界条件就停止递归（需要在递归函数中设计递归出口）。根据前面对递归函数的认识，利用递归分解完问题后...
搜索与回溯算法（1）——基础
搜索与回溯是计算机解题中常用的算法。搜索的策略是先选择一个起点开始向前探索，逐渐扩大寻找范围，在探索过程中一旦发现之前的选择是错误的，就退回一步重新选择（回溯），继续向前探索，如此反复进行，直到得到解或者证明问题无解。回溯是搜索算法的一种控...
搜索与回溯算法（2）——例题
一、数的拆分 问题：任何一个大于 1 的自然数 ，总可以拆分成若干个小于 的自然数的和。例如当 时，一共有 14 种拆分方法： 输入自然数 ，按照上面的格式输出拆分方案和方案种数。 分析：使用深度优先搜索算法，对于自然数 ，拆分出来一个整数...
搜索与回溯算法（3）——剪枝
DFS算法通过在函数内使用循环枚举下一步（或者是当前步）的所有情况，并在循环体中递归调用函数，实现了在当前基础上进一步搜索。如果根据题意可以严格限制循环枚举的条件（减少循环枚举的次数）或者在循环体中额外添加更全面的进一步递归搜索的条件，这两...
广度优先搜索（1）——基础
接下来介绍另一种搜索算法——广度优先搜索（BFS，有时候又称之为宽度优先搜索）。广度优先搜索比深度优先搜索简单，也更容易理解。如果一个问题两种搜索策略都能解决，一般情况推荐使用广度优先搜索，因为广度优先搜索的时间复杂度一般会低于深度优先搜索...
广度优先搜索（2）——例题
一、走迷宫 问题：迷宫是一个正方形，边长为 ，迷宫中的小格子（一共 个）有些能走通（标记 1），有些是墙壁（标记 0）。输入迷宫边长 和迷宫内部情况（ 行 列1、0整数），计算从迷宫左上角出发，到达右下角，最少需要走多少步？ 分析：这里要求...