分析:
在计算机上进行高精度计算,首先要处理好以下几个基本问题:
1、数据的接收与存储;
2、计算结果位数的确定;
3、进位处理和借位处理;
4、商和余数的求法;

输入和存储
运算因子超出了整型、实型能表示的范围,肯定不能直接用一个数的形式来表示。能表示多个数的数据类型有两种:数组和字符串。
(1)数组:每个数组元素存储1位(在优化时,这里是一个重点!),有多少位就需要多少个数组元素;优点:每一位都是数的形式,可以直接加减;运算时非常方便缺点:数组不能直接输入;输入时每两位数之间必须有分隔符,不符合数值的输入习惯;
(2)字符串:字符串的最大长度是255,可以表示255位。优点:能直接输入输出,输入时,每两位数之间不必分隔符,符合数值的输入习惯;缺点:字符串中的每一位是一个字符,不能直接进行运算,必须先将它转化为数值再进行运算;运算时非常不方便(注意‘0’的问题)。
优化:
一个数组元素存放四位数
注意:是加减法时可以用interger,但是当是乘法的时候,就要用int64,否则会出现越界的情况。
还有就是:输出时对非最高位的补零处理。

另一个问题:
存储顺序
正序??
逆序??

还有就是一定不要忘了初始化!!
计算结果位数的确定
两数之和的位数最大为较大的数的位数加1。
乘积的位数最大为两个因子的位数之和。
阶乘:lgn!=lgn+lg(n-1)+lg(n-2)……………….+lg3+lg2+lg1
=lnn/ln10+ln(n-1)/ln10+ln(n-2)/ln10+…………….+ln3/ln10+ ln2/ln10+ln1/ln10
=trunc(1/ln10*(lnn+ln(n-1)+ln(n-2)+………..+ln3+ln2+ln1)
乘方:lg(a?^b)=trunc(lg(a^b))+1
=trunc(b*lga)+1
=trunc(b*lna/ln10)+1

高精度的加法
ncarry=0;
for (i=0;i<=len;i++)
{
k=a[i]+b[i]+ncarry;
a[i+1]+=k/N;
ncarry=k%N;
}
当最后ncarry>0时,len会变化!!
高精度的减法

先比较大小,大的为a,用一个变量记录符号。
ncarry=0;
for (i=0;i<=len;i++)
{
if (a[i]-b[i]-ncarry>=0)
a[i]=a[i]-b[i]-ncarry,ncarry=0;
else
a[i]=a[i]+N-b[i]-ncarry,ncarry=1;
}
高精度的乘法
For (i=0;i<=lena;i++)
for (j=0;j<=lenb;j++)
c[i+j]+=a[i]*b[j];
For (i=0;i<=lena+lenb;i++)
{
c[i+j+1]+=c[i+j]/N;
c[i+j]=c[i+j]/N;
}
高精度的除法
A÷B精确值有两种情况:①、A能被B整除,没有余数。②、A不能被B整除,对余数进行处理。首先,我们知道,在做除法运算时,有一个不变的量和三个变化的量,不变的量是除数,三个变化的量分别是:被除数、商和余数。
可以用减法代替除法运算:不断比较A[1..n]与B[1..n]的大小,如果A[1..n]>=B[1..n]则商C[1..n]+1→C[1..n],然后就是一个减法过程:A[1..n]-B[1..n]→A[1..n]。
由于简单的减法速度太慢,故必须进行优化。
设置一个位置值J,当A[1..n]>B[1..n]时,B[1..n]左移→B[0..n],j:=j+1,即令B[1..n]增大10倍。这样就减少了减法的次数。当j>0且A[1..n]<B[1..n]时,B[0..n]右移
求n!

 

一个例子:计算5*6*7*8
方法一:顺序连乘
5*6=30,1*1=1次乘法
30*7=210,2*1=2次乘法
210*8=1680,3*1=3次乘法
方法二:非顺序连乘
5*6=30,1*1=1次乘法
7*8=56,1*1= 1次乘法
30*56=1680,2*2=4次乘法

若“n位数*m位数=n+m位数”,则n个单精度数。
无论以何种顺序相乘,乘法次数一定为n(n-1)/2次。(n为积的位数)
证明:
设F(n)表示乘法次数,则F(1)=0,满足题设
设k<n时,F(k)=k(k-1)/2,现在计算F(n)
设最后一次乘法计算为“k位数*(n-k)位数”,则
F(n)=F(k)+F(n-k)+k (n-k)=n(n-1)/2(与k的选择无关)

考虑k+t个单精度数相乘
a1*a2*…*ak *ak+1*…*ak+t
设a1*a2*…*ak结果为m位高进制数(假设已经算出)
ak+1*…*ak+t结果为1位高进制数
若顺序相乘,需要t次“m位数*1位数” ,共mt次乘法
可以先计算ak+1*…*ak+t,再一起乘,只需要m+t次乘法
在设置了缓存的前提下,计算m个单精度数的积,如果结果为n位数,则乘法次数约为n(n–1)/2次,与m关系不大
设S=a1*a2*…*am,S是n位高进制数
可以把乘法的过程近似看做,先将这m个数分为n组,每组的积仍然是一个单精度数,最后计算后面这n个数的积。时间主要集中在求最后n个数的积上,这时基本上满足“n位数*m位数=n+m位数”,故乘法次数可近似的看做n(n-1)/2次
10!=28*34*52*7
n!分解质因数的复杂度远小于nlogn,可以忽略不计
与普通算法相比,分解质因数后,虽然因子个数m变多了,但结果的位数n没有变,只要使用了缓存,乘法次数还是约为n(n-1)/2次
因此,分解质因数不会变慢(这也可以通过实践来说明)
分解质因数之后,出现了大量求乘幂的运算,我们可以优化求乘幂的算法。这样,分解质因数的好处就体现出来
二分法求乘幂

a2n+1=a2n*a
a2n=(an)2
其中,a是单精度数
二分法求乘幂之优化平方算法
怎样优化
(a+b)2=a2+2ab+b2
例:123452=1232*10000+452+2*123*45*100
把一个n位数分为一个t位数和一个n-t位数,再求平方
怎样分
设求n位数的平方需要F(n)次乘法
F(n)=F(t)+F(n-t)+t(n-t),F(1)=1
用数学归纳法,可证明F(n)恒等于n(n+1)/2
所以,无论怎样分,效率都是一样
将n位数分为一个1位数和n–1位数,这样处理比较方便
优化:

计算S=ax+kbx=(ab)xak
当k<xlogab时,采用(ab)xak比较好,否则采用ax+kbx更快
可以先计算两种算法的乘法次数,再解不等式,就可以得到结论
也可以换一个角度来分析。其实,两种算法主要差别在最后一步求积上。由于两种方法,积的位数都是一样的,所以两个因数的差越大,乘法次数就越小
∴当axbx–ak>ax+k–bx时,选用(ab)xak,反之,则采用ax+kbx。
∴axbx–ak>ax+k–bx
∴(bx–ak)(ax+1)>0
∴bx>ak
这时k<xlogab

这道题:
1.处理小数点问题,以及反序。
2.进行n次乘法。
3.进行输出,并加上小数点。

#include<stdio.h>
#include<string.h>
#define MAX 200

char str[MAX+1];
int num[MAX+1];
int num0[MAX+1];
int result[MAX+1];
int fraction_len;//小数部分的长度

void multify();
int length(int*);//返回整数的位数
bool find_radix();//判断是否有小数点
int main()
{
	int n,i,j,len;
	while(scanf("%s %d",str,&n))
	{
		fraction_len = 0;
		memset(num,0,sizeof(num));
		memset(num0,0,sizeof(num0));
		int temp_len = strlen(str);
		len = strlen(str);
		for(i = temp_len-1 ; i >= 0; i--)
			if(str[i] != '0' && find_radix())//去掉小数点后面的末尾的零
			{
				len = i + 1;
				break;
			}
			for(i = len - 1,j = 0;i >= 0; i--)
			{
				if(str[i] != '.')
				{
					num[j] = str[i] - '0';
					num0[j] = str[i] - '0';
					j++;
				}
				else
					fraction_len = len-1 - i;
			}
		  for(i = 1;i <= n-1; i++)
  multify();
  if(n * fraction_len >= length(num0))//处理小数部分的位数比结果位数多的情况
  {
					printf(".");
				for(i = n*fraction_len - length(num0); i >= 1; i--)
					printf("0");
			}
			for(i = length(num0)-1; i >= 0; i--)
			{
				printf("%d",num0[i]);
				if(i == n*fraction_len && i != 0)
					printf(".");
			}
			printf("\n");
			memset(str,'0',sizeof(str));
			memset(num,0,sizeof(num));
			memset(num0,0,sizeof(num0));
	}
	return 0;
}
int length(int* temp)
{
	int i;
	for(i = MAX; i >= 0; i--)
	{
		if(temp[i] != 0)
		{
			return i+1;
		}
	}
	return 0;
}
void multify()//num0和num的乘积放在result,然后把result赋值给num0,并且把result清空
{
	int i;
	int len1 = length(num0);
	int len2 = length(num);
	for(i = 0; i < len1; i++)
	{
		for(int j = 0; j < len2; j++)
		{
			result[i+j] += num0[i]* num[j];
		}
	}
	for(i = 0; i < length(result); i++) { if(result[i] >= 10)
	{
		result[i+1] += result[i]/10;
		result[i] %= 10;
	}
	}
	for(i = length(result)-1; i >= 0; i--)
		num0[i] = result[i];
	memset(result,0,sizeof(result));
}
bool find_radix()
{
	int i ;
	for(i =0;i<strlen(str);i++)
	{
		if(str[i] == '.')
			return true;
	}
	return false;
}

发表评论

电子邮件地址不会被公开。

Post Navigation