大数問題に関する個人的な理解

2747 ワード

大数の問題も初めて接触したわけではありませんが、こまごまといくつかの問題をしただけで、系統的に整理したことはありません.そして、自分の処理に多少の欠陥があるので、ここで整理します.
一、大数の記憶:対応して、大数の記憶は各ビットを配列の中に記憶すべきであるが、注意が必要な場合、配列の記憶は0から始まるので、大数の記憶は時数の逆記憶である.以前は自分の時に順方向に記憶していたので、計算キャリーに迷惑をかけ、逆方向記憶はキャリー問題をよく記憶し、管理することができる.struct bign{
int d[1000];
int len;
bign(){
    memset(d,0,sizeof(d));
    len=0;
}

};`ここでは構造関数を用いて、構造体が創立されたときに最初の時間に初期化できることを保証する.
初期化して数字を読み込む場合、私たちも数字を逆順序に処理する必要があります.
struct bign{
    int d[1000];
    int len;
    bign(){
        memset(d,0,sizeof(d));
        len=0;
    }
};

だから、異なる2つの数字について、私たちが比較する方法は以下の定義があります:もし長さが異なるならば、長いのは大きいです;長さが同じであれば、高位から1つずつ比較(すなわち逆列挙)し、数字が大きいものを見つける.
int compare(bign a,bign b){
    if(a.len>b.len)
        return 1;
    else if(a.len=0;i--){
            if(a.d[i]>b.d[i])
                return 1;
            else if(a.d[i]

二、加算演算:加算に対して、私たちは必ず進位問題に注意しなければならない.そして、正と負の時に直接減算演算をすることができ、いずれも負の数に加算し、後に記号を加えればよい.以下に示す
bign add(bign a,bign b){
    bign c;
    int carry=0;//carry 
    for(int i=0;i

上記のループ操作は、最短数字の後ろが0であるため、長いどのビットの本位を直接加算する要素に相当し、さらに進位(短い遍歴が完了した後carryが0になる)の後のif判断は、2つの数字のシーケンスの長さが等しい場合、新たにより高いビットの記憶進位を開くべきであることに注意すべきである.
三、減算:減算と加算はほぼ同じで、シーケンスの低位から始まるが、借位思想を持つように注意する必要がある.また、被減数が減数より小さい場合は、位置を交換して減算し、負の番号を出力するだけでよい.
bign sub(bign a,bign b){
    bign c;
    for(int i=0;i=1&&c.d[c.len-1]==0){
        c.len--;
    }
}

注意点は2つあります.1.ここでのビットは隣接する高位-1であり、本位+10が減算される動作である.2.高位相減算=0の可能性があるが、lenは任意にカウントする可能性があるため、高位から高位の先頭0を除去する.
四、高精度と低精度乗算:ここでいう高精度とは配列で保存された大数であり、低精度とはintで保存された数字である.仮に、配列が保存されている数は3桁、intが保存されている数は2桁で、普通の小学校の数学乗算とは異なり、intが保存されている2桁を採用し、配列が保存されている3桁を1つずつ積算すると、手書き演算の2回ではなく3回の演算が行われます.
bign multi(bign a,int b){
    bign c;
    int carry=0;
    for(int i=0;i

実は加算演算と似ています.計算が完了したが、carryが0でない場合、最後の操作はcarryをビット単位で上位に送ることに相当する.
五、高精度と低精度の除法:手書き除法と類似しており、このビットが除かれていない場合は、そのビットを保持し、置商は0であり、次のビットと1つの数を構成し、除けるかどうかを見るので、本質的には、コードの中で余剰数に対して除法操作を行うべきである.
bign divide(bign a,int b,int&r){
    //r 
    bign c;
    c.len=a.len;// 
    for(int i=a.len-1;i>=0;i--){
        r=r*10+a.d[i];
        if(r=1&&c.d[c.len-1]==0){
        c.len--;
    }
    return c;
}

ここで注意しなければならないのは、高位は依然として0操作を除去する必要があることである.0を含む場合、商の桁数は除数された桁数と一つ一つ対応しなければならない.これは私たちの境界判別条件の一つである.