高精度計算
轉載://www.cnblogs.com/ECJTUACM-873284962/p/6509429.html
高精度的計算包括幾個方面:
1:對數據的存取
2:對數據的加減乘除(運算)
下面我將用著兩部分來講解:
1:高精度的存取.
2高精度的運算
1:用字元串讀入然後轉換成數組.
#include <iostream>
#include <cstring>
using namespace std;
const int N=100;//最多100位
int main()
{
int a[N+1],i;
string s1;
cin>>s1;//數s1
memset(a,0,sizeof(a)); //數組清0
a[0]=s1.length(); //位數
for(i=1;i<=a[0];i++) a[i]=s1[a[0]-i]-'0';//將字元轉為數字並倒序存儲．
return 0;
}
2:直接讀取(這種針對數字本身沒有超界的)
#include <iostream>
using namespace std;
const int N=100;//最多100位
int main()
{
int a[N+1],i,s,key;
cin>>key;//數key
memset(a,0,sizeof(a)); //數組清0
i=0;//第0位
while(key) //當key大於0
{
a[++i]=key%10;//取第i位的數
key=key/10;
}
a[0]=i; //共i位數
return 0;
}
2:高精度的運算:
1比較:
int compare(int a[],int b[]) //比較a和b的大小關係，若a>b則為1，a<b則為-1,a=b則為0
{int i;
if (a[0]>b[0]) return 1;//a的位數大於b則a比b大
if (a[0]<b[0]) return -1;//a的位數小於b則a比b小
//比較剩下的位
for(i=a[0];i>0;i--) //從高位到低位比較
{if (a[i]>b[i]) return 1;
if (a[i]<b[i]) return -1;}
return 0;//各位都相等則兩數相等。
}
2高進度加法:本質就是模擬豎式運算,如果大於9了就進位就讓前一位加加
int plus(int a[],int b[]) //計算a=a+b
{
int i,k;
k=a[0]>b[0]?a[0]:b[0]; //k是a和b中位數最大的一個的位數
for(i=1;i<=k;i++)
{
a[i+1]+=(a[i]+b[i])/10; //若有進位，則先進位
a[i]=(a[i]+b[i])%10;} //計算當前位數字,注意：這條語句與上一條不能交換。
if(a[k+1]>0) a[0]=k+1; //修正新的a的位數（a+b最多只能的一個進位）
else a[0]=k;
return 0;
}
}
3:高精度減法:
int gminus(int a[],int b[]);//計算a=a-b，返加符號位0:正數 1:負數
{
int flag,i
flag=compare(a,b); //調用比較函數判斷大小
if (falg==0)//相等
{
memset(a,0,sizeof(a));
return 0;
} //若a=b，則a=0,也可在return前加一句a[0]=1,表示是 1位數0
if(flag==1) //大於
{
for(i=1;i<=a[0];i++)
{
if(a[i]<b[i])
{
a[i+1]--;
a[i]+=10;
} //若不夠減則向上借一位
a[i]=a[i]-b[i];
}
while(a[a[0]]==0) a[0]--; //修正a的位數
return 0;
}
if (flag==-1)//小於 則用a=b-a,返回-1
{
for(i=1;i<=b[0];i++)
{
if(b[i]<a[i])
{
b[i+1]--;
b[i]+=10;
} //若不夠減則向上借一位
a[i]=b[i]-a[i];
}
a[0]=b[0];
while(a[a[0]]==0) a[0]--; //修正a的位數
return -1;
}
}
高精度乘法:高精度乘單精度數，單精度數是指通常的整型數
int multi1(int a[],long key) //a=a*key,key是單精度數
{
int i,k;
if (key==0)
{
memset(a,0,sizeof(a));
a[0]=1;
return 0;
} //單獨處理key=0
for(i=1;i<=a[0];i++)a[i]=a[i]*key;//先每位乘起來
for(i=1;i<=a[0];i++){a[i+1]+=a[i]/10;a[i]%=10;} //進位
//注意上一語句退出時i=a[0]+1
while(a[i]>0) {a[i+1]=a[i]/10;a[i]=a[i]%10;i++;a[0]++];} //繼續處理超過原a[0]位數的進位,修正a的位數
return 0;
}
高精度除法:演算法：按照從高位到低位的順序，逐位相除。在除到第j位時，該位在接受了來自第j+1位的餘數後與除數相除，如果最高位為零，則商的長度減一。源程式如下(模擬豎式的運算)
#include <stdio.h>
#define N 500
main()
{
int a[N] = {0}, c[N] = {0};
int i, k, d, b;
char a1[N];
printf("Input 除數:");
scanf("%d", &b);
printf("Input 被除數:");
scanf("%s", a1);
k = strlen(a1);
for(i = 0; i < k; i++) a[i] = a1[k - i - 1] - '0';
d = 0;
for(i = k - 1; i >= 0 ; i--)
{
d = d * 10 + a[i];
c[i] = d / b;
d = d % b;
}
while(c[k - 1] == 0 && k > 1) k--;
printf("商=");
for(i = k - 1; i >= 0; i--) printf("%d", c[i]);
printf("\n餘數=%d", d);
}
高精度乘以高精度:演算法：用數組保存兩個高精度數，然後逐位相乘，注意考慮進位和總位數。源程式如下：
#include <stdio.h>
main()
{
int a[240] = {0}, b[240] = {0}, c[480] = {0};
int i, j, ka, kb, k;
char a1[240], b1[240];
gets(a1);
ka = strlen(a1);
gets(b1);
kb = strlen(b1);
k = ka + kb;
for(i = 0; i < ka; i++) a[i] = a1[ka-i-1] - '0';
for(i = 0; i < kb; i++) b[i] = b1[kb-i-1] - '0';
for(i = 0; i < ka; i++)
for(j = 0; j < kb; j++)
{
c[i + j] = c[i + j] + a[i] * b[j];
c[i + j +1] = c[i + j +1] + c[i + j]/10;
c[i + j] = c[i + j] % 10;
}
if(!c[k]) k--;
for(i = k-1; i >= 0; i--) printf("%d", c[i]);
}
高精度初一高精度:
#include <stdio.h>
#define N 500
int bj(int a[], int b[], int k1, int k2) /*比較大小函數*/
{
int i, t, flag; /*flag作標誌位*/
if(k1 < k2)
flag = 0; /*被除數小於除數返回0*/
else if(k1 > k2)
flag = 1; /*被除數大於除數返回1*/
else
{ /*被除數和除數位數相等則逐位進行比較*/
i = k1;
t = 0;
while(t == 0 && i > 0)
{
if(a[i] > b[i]) {t = 1; flag = 1;}
else if(a[i] == b[i]) i--;
else {t = 1; flag = 0;}
}
if(i == 0 && t == 0) flag = 2; /*被除數等於除數返回2*/
}
return flag;
}
int jf(int a[], int b[], int k1, int k2) /*減法運算*/
{
int i, k, d[N];
for(i = 0; i < k2; i++) d[i] = b[i]; /*把除數賦給數組d*/
for(i = k2; i < N; i++) d[i] = 0; /*d數組無數據的高位置0*/
k = k1 - k2 - 1; /*計算減法起始位置*/
if(k < 0) k = 0;
if(k > 0)
{
for(i = k2 - 1; i >= 0; i--) d[i + k] = d[i]; /*移動減數位數與被減數對齊*/
for(i = 0; i < k; i++) d[i] = 0; /*移動後的其餘位置0*/
}
for(i = 0; i < k1; i++)
{
if(a[i] >= d[i]) a[i] -= d[i];
else
{
a[i + 1] = a[i + 1] - 1;
a[i] = 10 + a[i] - d[i];
}
}
return k;
}
main()
{
int a[N] = {0}, b[N] = {0}, c[N] = {0}, d[N] = {0};
int i, ka, kb, m, t, t1, t2, k, x, kd, kk;
char a1[N], b1[N];
printf("Input 被除數:");
scanf("%s", a1);
ka = strlen(a1);
for(i = 0; i < ka; i++) a[i] = a1[ka - i -1] - '0';
printf("Input 除數:");
scanf("%s", b1);
kb = strlen(b1);
for(i = 0; i < kb; i++) b[i] = b1[kb - i -1] - '0';
kd = ka; /*保存被除數位數 */
t2 = bj(a, b, ka, kb);
m = 0;
do
{
while(a[ka - 1] == 0) ka--;
t = bj(a, b, ka, kb);
if(t >= 1)
{
k = jf(a, b, ka, kb);
c[k]++;
if(k > m) m = k;
t1 = 0;
for(i = k; i <= m; i++)
{
x = c[i] + t1;
c[i] = x % 10;
t1 = x / 10;
}
if(t1 > 0) {m++; c[m] = t1; }
}
}while(t == 1);
if(t2 == 0)
{
printf("商=0");
printf("\n餘數=");
for(i = kd - 1; i >= 0; i--) printf("%d", a[i]);
exit(1);
}
if(t2 == 2)
{
printf("商 = 1");
printf("\n餘數 = 0");
exit(1);
}
kk = kd;
while(!c[kd - 1]) kd--;
printf("商 = ");
for(i = kd - 1; i >= 0; i--) printf("%d", c[i]);
while(!a[kk]) kk--;
printf("\n餘數 = ");
if(kk < 0)
{
printf("0");
exit(1);
}
for(i = kk; i >= 0; i--) printf("%d", a[i]);
}
