C語言的高精度算法

1、高精度計算一 加法先判斷出兩個數(shù)哪個較長，兩個數(shù)從個位對齊后， 從個位數(shù)開始相加， 先不考慮進(jìn)位的問題， 相加直到較 短的數(shù)的最高位。 接著把較長的數(shù)未相加的部分進(jìn)行賦 值。最后在處理進(jìn)位問題 (判斷每位上的數(shù)是否大于等 于 10 )。其中要注意的是兩數(shù)相加，得到的和的位數(shù)是否比 較長的數(shù)的位數(shù)大 1。和進(jìn)位問題的處理。代碼：# include<stdio.h># include<string.h># include<malloc.h>void add(char* a,char* b,char* c)int i,j,k,max,min,n,temp;char

2、 *s,*pmax,*pmin;max=strlen(a); min=strlen(b);if (max<min)temp=max;max=min;min=temp;pmax=b;pmin=a;elsepmax=a;pmin=b;s=(char*)malloc(sizeof(char)*(max+1); s0='0'for (i=min-1,j=max-1,k=max;i>=0;i-,j-,k-) sk=pmini-'0'+pmaxj;for (;j>=0;j-,k-)sk=pmaxj;for (i=max;i>=0;i-)if (si&

3、gt;'9')si-=10;si-1+;if (s0='0')for (i=0;i<=max;i+)ci-1=si;ci-1='0'elsefor (i=0;i<=max;i+)ci=si;ci='0'free(s);二 減法先考慮減數(shù)大于被減數(shù)的情況。 也是先對齊， 再相 減，接賦值，最后是處理借位問題(判斷每位上的數(shù)是 否小于 0)。如果減數(shù)小于被減數(shù)的話，可以用被減數(shù)減去減 數(shù)。最后在結(jié)果的前面加個負(fù)號就可以了。源代碼：# include<stdio.h># include<string.h&g

4、t;# include<malloc.h>void subtract(char* a,char* b,char* c)int i,j,ca,cb;ca=strlen(a);cb=strlen(b);if (ca>cb|(ca=cb&&strcmp(a,b)>=0) for (i=ca-1,j=cb-1;j>=0;i-,j-) ai-=(bj-'0');for (i=ca-1;i>=0;i-)if (ai<'0')ai+=10; ai-1-;i=0;while (ai='0')i+;if (

5、ai='0')c0='0'c1='0'elsefor (j=0;ai!='0'i+,j+) cj=ai;cj='0'elsefor (i=ca-1,j=cb-1;i>=0;i-,j-) bj-=(ai-'0');for (j=cb-1;j>=0;j-)if (bj<'0')bj+=10; bj-1-;j=0;while (bj='0')j+;i=1;c0='-'for (;bj!='0'i+,j+)ci=bj; ci=

6、'0'三乘法 注意乘積的最大位數(shù)是兩個數(shù)的位數(shù)之和。先相 乘，再處理進(jìn)位問題。for (i=0;i<ca;i+)/ 相乘for (j=0;j<cb;j+)ci+j+1+=(ai-'0')*(bj-'0') ；源代碼：# include<stdio.h> # include<string.h># include<malloc.h>void multiply(char* a,char* b,char* c)int i,j,ca,cb,* s;ca=strlen(a);cb=strlen(b);s=(in

7、t*)malloc(sizeof(int)*(ca+cb);for (i=0;i<ca+cb;i+)si=0;for (i=0;i<ca;i+)for (j=0;j<cb;j+)si+j+1+=(ai-'0')*(bj-'0');for (i=ca+cb-1;i>=0;i-)if (si>=10)si-1+=si/10; si%=10;i=0;while (si=0)i+;for (j=0;i<ca+cb;i+,j+)cj=si+'0'cj='0'free(s);四 除法 高精度的除法最后的結(jié)果

8、整數(shù)部分和余數(shù)。其中 被除數(shù)一般是計算機(jī)可以表示的整數(shù)。源代碼：# include<stdio.h># include<malloc.h># include<string.h>int dividor(char* a,int b,char* c)int i,j,temp=0,n;char* s; n=strlen(a);s=(char*)malloc(sizeof(char)*(n+1);for (i=0;ai!=0;i+) temp=temp*10+ai-'0' si=temp/b+'0'temp%=b;si='0&#

9、39;for (i=0;si='0'&&si!='0'i+);if (si='0')c0='0'c1='0'elsefor (j=0;si!='0'i+,j+) cj=si;cj='0' free(s); return temp;例 1( ZOJ-1205)：在 22 世紀(jì)，科學(xué)家發(fā)現(xiàn)有外星人的存在。他們十分喜歡 數(shù)學(xué)。每年他們都舉行 ACM 比賽。題目是計算 2 個 100 位 數(shù)的和。誰用的時間最少，誰就獲勝。今年他們邀請我們?nèi)⒓铀麄兊谋荣悺６阈疫\的成為 我們

10、的代表去參賽?，F(xiàn)在你唯一的問題是編寫一個小程序去 計算 2個數(shù)的和。但是他們的數(shù)是 20 進(jìn)制。他們的數(shù)由 0-9 和 a-j （代表 10-19）表示。輸入：成對的給出一些他們用 20進(jìn)制表示的數(shù)， 每個數(shù)占一行。 而且每個數(shù)不會超過 100 位。輸出：對每一對數(shù)，在一行上輸出他們的和（還是用20 進(jìn)制表示）。分析：兩數(shù)相加，對齊后，從最后一位開始。先把各個位上的數(shù) 轉(zhuǎn)化成 10 進(jìn)制的數(shù)，再相加。最后把各個位上的數(shù)轉(zhuǎn)化成 20 進(jìn)制的數(shù)。 注意 2 個數(shù)的和， 最后位數(shù)可能跟較長的數(shù)相 同，可能大 1。源代碼：# include<stdio.h> # include<st

11、ring.h> int main()int i,min,max,j;char a101,b101,c102,*pmin,*pmax; while (scanf("%s %s",a,b)=2)if (a0='0'&&b0='0')printf("0n");elsefor (i=0;i<101;i+) ci='0'min=strlen(a);max=strlen(b) ；if (min<=max)pmin=a;pmax=b;elsei=min; min=max; max=i;

12、pmin=b;/判斷輸入是否結(jié)素/可能有點多余/*求每個數(shù)的長度 把較長的數(shù)的地址賦給 pmax 較短的賦給 pmin 這樣可以節(jié)省考慮的情況*/pmax=a;i=j=max; cmax+1='0'for (min-,max-;min>=0;i-,min-,max-)if (pminmin>='a')if (pmaxmax>='a') ci=pmaxmax-'a'+pminmin-'a'+20+'0'else ci=pminmin-'a'+pmaxmax+10;/*

13、先將 2 個數(shù)從最后一位對齊 在從最后一位開始相加 在相加的時候把 20 進(jìn)制的 數(shù)轉(zhuǎn)化成 10 進(jìn)制的數(shù) 一直加到較短那個數(shù)的 最高位為止*/elseif (pmaxmax>='a')ci=pmaxmax-'a'+pminmin+10;elseci=pmaxmax-'0'+pminmin;for (;max>=0;max-,i-)if (pmaxmax>='a')ci=pmaxmax-'a'+10+'0'elseci=pmaxmax;for (i=j;i>=0;i-)if

14、(ci>='0'+20)ci=ci-20;ci-1+;if (ci>='0'+10)ci=ci-'0'-10+'a'elseif (ci>='0'+10)ci=ci-'0'-10+'a'i=0;while (ci='0')i+;while (ci!='0')printf("%c",ci+);printf("n");return 0;/*把較長的數(shù)未相加的數(shù)賦給 C 注意轉(zhuǎn)換進(jìn)制*/* 再把相加的

15、每一位置上的數(shù) 從 10 進(jìn)制轉(zhuǎn)換成 20 進(jìn)制*/*最后判斷 2 個輸相加后， 得到的數(shù)的位數(shù)會不會比 較長的數(shù)的位數(shù)長*/例 2( ZOJ-1962)：考慮 Fibonacci 數(shù)，f1 := 1f2 := 2fn := fn-1 + fn-2 (n >= 3) ；給你 a,b 兩個整數(shù)，要你計算在a,b 間的 Fibonacci 數(shù)有多少個a,b。輸入：有多組測試，每組測試有 2 個非負(fù)的整數(shù)。當(dāng) a=b=0 是 輸入結(jié)束。而且 a <= b <= 10A100。輸出：對于每組數(shù)據(jù)，在單獨一行輸出滿足條件的Fibonacci 數(shù)的個數(shù)。注意：其中要用到線性表(屬于動態(tài)規(guī)

16、劃內(nèi)容)。分析：首先將 0-10A100 之間的 Fibonacci 數(shù)保存在數(shù)組 P 里。在 計算 Fibonacci 數(shù)的時候用開線性表的方法，否則會超時。對于輸入的 a,b 先在 P 里找到第一個大于等于 a 的Fibonacci數(shù)，并標(biāo)記此位置為j。再找第一個大于等于b的Fibonacci 數(shù)，標(biāo)記為 k。貝U a,b 間的 Fibonacci 數(shù)為 k-j.源代碼：# include<stdio.h># include<string.h># include<malloc.h>/高精度加法int add(char* a,char* b,char* c

17、)int i,j,k,max,min,n,temp;char *s,*pmax,*pmin;max=strlen(a);min=strlen(b);if (max<min)temp=max; max=min; min=temp; pmax=b; pmin=a;elsepmax=a;pmin=b;s=(char*)malloc(sizeof(char)*(max+1); s0='0'for (i=min-1,j=max-1,k=max;i>=0;i-,j-,k sk=pmini-'0'+pmaxj;for (;j>=0;j-,k-) sk=pma

18、xj;for (i=max;i>=0;i-)if (si>'9')si-=10;si-1+;if (s0='0')for (i=0;i<=max;i+)ci-1=si; ci-1='0' free(s); return max;else12for (i=0;i<=max;i+) ci=si;ci='0' free(s); return max+1;int main()int n,i,j,k;char p1000102,min101,max101;p00='1'p01='0'p

19、10='2'p11='0'n=1;for (i=2;n<101;i+)n=add(pi-1,pi-2,pi);scanf("%s %s",min,max);while (min0!='0'|max0!='0')j=strlen(min); k=strlen(max);for (i=0;i+)n=strlen(pi);if (n>=j)if (n=j)if (strcmp(pi,min) break;elsebreak;j=i;for (;i+)n=strlen(pi);if (n>=k)/*

20、首先開線性表，把在 都求出來，記錄在*/判斷 a,b 是否等于 0/查找第一個大于等于0-10X00 的數(shù)P 里。a 的 Fibonacci 數(shù)0)/查找第一個大于等于 b 的Fibonacci 數(shù)if (n=k)14if (strcmp(pi,max)>0) break;elsebreak;k=i;printf("%dn",k-j);scanf("%s %s",min,max);return 0;例 3( ZOJ-1923)：定義一種整數(shù)的連乘規(guī)則：給出一個數(shù)，它的各個位上的數(shù)的乘積，得到一個新的數(shù)。這個數(shù)在做這種運算，直到 最后得到的數(shù)是一位的

21、為止。如：679 -> 378 -> 168 -> 48 -> 32 -> 6 。我們說 679 要經(jīng)過 5 次這樣的運算得到是一位數(shù)。 假定一位數(shù)運算這種規(guī)則所要用的次數(shù)是 0?，F(xiàn)在你要解決的問題是：求最小的數(shù)經(jīng)過一次 這種乘法運算得到結(jié)果是給出的已知的數(shù)。輸入：每一組測試是一個十進(jìn)制的數(shù)，它的位數(shù)最多 1000 位。以 -1 作為測試結(jié)束的條件。輸出：對于每一組測試， 輸出滿足條件的數(shù)。 如果這個數(shù)存在， 輸出“ There is no such number ”。輸入：011851768-1輸出：101129There is no such number.2

22、688分析：首先發(fā)現(xiàn)，一個數(shù)經(jīng)過這種運算之后，要么是等于由 2-9 之間的數(shù) 的乘積，要么為 0 。所以判斷一個數(shù)能不能進(jìn)行這種規(guī)則的逆運算，至 需判斷它素因子只有 2，3，5 或 7。如果能進(jìn)行逆運算，找滿足條件的 最小的數(shù)，只須從 9 開始判斷能不能被整除，能的話就除以 9，再看能 不能被 9 整除，直到不能被整除， 并標(biāo)記能除以 9 的次數(shù)。接著考慮 8， 一直到 2 。最后把這些能整除的數(shù)從低向高排列就可以了。如 768 ，不能被 9 整除，考慮 8，能整除，且次數(shù) 2 ；接著是 6，次 數(shù) 1；最后是 2 ，次數(shù) 1。所以 768 可以分解成 2，6，8 ，8，要求的數(shù) 就是 268

23、8 。不過要注意特殊情況的出現(xiàn)，如果輸入的數(shù)是一位的話。那滿足條 件的數(shù)，是在它的前面加 1，就可以了。（因為滿足條件的數(shù)必須經(jīng)過 最少經(jīng)過一次這種運算。 所以要求的數(shù)最少是 2 位數(shù)，而在 2 位數(shù)里只 有 10 幾是最小的）源代碼：# include<stdio.h># include<string.h> /判斷一個數(shù)能不能整除另一個數(shù)bool judge(char* s,int n)int m,i;for (i=0,m=0;si!='0'i+)m=m*10+si-'0'if (m>=n)m=m%n;if (m=0)return true;elsereturn false;i