NOIP学习小站-西安交通大学附属中学航天学校NOIP学习小站

NOIP学习小站
西安交通大学附属中学航天学校

最新发布 第2页

搜索

广度优先搜索(2)——例题

tangyj626阅读(431)赞(19)

一、走迷宫 问题:迷宫是一个正方形,边长为 ,迷宫中的小格子(一共 个)有些能走通(标记 1),有些是墙壁(标记 0)。输入迷宫边长 和迷宫内部情况( 行 列1、0整数),计算从迷宫左上角出发,到达右下角,最少需要走多少步? 分析:这里要求...

搜索

广度优先搜索(1)——基础

tangyj626阅读(465)赞(19)

接下来介绍另一种搜索算法——广度优先搜索(BFS,有时候又称之为宽度优先搜索)。广度优先搜索比深度优先搜索简单,也更容易理解。如果一个问题两种搜索策略都能解决,一般情况推荐使用广度优先搜索,因为广度优先搜索的时间复杂度一般会低于深度优先搜索...

搜索

搜索与回溯算法(3)——剪枝

tangyj626阅读(281)赞(14)

DFS算法通过在函数内使用循环枚举下一步(或者是当前步)的所有情况,并在循环体中递归调用函数,实现了在当前基础上进一步搜索。如果根据题意可以严格限制循环枚举的条件(减少循环枚举的次数)或者在循环体中额外添加更全面的进一步递归搜索的条件,这两...

搜索

搜索与回溯算法(2)——例题

tangyj626阅读(493)赞(14)

一、数的拆分 问题:任何一个大于 1 的自然数 ,总可以拆分成若干个小于 的自然数的和。例如当 时,一共有 14 种拆分方法: 输入自然数 ,按照上面的格式输出拆分方案和方案种数。 分析:使用深度优先搜索算法,对于自然数 ,拆分出来一个整数...

搜索

搜索与回溯算法(1)——基础

tangyj626阅读(967)赞(15)

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

递推与递归

递归算法(2)

tangyj626阅读(410)赞(13)

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

递推与递归

递归算法(1)

tangyj626阅读(376)赞(12)

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

递推与递归

递推算法(3)——经典例题

tangyj626阅读(265)赞(11)

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

递推与递归

递推算法(2)——几种常见的递推关系

tangyj626阅读(363)赞(11)

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

递推与递归

递推算法(1)——基础

tangyj626阅读(380)赞(15)

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

暴力枚举

排列枚举

tangyj626阅读(217)赞(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...

暴力枚举

子集枚举

tangyj626阅读(401)赞(17)

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

暴力枚举

循环枚举——P2241 统计方形(数据加强版)

tangyj626阅读(231)赞(15)

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

暴力枚举

循环枚举——P3392 涂国旗

tangyj626阅读(188)赞(17)

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

暴力枚举

循环枚举——P1618 三连击(升级版)

tangyj626阅读(149)赞(18)

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

暴力枚举

循环枚举——P2089 烤鸡

tangyj626阅读(231)赞(19)

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

排序

归并排序

tangyj626阅读(248)赞(18)

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

排序

快速排序

tangyj626阅读(272)赞(20)

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

排序

冒泡排序

tangyj626阅读(180)赞(17)

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

排序

希尔排序

tangyj626阅读(209)赞(18)

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