一、数据输入
先将要计算的数据输入到内存中一般是按位存到数组中,按位对齐。
定义:第一位表示个位,n表示最高位。
1、利用字符串输入:先以字符串方式输入,再存入数组。对非法输入可以作检查,处理小数、有符号数比较方便。但需要对字符串操作比较熟悉。
字符串的输入和转换可用如下语句:
int a[100] = {0}, b[100] = {0};
int ka, kb, kc;
char a1[100], b1[100];
scanf(“%s”, a1);
scanf(“%s”, b1);
ka = strlen(a1); kb = strlen(b1);
for(i = 0; i<ka; i++) a[i] = a[ka – i - 1] – ‘0’;
for(i = 0; i<kb; i++) a[i] = a[kb – i - 1] – ‘0’;
字符串类型操作:
连接函数 strcat(str1, str2);
求字符串长度函数 strlen(str1)
2、带小数、正负号问题
①利用查找函数查找小数点(.)、正负号(+、-)
②记录小数点的位置和正负号。
③处理符号位。
3、位数对齐问题
①无小数位对齐:以个位对齐
②有小数位对齐:以小数点对齐
4、存储问题
①一位一存储 ②四位一存储
二、估算结果位数
高精度计算的结果位数要估算好,以便赋初值和控制循环次数。
设A、B为两个高精度数,结果为C,用LA、LB、LC分别表示A、B、C的位数。
加法:C=A+B LC=MAX(LA,LB)+1 是最长的位数加1
减法:C=A-B LC=MAX(LA,LB) 是最长的位数
乘法:C=A*B LC=LA+LB
除法:问题比较复杂,求商、余数、小数、可以不可以除尽,精确到小数点后几位。
一般取较大的位数作为结果位数。
阶乘、乘方的位数可以用对数求出。
1、XN的位数为计算
由数学知识可知:一个自然数的位数基本等于这个数的常用对数取整加1。由此可知对于XN来说它的位数为 = (int)n*log10(x) + 1
2、N!的位数计算
N!=N×(N-1)×(N-2)……×3×2×1
Log10(n!) = (int)(log10(n)+log10(n-1)+……+log10(2)+log10(1))+1
可用如下程序段求N!的位数:
int i,n,j;
double k=0;
scanf("%d",&n);
for(i=1;i<=n;i++) k+=log10(i);
j=(int)k+1;
三、计算和进位问题
高精度计算要求自己来编写进位。进位存放在CI中。
加法:
一位存储,CI=AI+BI+CI,若CI>10, 则CI=CI-10,CI+1=1
四位存储,CI=AI+BI+CI,若CI>10000,则CI=CI-10000,CI+1=1
减法:保证大数减小数。
一位存储,CI=AI-BI,若CI<0,则CI=CI+10,AI+1=AI+1-1
四位存储,CI=AI-BI,若CI>0,则CI=CI+10000,AI+1=AI+1-1
乘法:
一位存储,Y=AI*BI+C,C=Y整除10,AI=Y取模10
四位存储,Y=AI*BI+C,C=Y整除10000,AI=Y取模10000
除法比较复杂
1、A、B两数都为高精度数,利用减法求解。
2、A、B其中A为高精度数、B不是,可以利用除法。
3、A、B其中A不是高精度数、B是高精度数,利用除法减法求解。
4、A、B两数都不是高精度数,可以利用除法。精确到小数点后几位,判断循环小数。
乘法的控制:
for(i = 0; i < LA; i++)
for(j = 0; j < LB; 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;
}
四、输出问题
可以直接输出数组、或字符串。注意小数点位置,首尾的零。
五、优化程序
每个数组位置存四位整数逢10000进位,减少计算次数,提高运行速度。
六、高精度习题
问题1. 编程实现两个高精度实数加、减法,两数分别由键盘输入,均不超过240位。
1、加法运算a+b=c
算法:先确定a和b中的最大位数k,然后依照由低至高位的顺序进行加法运算。注意进位,若高位有进位,则c的长度为k+1。源程序如下:
#include <stdio.h>
main()
{
int a[240] = {0}, b[240] = {0}, c[241] = {0};
int i, ka, kb, k;
char a1[240], b1[240];
gets(a1); ka = strlen(a1);
gets(b1); kb = strlen(b1);
if(ka >= kb) k = ka;
else k = 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 < k; i++)
{
c[i] = a[i] + b[i] + c[i]; /*
c[i+1] = c[i+1] + c[i]/10;
c[i] = c[i]%10;
}
/* for(i=0;i<max;i++)
{ s=(A[i]+B[i]+c);
A[i]=s%10;
c=s/10;
}*/
if(c[k]) k++;
for(i = k-1; i >= 0; i--) printf("%d", c[i]);
}
当然也可把a+b的值直接存在a中,请大家在此基础上作出出修改。
2、减法运算a-b→a(a > b)
算法:依照由低位至高位的顺序进行减法运算。在每次位运算中,若出现不够减的情况,则向高位借位。在进行了la的减法后,若最高位为零,则a的长度减1。源程序如下:
#include <stdio.h>
main()
{
int a[240] = {0}, b[240] = {0};
int i, ka, kb;
char a1[240], b1[240];
gets(a1); ka = strlen(a1);
gets(b1); kb = strlen(b1);
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++)
{
if(a[i] < b[i])
{
a[i + 1]--;
a[i]+=10;
}
a[i] = a[i] - b[i];
}
while(!a[ka - 1])
{
ka--;
if(!ka) {printf("0"); break;}
}
for(i = ka-1; i >= 0; i--) printf("%d", a[i]);
}
若A、B大小未知,则需先判断大小。
问题2. 一个正整数的数字的乘积N的定义是:这个正整数中非零数字的乘积。例如:整数99数字乘积为9*9即81,81的数字乘积为8*1即8。
一个正整数的数字乘积根N是这样得到的:反复取该整数的数字乘积,直到得到一位数字为止。如:上题中99的数字乘积根为8。
编写一个程序,对于任意不超过70位数字的正整数,打印出计算其数字乘积根的每一步结果。例如:输入一个10位数9999999999,则输出如下:
9999999999
3486784401
516096
1620
12
2
算法:将正整数保存在数组中,高位在前、低位在后,首先去掉末位的‘0’,然后从第二位开始依次往前乘,低位在前、高位在后,完成一遍后,处理进位和去掉最高位的‘0’,最后再按正常顺序排放,重复上述过程直到仅一位为止。源程序如下:
#include <stdio.h>
main()
{
int a[100] = {0};
int i, j, k, m, n, l, temp;
char a1[100];
printf("Input N:\n");
gets(a1);
k = strlen(a1);
for(i = 0; i < k; i++) a[i] = a1[i] - '0';
if(k == 1) printf("%d\n", a[k - 1]);
while(k != 1)
{
while(a[k - 1] == 0) k--;
for(i = 1; i < k; i++)
{
for(j = 0; j < i; j++)
{
while(a[i] == 0)
{
for(m = i; m < k - 1; m++) a[m] = a[m + 1];
a[k - 1] = 0;
k--;
}
a[j] = a[i] * a[j];
}
for(n = 0; n < i-1; n++)
{
a[n + 1] = a[n + 1] + a[n] / 10;
a[n] = a[n] % 10;
}
a[i] = a[i - 1] /10;
a[i - 1] = a[i - 1] % 10;
if(a[i] == 0)
{
for(n = i; n < k - 1; n++) a[n] = a[n + 1];
a[k - 1] = 0;
k--;
i--;
}
}
while(a[k - 1] == 0) k--;
for(i = 0; i < k / 2; i++)
{
temp = a[i];
a[i] = a[k - i - 1];
a[k - i - 1] = temp;
}
for(i = 0; i < k; i++) printf("%d", a[i]);
printf("\n");
}
}
问题3.用高精度计算出s=1!+2!+3!+ …+n!。(n≤50)其中“!”表示阶乘,例如5!=5·4·3·2·1。输入正整数n,输出计算结果s。
算法:首先要确定结果的位数k,然后定义数组的大小,这一过程可单独做,并不需放在程序中。将阶乘的结果存放在数组并累加到S数组中,最后输出结果。源程序如下:
#include <stdio.h>
#include <math.h>
#define N 66
main()
{
int s[N] = {0}, a[N] = {0};
int i, j, k, n, digit = 1;
printf("Input N:");
scanf("%d", &n);
a[0] = 1;
s[0] = 1;
if(n == 1) printf("s= %d", s[0]);
for(k = 2; k <= n; k++)
{
for(j = 0; j < digit; j++) a[j] *= k;
for(j = 0; j < digit; j++)
{
if(a[j] >= 10)
{
a[j + 1] += a[j] / 10;
a[j] = a[j] % 10;
if(j == digit - 1) digit++;
}
}
for(i = 0; i < digit; i++) s[i] += a[i];
for(i = 0; i < digit; i++)
{
if(s[i] >= 10)
{
s[i + 1] += s[i] / 10;
s[i] = s[i] % 10;
if(i == digit - 1) digit++;
}
}
}
for(i = digit - 1; i >= 0; i--) printf("%d", s[i]);
}
问题4. 编程完成以下的高精度计算:
① 高精度乘以低精度;
算法:将多位数存入数组,低位在前、高位在后,然后用一位数去乘数组的各位,考虑进位,最后按按正常顺序输出。源程序如下:
#include <stdio.h>
#define N 200
main()
{
int a[N] = {0};
int i, j, k, m;
char b[N] = {0};
printf("Input two numbers:\n");
scanf("%d ", &m);
scanf("%s", b);
k = strlen(b);
for(i = 0; i < k; i++) a[i] = b[k - i - 1] - '0';
a[0] = a[0] * m;
for(i = 1; i < k; i++)
{
a[i] = a[i] * m;
a[i] = a[i] + a[i - 1] /10;
a[i - 1] = a[i - 1] % 10;
}
while(a[k - 1] >= 10)
{
k++;
a[k - 1] = a[k - 2] / 10;
a[k - 2] = a[k - 2] % 10;
}
for(i = k - 1; i>=0; i--) printf("%d", a[i]);
}
② 高精度除以低精度;
算法:按照从高位到低位的顺序,逐位相除。在除到第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;
if(k1 < k2)
flag = 0;
else if(k1 > k2)
flag = 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;
}
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];
for(i = k2; i < N; i++) d[i] = 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;
}
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]);
}
⑤ N!,要求精确到P位(0〈P〈1000〉。
算法:结果用数组a保存,开始时a[0]=1,依次乘以数组中各位,注意进位和数组长度的变化。源程序如下:
#include <stdio.h>
#define M 1000
main()
{
int a[M], i, n, j, flag = 1;
printf("n=");
scanf("%d",&n);
printf("n!=");
a[0] = 1;
for(i = 1; i < M; i++) a[i] = 0;
for(j = 2; j <= n; j++)
{
for(i = 0; i < flag; i++) a[i] *= j;
for(i = 0; i < flag; i++)
if(a[i] >= 10)
{
a[i+1] += a[i]/10;
a[i] = a[i] % 10;
if(i == flag-1) flag++;
}
}
for(j = flag - 1; j >= 0; j--)
printf("%d", a[j]);
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 20480
long* a[N];
int main()
{
int i, j, t, n;
int c;
memset(a, 0, sizeof(a));
a[0] = (long*)malloc(sizeof(long));
*a[0] = 1;
scanf("%d", &n);
t = 0;
for(i = 2; i <= n; ++i) {
c = 0;
for(j = 0; a[j] != 0; ++j) {
c += *a[j] * i;
*a[j] = c % 10000;
c /= 10000;
if(a[j+1] == 0 && c != 0) {
a[t=j+1] = (long*)malloc(sizeof(long));
*a[t] = c;
c = 0;
break;
}
}
}
printf("%d!=\n%d", n, *a[t]);
free(a[t--]);
for(i = t; i >= 0; --i) {
printf("%04d", *a[i]);
free(a[i]);
}
return 0;
}
问题5. 以字符串方式由键盘输入两个高精度的8进制正整数,串长小于255,以第一个数为被除数,第二个数为除数,进行高精度除法运算,并显示商和余数。
算法:
问题6. 麦森数
【问题描述】形如2P-1的素数称为麦森数,这时P一定也是个素数。但反过来不一定,即如果P是个素数,2P-1不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。
任务:从文件中输入P(1000<P<3100000),计算2P-1的位数和最后500位数字(用十进制高精度数表示)
【输入格式】
文件中只包含一个整数P(1000<P<3100000)
【输出格式】
第一行:十进制高精度数2P-1的位数。
第2-11行:十进制高精度数2P-1的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)
不必验证2P-1与P是否为素数。
【输入样例】
1279
【输出样例】
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
算法:2的幂可以转化成左移运算,为了提高运算速度,可每次左移10位,即每次乘210。对于个位单独考虑,每次左移一位。源程序如下:
#include <stdio.h>
#include <math.h>
#define MAX 100000
main()
{
int p;
int i, j;
scanf("%d", &p);
printf("%d\n", (int)(p * log10(2.0)) + 1);
long store[110] = {0};
store[0] = 1;
int left = p % 10;
p /= 10;
for(i = 1; i <= p; i++)
{
for(j = 0; j <= 100; j++)
store[j] <<= 10;
for(j = 0; j <= 100; j++)
{
if(store[j] >= MAX)
{
store[j + 1] += store[j] / MAX;
store[j] %= MAX;
}
}
}
for(i = 1; i <= left; i++)
{
for(j = 0; j <= 100; j++)
store[j] <<= 1;
for(j = 0; j <= 100; j++)
{
if(store[j] >= MAX)
{
store[j + 1] += store[j] / MAX;
store[j] %= MAX;
}
}
}
store[0] -= 1;
for(i = 1; i < 100; i++)
{
if(store[i - 1] < 0)
{
store[i] -= 1;
store[i - 1] += MAX;
}
else
break;
}
for(i = 99; i >= 0; i--)
{
printf("%05d", store[i]);
if((100 - i) % 10 == 0)
printf("\n");
}
}
问题7. 精确计算:1n+2n+3n+…+mN的后K位数,其中1<=n<=9999,1<=m<=9999,1<=K<=99。N,m,K从键盘输入。
例:输入:n=3 m=3 K=3 输出:36
问题8. 有一个正整数N(N可能达到120位),它是由若干个不大于65535的正整数相乘而得到的。请把这个数分解成素数因子(质因子)的乘积。
输入:输入文件只有一行为N的值。
输出:(1)素数因子由小到大分行输出;
(2)每一行输出一个素数因子和该素数因子的个数,用一个空格分开;
(3)如果正整数N的分解中有一个以上的大于65535的素数,请按照(1)、(2)的要求输出分解中的小于65535的素数后,在下一行输出“DATA ERROR!”。
算法:先将2到65535之间的所有素数保存在数组中,用这个数去除数组中的每一个数,得到一个质因数就打印出来。源程序如下:
#include <stdio.h>
#include <math.h>
int length, temp[120];
int sushu(int a[])
{
int i, j, k = 0, m;
for(i = 2; i <= 65537; i++)
{
m = sqrt(i);
for(j = 2; j <= m; j++)
if(i % j == 0) break;
if(j > m)
{
a[k] = i;
k++;
}
}
return k;
}
int divide(int a[], int k)
{
int i, d = 0;
for(i = length - 1; i >= 0; i--)
{
d = d * 10 + a[i];
temp[i] = d / k;
d = d % k;
}
if(!d)
{
while(temp[length - 1] == 0 && length > 1) length--;
for(i = 0; i < length; i++)
{
a[i] = temp[i];
temp[i] = 0;
}
for(i = length; i < 120; i++) a[i] = 0;
}
else
for(i = 0; i < length; i++) temp[i] = 0;
return d;
}
main()
{
int i, k, s, d;
int a[6600], b[120] = {0}, c[120] = {0};
char b1[120];
gets(b1);
length = strlen(b1);
for(i = 0; i < length; i++) b[i] = b1[length - i - 1] - '0';
k = sushu(a);
for(i = 0; i < k; i++)
{
s = 0;
d = divide(b, a[i]);
while(!d)
{
s++;
d = divide(b, a[i]);
}
if(i == k - 1)
{
printf("Data Error!");
break;
}
if(s) printf("%d %d\n", a[i], s);
}
}
分享到:
相关推荐
Java高精度计算Java高精度计算Java高精度计算Java高精度计算Java高精度计算Java高精度计算Java高精度计算Java高精度计算Java高精度计算Java高精度计算Java高精度计算Java高精度计算
ACM高精度计算.ACM高精度计算.ACM高精度计算.ACM高精度计算.ACM高精度计算.
Java高精度计算文件,很好用!!!非原创,特此向代码原作者致敬
高精度计算,包括高精度加减乘(如何存储大整数?如何实现?如何进位?)
最详细全面的黄金分割高精度计算算法资料,值得一看!(C/C++)
你是否因为JS端的小数计算的精度不足而发愁过呢 其实有个不错的资源可以利用。 引用附件的JS,就可以轻松搞定JS的计算问题了。 使用例 <!-- function //+ alert(new BigDecimal("10").add(new BigDecimal("3E+...
第四讲 高精度计算 由于计算机具有运算速度快,计算精度高的特点,许多过去由人来完成的烦琐、复杂的数学计算,现在都可以由计算机来代替,人可以从计算中解放出来,做更具有创造性的工作。 计算机计算结果的精度...
相当好用的VC++ 高精度计算库,算法来源于著名的gmp。
C++实现高精度计算类库,包含了FFT的乘法除法,开平方,用法类似java的bigint,实测速度比java的快很多
面向单纯形的高精度计算算法设计.pdf
用于Visual studio 高精度计算库项目文件; 包括了gmp, mpir, mpfr, gmp, 等,可以直接在visual studio中编译成为静态或动态链接库,用于作超高精度数值计算时调用; 跟Eigen C++ tempalte library库和Pavel写的mpfr C++...
高精度计算问题(大数加法、乘法、麦森数) 分析加代码
第1章 高精度计算-2019-02-19
基础算法 第1章 高精度计算_codes(2020.06.04).rar
高精度计算 高精度加法 高精度减法 高精度乘法 高精度除法
ACM模拟与高精度计算,具有大量的例题以及对应的详尽的题解与参考标准程序,适合acm入门者,以及应对ccf考试以及算法面试等等,很好理解
ACM高精度计算,非常详细适合入门 ACM高精度计算,非常详细适合入门
ACM高精度计算.pptACM高精度计算.pptACM高精度计算.ppt