存档

‘Cpp’ 分类的存档

基于2进制的大数类

2010年5月25日 1 条评论

我写的另一个大数类，基于二进制（确切的说在32位机下是2^31次进制），乘法是用移位和加法模拟的（如果不是考虑到64位兼容性的话，用long long可以显著提高乘法效率），除法是移位和减法（状况同乘法），效率上比我原来的那个低了很多（有兴趣的可以看我之前的文章，基于10^9次进制的大数类），尤其是输出函数。但毕竟是是我精心设计的，很多方面感觉还是很有价值的

有需要的朋友可以下载我的源码（基于code::blocks的工程）

下面是其中的一个头文件，包括了大数类的主要声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#ifndef LARGEINT_H_INCLUDED
#define LARGEINT_H_INCLUDED
 
#include "numarray.h"
 
const int bits=8*sizeof(numunit)-1;         //每一个存储单位的2进制位数
const int intlim=1000000000;//numunit能够容纳的最大的10的幂
const int intlimbits=9;//上面那个intLim的十进制位数（幂）
 
class largeInt
{
private:
    numArray number;     //反序保存数剧本身，最低位是number[0]
    int length;          //number的长度
    int sign;            //符号1表示正，-1表示负数，特殊的,有两个0,保证0的符号是1
public:
    largeInt() {length=1;sign=1;}
    largeInt(int in) {length=1;sign=(in>=0)?1:-1;number[0]=(numunit)sign*in;}
    largeInt(const largeInt &in) {number=in.number;length=in.length;sign=in.sign;}
    largeInt& operator=(const largeInt &in) {number=in.number;length=in.length;sign=in.sign;return *this;}
    largeInt operator-() const {largeInt opposite=(*this);opposite.sign=-sign;return opposite;}
    void opposite() {sign*=-1;}
    //##I/O################################
    largeInt& read();
    largeInt& read(const char *);
    void print() const;
private:
    void printAll(largeInt &num) const;
    void printDecimalUnit(int unit,int len) const;
    void printDecimalUnit(int unit) const;
public:
    //##compare############################
    bool operator==(const largeInt&) const;
    bool operator>(const largeInt&) const;
    bool operator<(const largeInt&) const;
    bool operator>=(const largeInt &right) const {return !(*this<right);}
    bool operator<=(const largeInt &right) const {return !(*this>right);}
    bool operator!=(const largeInt &right) const {return !(*this==right);}
    //##movement###########################
    largeInt operator<<(int n) const {largeInt solution=*this;solution<<=n;return solution;}
    largeInt operator>>(int n) const {largeInt solution=*this;solution>>=n;return solution;}
    const largeInt& operator<<=(int);
    const largeInt& operator>>=(int);
private:
    void moveLeft(int);    //大移位，移1就是移动bits位
    void moveRight(int);
public:
    //##+ - * / %##########################
    largeInt operator++(int) {*this+=1;return *this-1;}//后缀运算
    const largeInt& operator++() {return *this+=1;}//前缀
    largeInt operator--(int) {*this-=1;return *this+1;}
    const largeInt& operator--() {return *this-=1;}
    //*************************************
    largeInt operator+(const largeInt &right) const {largeInt solution=*this;solution+=right;return solution;}
    const largeInt& operator+=(const largeInt&);
    largeInt operator-(const largeInt &right) const {largeInt solution=*this;solution-=right;return solution;}
    const largeInt& operator-=(const largeInt&);
    largeInt operator*(const largeInt&) const;
    largeInt operator*(int) const;
    const largeInt operator*=(const largeInt &right) {return *this=*this*right;}
    const largeInt operator*=(int right) {return *this=*this*right;}
    largeInt operator/(largeInt&) const;
    largeInt operator/(int) const;
    largeInt operator/(const largeInt &divi) const {largeInt divisor=divi;return *this/divisor;}
    const largeInt& operator/=(largeInt &divisor) {return *this=*this/divisor;}
    const largeInt& operator/=(const largeInt &divi) {largeInt divisor=divi;return *this/=divisor;}
    const largeInt& operator/=(int divisor) {return *this=*this/divisor;}
    largeInt operator%(const largeInt &divisor) const {largeInt solution;solution%=divisor;return solution;}
    largeInt operator%(largeInt &divisor) const {largeInt solution;solution%=divisor;return solution;}
    const largeInt& operator%=(largeInt&);
    const largeInt& operator%=(const largeInt &divisor) {largeInt divi=divisor;return *this%=divi;}
    const largeInt& operator%=(int);
    int operator%(int) const;              //特殊的取模函数，用于返回int型的余数
    //**************************************
    friend largeInt operator+(int a,const largeInt& b) {return b+a;}
    friend largeInt operator-(int a,const largeInt& b) {return -(b-a);}
    friend largeInt operator*(int a,const largeInt& b) {return b*a;}
    friend largeInt operator/(int a,const largeInt& b) {largeInt x=a;return a/b;}
    friend largeInt operator%(int a,const largeInt& b) {largeInt x=a;return a%b;}
private:
};
 
 
#endif // LARGEINT_H_INCLUDED
分类: Cpp 标签:

等比序列的前n项和

2010年5月11日 1 条评论

计算等比数列前n项和，首先想到高中学过的公式

这个公式是出色的，而且用逐次平方法就可以算出q^n，当然当n很大的时候，如果我们要对结果取模，那么显然这个公式中出现的除法是很糟糕的（取模运算不能对除法满足分配律），于是，我给出了下面的方法。首先看下面的式子：

你有发现什么吗？有没有看到里面的递推特性？
要知道我特意选了15，因为15的2进制表示中每一位都是1.很遗憾，这个式子我很难用逐次平方法那样显而易见的式子了表示，我只能说，两者是类似的（其实我觉得这已经是显而易见的了）。
我只能在下面的两个式子里，给出了一个基于二进制的标识，式子下面的一串数是二进制的各位，找规律吧

依然给出代码，这是一个O(lgn)的基于递推的算法，和用公式的效率是接近的。和递归的二分类似，但理解更困难

特别的，模p的代码就不加了，当然添加是很简单的 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int sum(int q,int n)
{
    int solution=0,temp=1;
    while(n) //n不为0就循环
    {
        if(n%2) //如果n是奇数
        {
            solution*=q;
            solution+=temp; 
        }
        temp*=(1+q);//生成上面式子中数字1所对应的表达式
        q*=q;
        n>>=1;
    }
    return solution;
}
分类: Cpp 标签:

逐次平方法(快速幂取模)

2010年5月11日 没有评论

快速幂取模，方法其实就是逐次平方法.计算a^k mod m:

将k表示成2进制,有

由ur的值决定该因子是否乘入（是就是1，否是0），每一个因子都可以由前一个递推的产生，于是，给出下面的函数(考虑到n会很大，所以对结果取模),时间上是O(lgn)的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int x_Power_k_Mode_m(int x,int k,int m)  //x^k(mod m)
{
    int solution=1;
    x%=m;
    while(k)
    {
        if(k%2)
        {
            solution*=x;
            solution%=m;
        }
        x*=x;
        x%=m;
        k>>=1;
    }
    return solution;
}
分类: Cpp, Math 标签:

Fibonacci序列 及其前n项和

2010年5月7日 3 条评论

Fibonacci序列：1，1，2，3，5，8，13，21，34，55...

递推式：fib(n)=fib(n-1)+fib(n-2),(n>2)

至于通项就不说了，找起来很容易

现在我们要计算Fibonacci的第n项，用递推是容易的，这是一个O(n)的算法，但是当n很大的时候显然不行（当然这个时候fib(n)本身也非常大，暂且不管它）。我刚学会了一种新方法——矩阵

其中的fib(n)=Fn.以次类推.这个公式很好证明.当然只是证明是不够的，我还没吃透它，先不管这点，看看怎么使用它.

令左边的矩阵为A，右边的矩阵为F(n+1), 则F(n)=A^(n-1)

定义矩阵的乘法之后，用逐次平方计算即可得到F(n),也就能得到fib(n),我在下面给出代码

那么我们怎么计算fib序列的前n项和呢？

考虑到S(n)=F(1)+F(2)+...+F(n-1)+F(n)=A^0+A^1+A^2+..+A^(n-1)

注意到中学的等比数列公式没?
(A-I)S(n)=A^n-I
其中I是二阶单位矩阵，左乘A-I的逆(A-I)^-1,就能得到S(n)了.
你算下就知道，逆就是A.于是S(n)=A*(A^n-I)逐次平方搞定，类似的还可以计算连续n项的和，提出第一项对应的矩阵就明白了，下面给出相关矩阵的代码，以及逐次平方实现

****推荐下英文的wiki，上面对于fib序列的描述是令人满意的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

struct matrix2
{
    long long num[2][2];
    matrix2(){num[0][0]=1;num[1][1]=1;num[0][1]=0;num[1][0]=0;}// 初始化为单位矩阵
};
int p=2010;//以为fib序列很大，所以结果全部mod p
matrix2 operator*(matrix2 x,matrix2 y)
{
    matrix2 solution;
    solution.num[0][0]=((x.num[0][0]*y.num[0][0])%p+x.num[0][1]*y.num[1][0])%p;
    solution.num[0][1]=((x.num[0][0]*y.num[0][1])%p+x.num[0][1]*y.num[1][1])%p;
    solution.num[1][0]=((x.num[1][0]*y.num[0][0])%p+x.num[1][1]*y.num[1][0])%p;
    solution.num[1][1]=((x.num[1][0]*y.num[0][1])%p+x.num[1][1]*y.num[1][1])%p;
    return solution;
}
matrix2 operator-(matrix2 x,matrix2 y)
{
    matrix2 solution;
    solution.num[0][0]=x.num[0][0]-y.num[0][0];
    solution.num[0][1]=x.num[0][1]-y.num[0][1];
    solution.num[1][0]=x.num[1][0]-y.num[1][0];
    solution.num[1][1]=x.num[1][1]-y.num[1][1];
    return solution;
}
matrix2 operator^(matrix2 h,int n) //计算h^n,逐次平方法O(lgn).令h=A，计算F(n+1)
{
    matrix2 solution;
    while(n)
    {
        if(n%2)
        {
            solution=solution*h;
        }
        h=h*h;
        n>>=1;
    }
    return solution;
}
分类: Cpp, Math 标签: ,

输出循环节，进制的游戏

2010年4月22日 2 条评论

首先给出一个特殊情况的分数m/n循环节输出(代码,基于小学就学过的除法笔算算法，p是进制，当然你可以全部用10替换)，我们先假设它的循环节是从小数点第一位开始（在下面我会用进制变换证明）

void printDecimalRec(int m,int n,int p) //这里假设m<n,且(n,p)=1,且输出省略“0.”
{
    int flag=m;
    do
    {
        m*=p;
        printf("%d",m/n);
        m%=n;
    }while(m!=flag);
}

分类: C, Cpp 标签: