NOIP学习小站

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2020-09-27tangyj626阅读(285)赞(17)

前面小节我们学习了用结构体数组来存储链表，结构体中的prev和next“指针”其实是整数，指向的是上一个元素和下一个元素在数组中的存储下标。其实我们还可以在结构体中使用真正的指向上一个元素和下一个元素的指针来实现链表。 一、普通链表 1.使...

2020-09-20tangyj626阅读(472)赞(17)

班级所有同学去参观自然博物馆，在博物馆前列队完毕后解散进入馆内自由参观。活动结束后，领队老师想恢复参观前队列的次序，但是在解散前老师并没有记录下来所有人的次序，幸运的是每个人都知道在队列里自己的下一个人是谁，领队老师也知道队列里第一个人是谁...

2020-09-20tangyj626阅读(311)赞(14)

中午在食堂打饭，真是一个令人头疼的事情，去食堂的路上也总是步伐匆匆，迟一点去，就会深刻领悟什么叫做人山人海了。相比较学生来说，打饭阿姨毕竟是少数，在每个窗口都有人的时候，我们就得排队等待，队列最前面的一个学生打完饭离开，后面排队的人才可以继...

2020-09-20tangyj626阅读(446)赞(13)

线性表是最简单、最基本的一种数据结构，线性表可以描述为若干具有相同数据类型的数据按照线性“串起来”的结构，线性表中的每个元素都有前一个元素（前驱）和后一个元素（后继）。线性表可以分为栈、队列、链表等。 一、栈的定义 先来看一个例子：小张是流...

2020-09-20tangyj626阅读(322)赞(13)

指针其实存储的是变量在内存中的地址，将指针指向变量后，就可以使用该指针来获取变量的值或者为变量赋新值。 一、指针的基本用法 指针是用来指向某个变量的，将指针指向变量后，指针存储的是该变量在内存中的地址。要使用指针，首先要申明指针，然后就可以...

2020-09-20tangyj626阅读(581)赞(15)

结构体能够将一些不同类型的信息“捆绑”聚合成一个整体，例如可以用一个结构体来记录学生的姓名（字符串类型）、性别（char类型）、年龄（int类型）等信息。结构体就像int、double一样，是一种（自定义的）数据类型。 一、结构体的基本使用...