如何将高精度算法应用于长尾词处理中？

本文共计2367个文字，预计阅读时间需要10分钟。

首先，看看每种数据类型可表示的数据范围。当我们要表示的数据很长时，无法用数据类型表示，可以使用数组存储。单精度：+/- 3.4E38；双精度：+/- 1.7E308。不能使用内置类型存储。

先来看一下每个数据类型可表示的数据范围

当我们要表示的数很长时，无法用数据类型表示，可以用数组存储

单精度：能用一个内置类型存储的整数

高精度：不能用内置类型存储的大整数，通常用数组存储每一个数位

建议使用小端存储（个位放在最前面）（原因：大端存储虽然看似更直观，但是当处理进位时就会遇到问题：必须要将所有元素移位，为新位腾出空间！方便模拟竖式运算！）

高精度加法

按照竖式计算方法，①从低位到高位，②对于较长数的每一位i，和的第i位为两加数第i位与当前进位三者之和，③若和大于10，则下一进位为1，当前位和减10，④结束后，若进位非0，则结果增加一位，值为进位（此处必为1）

// 从低到高位计算 for (int i = 0; i < len; i++) { // 和的第i位为两加数第i位与当前进位三者之和 c[i] += a[i] + b[i]; // 若和大于10，则下一进位为1 c[i + 1] = c[i] / 10; // 当前位和减10 c[i] %= 10; } // 结束后，若进位非0，则结果增加一位，值为进位（此处必为1） if (c[len + 1])len++;

完整程序：

#include<iostream> #include<cstdio> #include<cstring> #define maxn 520 using namespace std; int a[maxn], b[maxn], c[maxn] int main() { string A,B; cin>>A>>B; //输入加数与被加数 int len=max(A.length(),B.length());//和的位数与最大值的位数有关 for (int i=A.length()-1,j=1; i>=0;i--,j++) a[j]=A[i]-'0'; //加数放入a数组 　 for (int i=B.length()-1,j=1; i>=0;i--,j++) b[j]=B[i]-'0'; for (int i=1; i<=len;i++){ c[i]+=a[i]+b[i]; c[i+1]=c[i]/10; c[i]%=10; } if(c[len+1])len++; for(int i=len;i>=1;i--)cout<<c[i]; return 0;

使用数组0~(n-1)和使用数组1~n在进行高精度运算时，分别有什么好处?

高精度乘法

算法分析

类似加法，可以用竖式求乘法。

分析c数组下标的变化规律，可以写出如下关系式：ci = c’i +c”i +…由此可见，c i跟a[i]*b[j]乘积有关，跟上次的进位有关，还跟原c i的值有关,可以把所有贡献算出来，最后一口气处理进位问题，有

c[i+j-1]= a[i]*b[j]+ x + c[i+j-1]; x=c[i+j-1]/10 ; c[i+j-1]%=10;

完整程序如下：

#include<iostream> #include<cstring> #define maxn 5010 using namespace std; int a[maxn],b[maxn],c[maxn]; int main() { int i,j,x,lena,lenb,lenc; string A,B; cin>>A>>B; lena=A.length();lenb=B.length(); for (i=lena-1;i>=0;i--) a[lena-i]=A[i]-48; for (i=lenb-1;i>=0;i--) b[lenb-i]=B[i]-48; for (i=1;i<=lena;i++) for (j=1;j<=lenb;j++) c[i+j-1]+=a[i]*b[j]; lenc=lena+lenb; for(i=1;i<=lenc;i++){ c[i+1]+=c[i]/10; c[i]%=10; } for(;!c[lenc];)lenc--; for (i=max(lenc,1);i>=1;i--) cout<<c[i]; return 0; }

补充：高精度减法

算法分析

类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。

减法进位

if (a[i]<b[i]) { --a[i+1]; a[i]+=10; } c[i]=a[i]-b[i];

完整程序如下：

#include<iostream> #include<cstdio> #include<cstring> #define maxn 520 using namespace std; int a[maxn], b[maxn], c[maxn]; int main() { int i,j,lena,lenb,lenc; char A[maxn],B[maxn],C[maxn]; gets(A); gets(B); if (strlen(A)<strlen(B)||strlen(A)==strlen(B)&&strcmp(A,B)<0)//strcmp()为字符串比较函数，当n1==n2, 返回0，A>B时，返回正整数；A<B时，返回负整数 {//处理被减数和减数，交换被减数和减数 strcpy(C,A); strcpy(A,B); strcpy(B,C); cout<<"-"; } lena=strlen(A),lenb=strlen(B); for(i=lena-1,j=1;i>=0;i--,j++) a[j]=A[i]-'0'; //加数放入a数组 for(i=lenb-1,j=1;i>=0;i--,j++){ b[j]=B[i]-'0'; } i=1; while (i<=lena||i<=lenb) { if (a[i]<b[i]) { a[i]+=10;//不够减，那么向高位借1当10 a[i+1]--; } c[i]=a[i]-b[i];//对应位相减 i++; } lenc=i; while ((c[lenc]==0)&&(lenc>1)) lenc--;//最高位的0不输出　　 for (i=lenc;i>=1;i--) cout<<c[i];//输出结果 return 0; }

高精度除法

1. 高精度数除以单精度数

算法分析

做除法时，每一次上商的值都在０～９，每次求得的余数连接以后的若干位得到新的被除数，继续做除法。

因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。

当然，为了程序简洁，可以避免高精度除法，用0～9次循环减法取代得到商的值。这里，我们讨论一下高精度数除以单精度数的结果，采取的方法是按位相除法。

完整程序如下：

#include<iostream> #include<cstring> #include<cstdio> using namespace std; int main() { char a1[100],c1[100]; int a[100],c[100],lena,i,x=0,lenc,b; memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); gets(a1); cin>>b; lena=strlen(a1); for (i=0;i<=lena-1;i++) 　　 a[i+1]=a1[i]-48; for (i=1;i<=lena;i++) //按位相除 { c[i]=(x*10+a[i])/b; x=(x*10+a[i])%b; } 　 lenc=1; while (c[lenc]==0&&lenc<lena) 　 lenc++; //删除前导0 for (i=lenc;i<=lena;i++) cout<<c[i]; cout<<endl; return 0; }

实质上，在做两个高精度数运算时候，存储高精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位数（例如一个整型或长整型数据等），这样，在做运算（特别是乘法运算）时，可以减少很多操作次数。

例如图5就是采用4位保存的除法运算，其他运算也类似。具体程序可以修改上述例题予以解决，程序请读者完成。

2.高精除以高精

算法分析

高精除以低精是对被除数的每一位（这里的“一位”包含前面的余数，以下都是如此）都除以除数，而高精除以高精则是用减法模拟除法，对被除数的每一位都减去除数，一直减到当前位置的数字（包含前面的余数）小于除数（由于每一位的数字小于10，所以对于每一位最多进行10次计算）

完整程序如下：

#include<iostream> #include<cstring> using namespace std; int a[101],b[101],c[101],d,i; void init(int a[]) { string s; cin>>s; //读入字符串s a[0]=s.length(); //用a[0]计算字符串 s的位数 for(i=1;i<=a[0];i++) a[i]=s[a[0]-i]-'0'; //将数串s转换为数组a，并倒序存储． } void print(int a[]) //打印输出 { if (a[0]==0){cout<<0<<endl;return;} for(int i=a[0];i>0;i--) cout<<a[i]; cout<<endl; return ; } int compare (int a[],int b[]) //比较a和b的大小关系，若a>b则为1，a<b则为-1,a=b则为0 { 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; //各位都相等则两数相等。 } void numcpy(int p[],int q[],int det) //复制p数组到q数组从det开始的地方 { for (int i=1;i<=p[0];i++) q[i+det-1]=p[i]; q[0]=p[0]+det-1; } void jian(int a[],int b[]) //计算a=a-b { int flag,i; flag=compare(a,b); //调用比较函数判断大小 if (flag==0) {a[0]=0;return;} //相等 if(flag==1) //大于 { for(i=1;i<=a[0];i++) { if(a[i]<b[i]){ a[i+1]--;a[i]+=10;} //若不够减则向上借一位 a[i]-=b[i]; } while(a[0]>0&&a[a[0]]==0) a[0]--; //修正a的位数 return; } } void chugao(int a[],int b[],int c[]) { int tmp[101]; c[0]=a[0]-b[0]+1; for (int i=c[0];i>0;i--) { memset(tmp,0,sizeof(tmp)); //数组清零 numcpy(b,tmp,i); while(compare(a,tmp)>=0){c[i]++;jian(a,tmp);} //用减法来模拟 } while(c[0]>0&&c[c[0]]==0)c[0]--; return ; } int main() { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); init(a);init(b); chugao(a,b,c); print(c); print(a); return 0; }