ITeye博客

蛋→恋饭&

EGG_BMJIAOYANG · 共 6 篇文章

筛素数法的进阶

最简单的筛素数法方法就是从2开始,将所以2的倍数去掉,然后从3开始,将3的倍数去掉。根据这样很容易写出代码,下面代码就是是筛素数法得到100以内的素数并保存到primes[]数组中。 //by MoreWindows( http://blog.csdn.net/MoreWindows ) const int MAXN = 100; bool flag[MAXN]; int primes[MAXN / 3], pi; void GetPrime_1() { int i, j; pi = 0; memset(flag, false, sizeof(flag)); for (i = 2; i < …

2012-07-25 10:24 · C++ · 评论(0)

C/C++中二维数组的分配

在C/C++中动态分配二维数组可以先申请一维的指针数组,然后该数组中的每个指针再申请数组,这样就相当于二维数组了,但是这种方法会导致每行可能不相邻,从而访问效率比较低。如何申请连续的二维数组了?本文将分别三个方面讲解: 一.动态申请列大小固定的二维数组 二.C语言中动态申请连续的二维数组 三.C++语言中动态申请连续的二维数组 一.动态申请列大小固定的二维数组 首先如果二维数组的列大小固定,那么很简单,可以用申请一维数数组再其指针强制转化成为二维数组指针即可。详见代码: //列大小固定的二维数组可以申请一维数据并将指针强转成二维数组 #include <stdio.h> int main()…

2012-07-24 21:41 · C++ · 评论(0)

C++大数

分别使用C++中的运算符重载的方法来实现大数之间的数学运算,包括加法、减法、乘法、除法、n次方、取模、大小比较、赋值以及输入流、输出流的重载。。 #include #include #include #include using namespace std; #define MAXN 9999 #define MAXSIZE 10 #define DLEN 4 class BigNum { private: int a; //可以控制大数的位数 int len; //大数长度 public: BigNum(){ len = 1;memset(a,0,sizeof(a)); } //构造函数 …

2012-07-24 11:10 · C++ · 评论(0)

斐波那契数列的实现

一:递归实现 使用公式f=f+f,依次递归计算,递归结束条件是f=1,f=1。 二:数组实现 空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快。 三:vector 实现 时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源。 四:queue 实现 当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector 一样,但队列太适合这里了, f(n)=f(n-1)+f(n-2),f(n)只和f(n-1)和f(n-2)有关,f(n)入队列后,f(n-2)就可以出队列了。 五:迭代实现 迭代实现是最高效的,时间复…

2012-07-24 11:07 · C++ · 评论(2)

约瑟夫环的改进

首先,约瑟夫环的数学优化方法为: 为了讨论方便,先把问题稍微改变一下,并不影响原意:问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号。 我们知道第一个人(编号一定是(m-1)%n) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m%n的人开始): k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2 并且从k开始报0。现在我们把他们的编号做一下转换: k --&gt; 0 k+1 --&gt; 1 k+2 --&gt; 2 n-1 --&gt; n-1-k 0--&gt; n-k …

2012-07-24 11:03 · C++ · 评论(0)

acmの单调队列

********一、 什么是单调(双端)队列 单调队列,顾名思义,就是一个元素单调的队列,那么就能保证队首的元素是最小(最大)的,从而满足动态规划的最优性问题的需求。 单调队列,又名双端队列。双端队列,就是说它不同于一般的队列只能在队首删除、队尾插入,它能够在队首、队尾同时进行删除。 【单调队列的性质】 一般,在动态规划的过程中,单调队列中每个元素一般存储的是两个值: 1、在原数列中的位置(下标) 2、 他在动态规划中的状态值 而单调队列则保证这两个值同时单调。 从以上看,单调队列的元素最好用一个类来放,不这样的话,就要开两个数组。。。 单调队列:单调队列 即保持队列中的元素单调递增(或递减…

2012-07-24 10:59 · 技术概念以应用 · C++ · 评论(0)