素数筛法求素数

如今的孩子可能没怎么见过筛子,传统的筛子样式如同[图1],多是用竹子编织而成,其作用就是通过抖动让细小的东西从筛子下部掉落,而较大的颗粒则留在筛子内,筛子上留的孔洞的大小不同,决定其的应用的地方,这种一次性“留精弃粗”的方式给人们的生活带来的很多的便利(现在有些饮用水过滤机就是利用层层筛网,让自来水成为可供饮用的纯净水)。 那么素数筛又是什么呢?顾名思义,所谓素数筛,“筛”的就是“数”。我回想了一下小学最开始学素数(那时候还有一种说法叫做“质数”,但是就语言上来说,我觉得“素数”这种叫法和“合数”比较搭配,类比于“化学元素”和“化合物”来看,叫“素数”非常贴切)的时候,书上给出的“找素数”的方法,并不是试除法,而是筛选法。所谓筛的过程,用[图2]来展示就很形象: 第一层筛网筛掉所有数字中大于2,且为2的倍数的数字; 第二层筛网筛掉所有数字中大于3,且为3的倍数的数字; 第三层筛网筛掉所有数字中大于5,且为5的倍数的数字; …… 层层筛选之后,我们就可以得到一个范围内的素数表[图3...

DP最大子段和

动态规划处理“线”上的问题非常在行,今天我们就来探讨求解最大字段和的问题。 问题是这样的。 给定N个整数,要求求出最大的连续子段的和。 例如给定:1 -4 3 1 -2 其最大子段和为:4 该子段为:3 1 我们先来分析这个问题。我们最直观的方法就是穷举所有的子段并求和,找到其中最大的,即为答案,但是明显这样做,效率太低。题目中涉及到了“子段”,这使我们想到动态规划的通过寻找“最优子结构”来找到“最优解”的思路。 给定的N个数字存在数组A[N]当中,然后用B[N]来记录子段和的状态。读者可能有疑问,一个串的子串明显不会只有N个,那为什么只用N个元素来记录状态呢?这样做的原因正是因为我们使用动态规划的思路,B中存储的是状态,串中的每个数字的状态只考虑一次。 那么我们来考虑状态转移方程该如何构造: 假设我们已经得到了一个局部最大子串和B[K-1],考虑算上下一个元素A[K]的时候,这个子串的和为B[K] = B[K – 1] + A[K], 这里算出来B[K]如果大于或等于零,则一定有B[K

高精度运算(4)比较

比较运算用于比较两个高精度整数的大小,算法十分简单,只需要按照两个规则,就可以得到两个数字谁大谁小: (1)如果一个数字比另一个数字位数少,则这个数字必比另一个数字小。 这就要求我们存储的数字不能有前导零。 (2)从末位开始向个位逐个比较,位上的数字大的,则这个数字也大。 通过这样的比较法则,我们就可以实现比较运算小于号“<”: [crayon-59c23149ca063401791135/] 神奇的是,我们只需要一个小于的比较运算符,就可以实现其它所有的比较运算符,请看下面的代码: [crayon-59c23149ca069565755140/] 下面给出完整的高精度运算类的代码: [crayon-59c23149ca06b739990513/]

高精度运算(3)乘法

在本篇文章中我们将实现高精度乘法运算。 乘法和加法比起来就复杂很多了,我们知道乘法可以由加法直接实现(连续加因数2次因数1),在有我们之前的加法运算的基础的情况下,这种乘法运算极其简单便能实现(但是需要先做出高精度数比较运算,这是下节的内容了,不过这种方法并不明智,对于一个N位数乘以N位数的运算,其时间复杂度为O(10^N),这个增长速度实在是太大了。 那么我们继续按照上次的思路,回到我们算乘法的竖式,看图1: 对于我们的乘法运算,按照计算机的运算思路,就是两个大循环,逐位相乘,最后再相加,然后转换为十进制数字,也就是进位,就能得到我们的结果了。 下面是乘法的实现方法: [crayon-59c23149ca24a257798386/] 依照惯例,给出完整的高精度整数类的代码,除了增加了乘法及乘法相关的运算符的重载外,为了防止乘法运算中相加过程中出现数值溢出,原先的short类型的容器修改为了int,这样可以确保不会出现乘法运算溢出的现象,同时在每次赋值和输入的最后,会自动去掉数字的前...

高精度运算(2)加法

在解决了高精度整数的输入、存储以及输出的问题后,我们终于开始正式思考“运算”部分的实现。 加法是最简单的一种四则运算,也是我们小学时数学最先就学到的运算规则,对于内置的整数类型而言,计算机通过二进制的电位运算可以快速的得到结果,而对于我们按位存入的高精度整数而言,要想对其进行加法运算,我们就需要返璞归真,首先,我们来回忆下小学时的加法,看图1: 从个位开始相加,结果放在横线下,如果相加的结果超过10,则进1到下一位。 没错,我们就是要所要依靠的就是这样一个简单的规则! 首先考虑到我们存储数字的方式:如果两个数字位数不同,则会出现超过数位的数字再相加时vector out of range的情况,所以我们要把两个数字一个一个加到结果的位置上(比如图1的个位,结果位原先是0,先把4加到结果位,结果位变为4,然后再把2加到结果为,变为6),这样可以方便我们对两个加数的各个位的情况进行把握。 下面就是加法运算的具体实现方法: [crayon-59c23149ca5bb484093256/...

高精度运算(1)结构

在解题过程中,经常会出现需要运算的数据超过系统内置的整型范围的情况,在这种时候我们就需要用到高精度运算算法,我将分几篇文章来解释,如何实现高精度运算,并且我将会将高精度运算封装为一个命名为BigInt的高精度整数类,方便未来的使用。 在本篇中,主要实现的是高精度整数的存储、输入与输出。 在给出具体的实现之前,我先介绍一点预备知识,关于C++标准库vector。 vector这个词在上一篇文章中提及过,vector是C++提供的一种顺序容器,而对于vector这种容器来说,其特点就是支持快速的随机访问(想一想数组通过下标值访问的方式),作为一种可变长的容器,我们可以把它当作一种“高端的数组”,用vector来存储高精度整数的好处在于可以解决由大整型数组来存数高精度整数时所造成的空间浪费问题。 我们对于高精度整数的存储方式是按位存储,为了避免运算的时候对齐各个位时产生麻烦,所以我们从个位开始存储,也就是说,在vector容器中存储的数字顺序,与你实际看到的数字顺序是正好相反的。 下面就给出具体

栈(stack)是一种数据结构,它遵循一个简单的规则,即后进先出(Last in First out, LIFO)。 栈的工作方式很容易理解,用一个图表形象的表示就是这样,见图1: 这个只有上端开口的容器,就是用来存放数据的栈,我们要取容器中的东西,必须从最顶端开始,一个一个拿掉,才能取到我们想要的,而如果要放一个元素呢,也只能放在最顶端,这也就是栈的后进先出原则。 这样的数据结构可以使用C++标准库来实现,非常简单,下面就对C++标准库中的栈做一点简介: C++提供了三种顺序容器(sequential container)vector(支持快速随机访问)、list(支持快速插入删除)、deque(双端队列),vector比较类似与数组,而list则更加像链表结构。C++标准库为顺序容器提供了三种容器适配器(adaptor), 不要被名字吓到,所谓适配器,就像你的电脑电源适配器一样,将交流电(这里是顺序容器)做出一定的调整,来适合电脑工作,也就是说,容器适配器,是利用容器来...

DP记忆化搜索

动态规划(dynamic programming)这个名词曾不止一次吓到我,而事实上,动态规划作为一种思想而非算法,其最大的作用是优化。这次笔记中,我就对最为经典的The Triangle[1]问题来对DP的记忆化搜索进行解释。 如图1,从三角形的最上面的顶点往下层走(每次只能向左或向右一个),那么如何走,才能途径的所有位置的点数之和最大呢? 第一种自然而然的思路就是把所有可能的路径都找到,并找到其中点数和最大的一条路径作为答案,然而这样的思路却存在着很大的效率问题,从第一个顶点开始往下走,每走一步都有2种选择,那么走到第N层的时候,路径数目就多达2^N条,枚举如此巨大数目的路径,必然会使程序在测试的过程中出现超时(TLE),所以这样的方法并不可取。 至此,我们可以隆重推出动态规划的思想了,我们从结果来看,答案的路径是确认的,那么第一步只有向左或向右才可能到达最终答案的地点,第二步也是,第三步也是……在这个过程中,我们往下走,只选择“能到达最优解”的路径走,这样就可以帮助我们减少大量的搜索