NOIP学习小站

2020-10-23tangyj626阅读(1125)赞(15)

搜索与回溯是计算机解题中常用的算法。搜索的策略是先选择一个起点开始向前探索，逐渐扩大寻找范围，在探索过程中一旦发现之前的选择是错误的，就退回一步重新选择（回溯），继续向前探索，如此反复进行，直到得到解或者证明问题无解。回溯是搜索算法的一种控...

2020-10-19tangyj626阅读(432)赞(13)

如果能够将一个大的任务分解成若干个规模较小的任务，而且这些任务的形式与结构与原问题一致，这个时候就可以考虑使用递归。当问题规模足够小或者达到了边界条件就停止递归（需要在递归函数中设计递归出口）。根据前面对递归函数的认识，利用递归分解完问题后...

2020-10-19tangyj626阅读(425)赞(12)

在函数学习时，已经初步学习了 递归函数 的使用，借助递归函数编写程序解决问题是一种重要的方法，能够使一些复杂的问题变得简单，对应地编写的程序也简洁。递归的特点是函数体中又调用自己。如果是直接调用自己称为直接递归；如果是函数 中调用函数 ，函...

2020-10-19tangyj626阅读(288)赞(11)

本文通过例题来进一步帮助读者学习掌握递推算法。 一、位数问题 问题：在所有的 位数中，有多少个数中有偶数个数字 3？注意：如果一个数字没有出现 3，那么就有 0 个 3，也算有偶数个 3。由于结果很大，只需要输出答案对 12345 取余的值...

2020-10-19tangyj626阅读(415)赞(11)

本文通过几个经典的例题介绍几种典型的递推关系。在实际做题时，如果找不出递推关系，那么可以尝试笔算得出前几项结果，通过寻找规律来发现递推关系。严格情况下，通过寻找规律得出的递推关系需要进一步理论论证。 1.斐波那契数列 来看兔子繁殖问题：一般...

2020-10-17tangyj626阅读(413)赞(15)

递推算法是一种重要的数学方法，在数学领域广泛应用，也是计算机领域用于数值计算的一种重要算法。递推算法的特点是：一个问题的求解需要一系列的计算，在已知条件和所求问题之间存在着某种相互联系的关系，在计算时，如果能够找到前后过程之间的数量关系（也...

2020-10-15tangyj626阅读(248)赞(15)

排列枚举，就是枚举所有元素的排列（要考虑元素的先后顺序）情况。例如三个数 {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...

2020-10-15tangyj626阅读(458)赞(17)

先来看一个问题，从 1～ 中选择 4 个数，有多少种选择方法？输出具体的选择方案。 这是一个数学的组合问题，组合不讲顺序（选出来的数不考虑它们位置关系），例如 {1,2,3,4} 和 {1,2,4,3}、{1,3,2,4}、{1,3,4,2...

2020-10-14tangyj626阅读(255)赞(15)

来看例题：P2241 统计方形（数据加强版） 首先来考虑棋盘中正方形和长方形的特征，可以得出一个明显的结论：棋盘中不同行不同列的两个点能够确定一个正方形或者长方形。 但是究竟是正方形还是长方形需要进一步考查两点的坐标关系（通过坐标计算两条边...

2020-10-14tangyj626阅读(228)赞(17)

来看例题：P3392 涂国旗 国旗从上到下分成三个颜色区域，可以使用双重循环枚举白色区域的高度和蓝色区域的高度，那么剩下的就是红色区域，高度为。可知，： 双重循环的最内层就对应了一个方案。接下来需要计算：1～行全部格子涂成白色需要涂改的格子...

2020-10-13tangyj626阅读(180)赞(18)

来看例题：P1618 三连击（升级版） 初步想法仍然是依次枚举三位数每位上的数字，简单暴力的做法是使用九重循环枚举，每一层枚举1～9九个数字，那么需要枚举次，在1s内很可能会超时。 其实可以枚举第一个数，第二个数和第三个数可以通过题目中指出...

2020-10-13tangyj626阅读(270)赞(19)

枚举算法是我们在日常中使用到的较多的一个算法，它简单粗暴，算法的核心是暴力枚举所有可能情况，并进一步从中筛选出满足条件的方案。因为枚举法编程实现最简单，并且得到的结果往往是正确的，所以虽然枚举算法非常暴力，而且速度可能很慢（导致超时），但却...

2020-10-04tangyj626阅读(270)赞(18)

一、归并排序 归并排序（Merge sort），是创建在归并操作上的一种有效的排序算法，是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序思路简单，速度仅次于快速排序，且排序稳定，一般用于对总体无序，但是各子...

2020-10-03tangyj626阅读(295)赞(20)

一、快速排序 从快速排序（Quick Sort）的名称来看就知道这种排序的效率要高于前面介绍的选择排序、插入排序和冒泡排序。快速排序的原理其实很简单，以升序排序为例，首先在序列里找到一个基准元素（可以随意找一个，一般用序列第一个元素或者中间...

2020-10-03tangyj626阅读(213)赞(17)

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访要排序的序列，一次比较两个相邻元素，如果它们的顺序错误就把它们交换过来。重复执行走访序列的过程，直到没有再需要交换的元素，这样序列就完成了排序。排序过程中，越小的元素经由交...

2020-10-03tangyj626阅读(228)赞(18)

希尔排序（Shell Sort）是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序是一种插入排序，它是将简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，该算法是冲破 时间复杂度的第一批算法之一。 ...

2020-10-03tangyj626阅读(223)赞(18)

插入排序（Insertion Sort）是一种简单直观的排序算法。其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 插入排序算法描述如下（以升序排序为例说明）： 可知插入排序是从序列的第 2 个...

2020-10-03tangyj626阅读(211)赞(16)

选择排序（Selection Sort）是一种简单直观的排序算法。算法的处理过程是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到未排序序列的首部（也就...

2020-10-03tangyj626阅读(248)赞(14)

一、桶排序 桶排序（Bucket Sort）是计数排序的升级版。假设输入数据服从均匀分布，桶排序的工作原理： 假设要排序的所有数据都是 1～99 的整数，那么可以以十位上的数字为标准将所有的数据放到编号为 0～9这 10 个“桶”中，然后对...

2020-10-03tangyj626阅读(275)赞(14)

一、计数排序 先来看一个例题“P1271 选举学生会”： 学校正在选举学生会成员，有 （）名候选人，每名候选人编号分别从 1 到  ，现在收集到了  （ ） 张选票，每张...