632 文字
2 分
高精度演算の学習記録
高精度演算
普段、加算・減算・乗算・除算は直接+-*/を使って実現しますが、数の長さが100や1000になると、intやlong longの格納範囲では足りなくなります。そんな時こそ高精度を使う時です。
1. 高精度加算 A+B
1.1 演算原理
まずは大きな数同士の加算です。通常の加算の手順を模して計算します。例えば下の図のように：
加算は後ろから前に向かって行われることが分かります。なので得られた大数をreverseして逆順にし、計算が終わったら正順に出力します。
1.2 例題
参考コード：
void solve(){ //... for(int i=0,c=0;i<max(a.length(),b.length()) || c;i++){ int t1=0,t2=0; if(i<a.length()) t1 = a[i]-'0'; if(i<b.length()) t2 = b[i]-'0'; int t = t1 + t2 + c; c = t / 10;t %= 10; ans.push_back(t+'0'); } //...}2. 高精度減算 A-B
2.1 演算原理
次に大きな数同士の減算です。具体的な方法は依然として大数加算と似ていますが、ABの大きさの差により結果が負になることがあります。その場合、A-B = -(B-A)として減算の結果を常に正に保つことができます。
P.S. 減算のため先頭ゼロが出現することがあります。出力前に除去してください。
2.2 例題
参考コード：
bool comp(){ if(a.length()!=b.length()) return a.length()>b.length(); for(int i=a.length()-1;~i;i--) if(a[i]!=b[i]) return a[i]>b[i]; return true;}void solve(){ //... if(!comp()) p = 1,swap(a,b); for(int i=0,c=0;i<a.length();i++){ int t1=0,t2=0; if(i<a.length()) t1 = a[i]-'0'; if(i<b.length()) t2 = b[i]-'0'; int t = t1 - t2 + c; if(t < 0) c=-1,t+=10; else c = 0; ans.push_back(t+'0'); }reverse(ans.begin(),ans.end()); if(p) cout<<"-";p=-1; while(++p<ans.length() && ans[p]=='0'); ans = ans.substr(min(p,(int)(ans.length()-1)),max((int)(ans.length()-p),1)); //...}3. 高精度乘法 A*b
3.1 演算原理
大数と小数の乗算は比較的単純で、Aの各桁とbの積和の残りを1つの値で記録します。順に各桁の計算結果を得るだけです。
P.S. 大きな数が0の時は積の先頭ゼロが出ることがあります。取り除いてください。
3.2 例題
参考コード：
void solve(){ for(int i=0,c=0;i<a.length() || c;i++){ int t1 = 0; if(i<a.length()) t1 = a[i]-'0'; int t = t1 * b + c; ans.push_back(t%10+'0');c = t / 10; }}4. 高精度除法 A/b
4.1 演算原理
同大数と小数の乘法、大数と小数の除法も同様に比較的簡単です。此時は大数の前半から順に後ろへ除いていき、前段とcをbで割った商と余りを順次記録します。
P.S. 初期の演算で被除数が小さすぎて先頭ゼロが出現することがあります。出力前に取り除いてください。
4.2 例題
参考コード：
void solve(){ for(int i=0;i<a.length();i++){ int t1 = a[i]-'0'; int t = t1 + 10 * c; ans.push_back(t/b + '0'); c = t%b; }int p = -1;while(++p<ans.length() && ans[p]=='0'); ans = ans.substr(min(p,(int)(ans.length()-1)),max(1,(int)(ans.length()-p)));} 共有
この記事が役に立ったときは、ぜひ他の人に共有してください!
一部の情報は古い可能性があります
関連した投稿 スマート
1
アルゴリズム学習：ビット演算・離散化・区間マージ
algorithm ビット演算、離散化、区間マージのアルゴリズムを紹介します。ビット演算は2進数処理に用いられ、離散化は疎データの保存・検索を最適化し、区間マージはソートと重なり判定によって複数区間を効率的に統合します。理解と応用を助けるため、関連する例題と参考コードも掲載しています。
2
ソートと二分探索の学習
algorithm クイックソートとマージソートの原理と実装を、時間計算量や関連問題とあわせて紹介します。クイックソートは中間値を基準に数列を2つに分割して整列し、マージソートは整列済み部分列を統合していきます。整数・浮動小数点数に対する二分探索アルゴリズムとその実装方法についても解説します。
3
アルゴリズム学習：前計算和・差分・双方向ポインタ
algorithm 前計算和（prefix sum）、差分配列、双方向ポインタ法（two pointers）の原理と応用を紹介します。前計算和は配列区間和を高速に計算し、差分配列は区間更新を効率化し、双方向ポインタ法はポインタを維持することでクエリ効率を最適化します。理解と応用を助けるため、関連例題と参考コードも掲載しています。
4
面接アルゴリズム学習1
algorithm 蛇行行列の埋め込み、単方向連結リストの高速ソート、ピーク値や極小値の探索、卵の硬度問題、最小値取得をサポートするスタック、連結リストの循環開始ノード探索など、複数のアルゴリズム面接問題とその解法をまとめています。各問題には詳細な説明、入出力形式、サンプルコードが付いています。
5
心理記録1
psycho 自分が感情を抑圧していることに気づき、過去の生活習慣が外界への恐怖と内面の停滞を招いてきたことを振り返る。世界との相互作用を通じて本当の自分を見つけたいと思い、進む方向を選ぶ責任感と、可能性を失うことへの恐れに向き合う。本当の自分は探求の中で形づくられる必要があり、未来の方向を選ぶことは他の可能性を手放すことを意味する。