基础算法

2020-10-02tangyj626阅读(383)赞(19)

通过模拟解决问题，这里的“模拟”指的是编写程序时，让程序按照题目的描述方式执行得到最终的答案，也就是程序来模拟题目中描述的问题处理方法。正因为如此，模拟并不是一种真正意义上的算法。但是模拟的技巧是关注问题的细节，做到完整处理每个技术细节。而...

2020-10-02tangyj626阅读(311)赞(16)

通过前面章节的学习，我们已经知道C/C++中存储整数一般使用 int 类型，如果要存储更大的整数，可以使用long long类型。如果要存储更大的整数，还可以尝试使用float或者double浮点数，但这样做精度会受到影响。如果处理的整数特...

2020-10-02tangyj626阅读(249)赞(14)

两个高精度数按照前面的规则存储到数组中后，只需要从低位到高位按位相加就能实现高精度数的加法。在按位相加的过程中需要处理进位： 当然也可以使用整除直接计算进位，使用模运算修正每位的数字： 也可以实现高精度自加： 完整的测试程序如下：

2020-10-02tangyj626阅读(160)赞(15)

高精度数A-高精度数B，如果A>=B，那么直接从低位到高位按位相减即可，需要额外处理不够减时的借位情况；如果A<B，则结果是-(B-A)。可知高精度减法，只需要考虑较大数减去较小数的情况，如果较小数减去较大数，那么可以先输出负号...

2020-10-02tangyj626阅读(226)赞(14)

先来看高精度正整数乘以低精度正整数的情况，直接按位相乘即可，高精度从低位到高位每位上的数字乘以低精度整数，结果每位上的数字很可能超过10，需要处理进位，并且全部计算结束后还需要考虑最后一次乘法结果的特殊进位： 上图展示了高精度数753乘以低...

2020-10-02tangyj626阅读(213)赞(15)

先来看高精度除以低精度，观察除法竖式运算的过程： 首先高精度数最高位1除以31，商0余1；然后上一次的余数1×10+高精度数的下一位6，也就是16除以31，商0余16；然后上一次的余数16×10+高精度数的下一位4，也就是164除以31，商...

2020-10-03tangyj626阅读(164)赞(13)

来看问题：P1009阶乘之和 根据数据规模可以明显看出这里需要使用高精度运算。可以将高精度正整数封装成一个结构体，通过重载运算符来实现高精度正整数的四则运算，下面给出参考代码，但是涉及到C++的一些高级用法，理解起来有一定难度： 通过封装结...

2020-10-03tangyj626阅读(397)赞(15)

在生活中，我们往往需要排序，例如考试结束后老师会按照成绩高低排序确定名次，对每天要完成的工作按照紧急程度排序后优先完成急需完成的工作。排序就是将杂乱无章的无序的数据按照某种规则整理使这些数据有序。 一、sort函数对数组排序 排序的算法很多...

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

结构体数组是不能直接简单调用sort函数排序，因为两个结构体变量不能直接比较大小（没有定义比较规则），但是可以指定sort函数的第三个参数（比较函数）来实现对结构体数组的自定义排序。 【问题】一次测试后，小组内位同学的姓名和语文、数学、英语...

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

先来看对一组结构体数据排序： 程序运行结果如下（分两部分显示）： 分析排序结果可知，按照结构体成员n升序排序，对于成员n相等的结构体数据，排序后没有维持原来的相对顺序（例如n=1的所有结构体数据，原始顺序是“Name01 1”、“Name0...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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