20150206讲义 高精度

diggersun

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、利用以前的结果