之前早就想把學(xué)過的算法記錄下來(lái)涂籽，但是一直沒有時(shí)間吕喘。最近在給五年級(jí)的小學(xué)生上OI的算法課，所以正好可以把所思所想留存下來(lái)矮固。
一失息、為什么需要高精度運(yùn)算
當(dāng)要處理的數(shù)據(jù)超過了任何一種數(shù)據(jù)類型所能容納的范圍，這種數(shù)稱為高精度數(shù)档址，必須自定義類型來(lái)存儲(chǔ)盹兢。同時(shí)還要自行編寫高精度數(shù)的運(yùn)算函數(shù)（加\減\乘\除等）辆亏。
基本整數(shù)類型的取值范圍
| 類型 | 數(shù)值范圍 | 占字節(jié)數(shù) |
|---|---|---|
| char | -128 .. 127 | 1 |
| unsigned char | 0 .. 255 | 1 |
| int (long) | -2147483648 .. 2147483647 | 4 |
| unsigned int (long) | 0 .. 4294967295 | 4 |
| long long | -9223372036854775808 .. 9223372036854775807 | 8 |
| unsigned long long | 0 .. 18446744073709551615 | 8 |
二循头、高精度數(shù)的輸入和存儲(chǔ)
在運(yùn)算對(duì)象的數(shù)值范圍為任何數(shù)據(jù)類型所無(wú)法容納的情況下漓摩，采用數(shù)組（每一個(gè)元素對(duì)應(yīng)一位十進(jìn)制數(shù)顽爹，由其下標(biāo)順序指明位序號(hào)）來(lái)表示一個(gè)數(shù)，就稱為高精度數(shù)跃惫。
- 采用字符串形式輸入体谒，并將其轉(zhuǎn)化為整數(shù)數(shù)組填抬。
- 用一個(gè)整型變量記錄數(shù)據(jù)的實(shí)際長(zhǎng)度（即數(shù)組的元素個(gè)數(shù)）
字符串到整數(shù)數(shù)組的轉(zhuǎn)換
字符串存儲(chǔ)時(shí)窘问，數(shù)的高位被存放在字符串的低位辆童。轉(zhuǎn)換成整數(shù)數(shù)組時(shí)宜咒，要把高精度數(shù)的低位“還原”到數(shù)組的低位惠赫。這樣才便于后續(xù)計(jì)算。a[1]存放最低位故黑，a[6]存放最高位儿咱。高精度數(shù)的位數(shù)可存放在a[0]中。也可以另用一個(gè)變量存放场晶。
例如
字符串s: 763218
轉(zhuǎn)化成整數(shù)數(shù)組：6812367
其中數(shù)組第一個(gè)元素6是數(shù)組的位數(shù)
高精度數(shù)類型的定義與讀入
const int MAXLEN = 241; //最大長(zhǎng)度為240位
typedef int hp[MAXLEN]; //定義hp為高精度類型
void Str2hp(string s,hp &a) //s轉(zhuǎn)換后存入a
{
int i, len;
memset(a, 0, sizeof(a)); //clear a
len = s.size();
a[0] = len; //save the length
for (i=0; i<len; i++) //convert
a[len-i] = s[i] - '0';
}
輸出
void Print(hp a)
{
int i, len;
len = a[0]; //get the length
for (i=len; i >=1; i--)
cout << a[i];
cout << endl;
}
三混埠、高精度加法
問題表述：輸入a，b（<10^240）兩個(gè)數(shù)诗轻，輸出a+b的值钳宪。
樣例輸入：
99999999999999999999
12345678901234567890
樣例輸出：
112345678901234567889
算法思想類似于豎式加法運(yùn)算，注意進(jìn)位處理扳炬。把計(jì)算結(jié)果存到c中：
- 先計(jì)算：直接將a[i]和b[i]相加吏颖，結(jié)果放在c[i]中。
- 處理進(jìn)位：從最低位開始恨樟，逐位整理：把本位模10半醉，向高一位進(jìn)位。
c[i+1] += c[i] / 10;
c[i] = c[i] % 10;
- 去掉最高位的0：因?yàn)閮蓴?shù)相加,也可能不產(chǎn)生進(jìn)位劝术，因此要把這種情況下最高位的0去掉缩多，其實(shí)就是減小和的長(zhǎng)度len的值呆奕。
while ( (len>1) && (c[len] ==0))
len--;
void add(hp a, hp b, hp &c) //Add a, b to c
{
hp d;
int i, len;
memset(d, 0, sizeof(d)); //d清0
if (a[0] > b[0]) len = a[0];//求和的位數(shù)
else len = b[0];
len++; //位數(shù)加1
for (i=1; i<=len; i++) //逐位相加
d[i] = a[i] + b[i];
for (i=1; i<len; i++) //處理進(jìn)位
{
d[i+1] += d[i] / 10;
d[i] %= 10;
}
while ( (len > 1) && (d[len] == 0)) //處理最高位
len--;
d[0] = len;
memcpy(c, d, sizeof(d)); //保存結(jié)果
}
四、高精度減法
問題表述：輸入a衬吆，b（<10^240）兩個(gè)數(shù)梁钾，輸出a-b的值。
樣例1輸入：
456
409
樣例1輸出：
47
樣例2輸入：
999
1000
樣例2輸出：
-1
- 比較a和b的大小咆槽，從而確定結(jié)果的正負(fù)號(hào)
- a陈轿、依照由低位至高位的順序進(jìn)行減法運(yùn)算；b秦忿、在每一次位運(yùn)算中麦射，若出現(xiàn)不夠減的情況(a[i]<b[i])，則向高位借位灯谣；c潜秋、在進(jìn)行了減運(yùn)算后，若高位為0胎许，則要減少結(jié)果的長(zhǎng)度峻呛。在具體計(jì)算過程中，仍然用abc三步走的辦法辜窑。
void sub(hp a, hp b, hp &c) //a must be greater than b
{
int i, len;
hp d;
memset(d, 0, sizeof(d)); //clear d
len = a[0];
for (i=1; i<=len; i++)
d[i] = a[i] - b[i];
for (i=1; i<=len; i++)
if (d[i] < 0) //處理借位
{
d[i] += 10;
d[i+1] -= 1;
}
while ( (len > 1) && (d[len] == 0) ) //整理差的長(zhǎng)度
len--;
d[0] = len;
memcpy(c, d, sizeof(d));
}
注意：保存結(jié)果的數(shù)組使用前一般都要清零钩述；循環(huán)控制變量一般用 i 、 j 穆碎、 k牙勘，一般不要用m、n等所禀，長(zhǎng)度用len表示方面，這樣容易找錯(cuò)誤。
五色徘、比較兩個(gè)高精度數(shù)大小
當(dāng)a>b恭金，返回1； a<b,返回-1褂策；a==b横腿，返回0
int compare(hp a, hp b)
{
int i;
if (a[0] > b[0]) return 1;
if (a[0] < b[0]) return -1;
for (i=a[0]; i>=1; i--)
if (a[i] > b[i]) return 1;
else if (a[i] < b[i]) return -1;
return 0;
}
例題：求Fibonacci數(shù)列的第n項(xiàng)
Fibonacci數(shù)列的代表問題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖問題”(又稱“Fibonacci問題”)。問題：有雌雄一對(duì)兔子斤寂，假定過兩個(gè)月后便每個(gè)月可繁殖雌雄各一的一對(duì)小兔子耿焊。問過n個(gè)月后共有多少對(duì)兔子？已知：N <= 1000
當(dāng)N<=93時(shí)扬蕊，可以用基本類型long long解決搀别，但是大于93就需要使用到高精度算法。
void fibo (int n, hp & ans)
{
hp f0, f1, t;
int i;
memset(ans, 0, sizeof(ans));
f0[0] = 1; f0[1] = 1;
f1[0] = 1; f1[1] = 1;
if ( (n == 1) || (n == 2) )
{
ans[0] = 1;
ans[1] = 1;
return ;
}
for (i=3; i<=n; i++)
{
add(f0, f1, t);
memcpy(f0, f1, sizeof(f1));
memcpy(f1, t, sizeof(t));
}
memcpy(ans, f1, sizeof(f1));
}
六尾抑、高精度數(shù)乘以整形數(shù)運(yùn)算
問題表述：精確計(jì)算n的階乘n!（7<n<80）
樣例輸入：
20
樣例輸出：
2432902008176640000
- 估算n!所需的高精度數(shù)組長(zhǎng)度
- 被乘數(shù)（高精度）從低位向高位逐位乘以乘數(shù)（整數(shù)）
因?yàn)?0!<8080<10080=(102)80=10^160歇父，所以80蒂培！可以用160個(gè)數(shù)組元素a[1]a[2]…a[160]來(lái)存放，一個(gè)數(shù)組元素存放一個(gè)數(shù)位上的數(shù)字榜苫。同樣的方法护戳，可以估算出100！可以用200位的數(shù)組來(lái)存放垂睬。
void multiply(hp a, int b,hp &c)
{
hp d;
int i, len, t;
memset(d, 0, sizeof(d));
len = a[0];
for (i=1; i<=len; i++)
{
t = a[i] * b + d[i];
d[i] = t % 10;
d[i+1] = t / 10;
}
len++;
while (d[len])
{
d[len+1] = d[len] / 10;
d[len] %= 10;
len++;
}
while ( (d[len] == 0) && ( len > 1))
len--;
d[0] = len;
memcpy(c, d, sizeof(d));
}
int main()
{
int n, i;
hp ans;
cin >> n;
ans[0] = 1;
ans[1] = 1;
for (i=2; i<=n; i++)
multiply(ans, i, ans);
for (i=ans[0]; i>=1; i--)
cout << ans[i];
cout << endl;
return 0;
}
七媳荒、高精度數(shù)乘以高精度數(shù)
問題表述：輸入a，b（<10^100）兩個(gè)數(shù)驹饺，輸出a*b的值钳枕。
樣例輸入：
12345678900
98765432100
樣例輸出：
1219326311126352690000
- 積的位數(shù)為lena+lenb-1或者lena+lenb；
- 如果暫且不考慮進(jìn)位關(guān)系赏壹，則aibj應(yīng)該累加在積的第j+i-1位上：c[i+j-1] := a[i]b[j] + c[i+j-1];
- 可以先乘鱼炒、后處理進(jìn)位
void high_multiply(hp a, hp b, hp &c)
{
hp d;
int i, j, len;
memset(d, 0, sizeof(d));
for (i=1; i<= a[0]; i++)
for (j=1; j<= b[0]; j++)
d[i+j-1] += a[i] * b[j];
len = a[0] + b[0] + 1;
for (i=1; i<= len; i++)
{
d[i+1] += d[i] / 10;
d[i] = d[i] % 10;
}
while ((d[len] == 0) && (len > 1))
len--;
d[0] = len;
memcpy(c, d, sizeof(d));
}
int main()
{
int i;
hp a, b, ans;
string s1, s2;
cin >> s1;
cin >> s2;
str2hp(s1, a);
str2hp(s2, b);
high_multiply(a, b, ans);
for (i=ans[0]; i>=1; i--)
cout << ans[i];
cout << endl;
return 0;
}
八、高精度數(shù)除以整形數(shù)
問題表述：輸入a（<10^240） 蝌借，b（<10^9）兩個(gè)數(shù)昔瞧，輸出a/b的值和余數(shù)。
樣例輸入：
99887766554433221100
2001920
樣例輸出：
49895983133408
1077740
基本方法是從被除數(shù)的最高位開始菩佑，逐位計(jì)算商和余數(shù)自晰。存儲(chǔ)商。余數(shù)則轉(zhuǎn)移到下一次的被除數(shù)中稍坯。注意在下一次的計(jì)算中酬荞，余數(shù)要乘以10，然后再加上當(dāng)前位的被除數(shù)劣光。
void divide(hp a, int b, hp &c, int &r)
{
hp d;
int i, len;
memset(d, 0, sizeof(d));
r = 0;
len = a[0];
for (i = len; i>=1; i--)
{
r = r * 10 + a[i];
d[i] = r / b;
r = r % b;
}
while ( (len > 1) && (d[len] == 0))
len--;
d[0] = len;
memcpy(c, d, sizeof(d));
}
九袜蚕、練習(xí)題
階乘之和糟把，求1绢涡！+2！+3遣疯！+…+n雄可！
輸入數(shù)據(jù)(sumfac.in)：
一行，一個(gè)整數(shù)n （n<=100）
輸出數(shù)據(jù)(sumfac.out):
一行缠犀，1~n的階乘之和数苫。
輸入樣例：
5
輸出樣例：
153
