华师一附中OI组

标题: 20150206讲义高精度 [打印本页]

作者: diggersun 时间: 2015-2-6 16:25
标题: 20150206讲义高精度
1、读得字符串
2、对齐。把短串的前面添上0
3、从最右边开始，逐步往前加注意进位
ic=a[i]-'0'+b[i]-'0'+k  K 是进位
if (ic>=10) {ic=ic-10;k=1;}
else {k=0}
c[i]=ic+'0'
4、最后一位若有进位直接在前面添1

乘法 100！  3^N
大数字乘以小数字

用a【0】表示个位
一起乘一起进位
进位标准程序
for(i=0;i<=l-1!!!!;i++)
   {  x=a[i];
      a[i]=x%10;
      a[i+1]=a[i+1]+x/10;
   }
while a[l]>9{!!!!!}

高精度  大数字乘以大数字
好简单
  for (i=0;i<=la;i++)
for (j=0;j<=lb;j++)
   c[i+j]=c[i+j]+a[i]*b[j]
  然后一起处理进位

除法两种单精度  高精度
ys=0;
for (i=0;i<=la;i++)
{
   x=ys*10+a[i]
   s[i]=x/CS  CS 是除数
   ys=x%cs
}
  最后一位处理四舍五入  *****
高精度就很麻烦了
  可以用字符串表示
先存下来 cs的0 1 2 3 4 5 6 7 8 9倍
从第一位开始逐个去比较，假设小于N+1倍

而大于N倍则减去N倍，余数乘以10加上当前

位继续。

考试题集锦
1、1！+2！+3！+****100！
2、N进制多位数加法  给定100个以内100位

以内的2-16进制的数字，求和。
3、1^n+2^n+***m^n的最后K位  其中MNK

都小于999
4、麦森数2^N-1的位数和最后500位
5、n!末尾有多少个连续的0 ，最后一个非零的

数字是几。
变形和技巧
1、数字很大我们需要记录数字的有效位数
2、考虑多位进制  每个数字表示10000或

者10^8（看情况加减问题不大乘除要注意范

围）
3、利用以前的结果

欢迎光临华师一附中OI组 (http://hsyit.cn/)