`
isiqi
  • 浏览: 15950615 次
  • 性别: Icon_minigender_1
  • 来自: 济南
社区版块
存档分类
最新评论

高精度计算

 
阅读更多

一、数据输入
先将要计算的数据输入到内存中一般是按位存到数组中,按位对齐。

定义:第一位表示个位,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

算法:将正整数保存在数组中,高位在前、低位在后,首先去掉末位的‘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);

}

}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics