乘法

【题目】求ｍ×ｎ的值。（ｍ与ｎ的位数均不超过２５５位）

【算法分析】由于ｍ与ｎ的位数太大，所以必须用高精度运算。

            与高精度阶乘不同之处在于,如何处理部分积相加的问题.

            两数相乘的高精度运算，其实即是用计算机来模拟手工进行两数相乘。

            试看 n=811,m=98 的情况:

              811          用m的每一位(从低位到高位)去乘n的每一位,

            × 98

            ------

             6488

            7299    <------------注意这里如何处理相加.同理,m的百位,千位.....

           -------               乘n后的结果如何相加,也要处理好.

            79478

【参考答案】

123456789*123456789=15241578750190521

1111111*111=123333321

9999999*99=989999901

987654321*987654321=975461057789971041

99999999999999999999*99999999999999999999=9999999999999999999800000000000000000001

【参考程序】

const max=10000;

var i,j,jinwei,weishu:integer;

    n,m:string;n_length,m_length:integer;

    result:array[1..max] of integer;

begin

     writeln('input n:');readln(n);  {m,n均用字符串输入}

     writeln('input m:');readln(m);

     fillchar(result,sizeof(result),0);

     n_length:=length(n);               {n_length:被乘数n的位数}

     m_length:=length(m);               {m_length:乘数m的位数}

     for i:=1 to m_length  do begin     {用m的每个数字去乘n}

          jinwei:=0;                    {预置进位为0}

          for j:=1 to n_length do begin    {因n也是大数,故要一位一位地去乘}

              result[j+i-1]:=(ord(n[n_length+1-j])-48)

                             *(ord(m[m_length+1-i])-48)+jinwei+result[j+i-1];

            {相乘的结果放数组result,其下标j+i-1同时反应了应该加在哪个位上}

            {注意要把字符串的数字转换成数值才能相乘}

              jinwei:=result[j+i-1] div 10;            {处理进位}

              result[j+i-1]:=result[j+i-1] mod 10;

          end;

          weishu:=n_length+i-1;          {乘完一轮后,已有的位数}

          while jinwei<>0 do begin       {处理乘完一轮后,产生的进位}

                  weishu:=weishu+1;

                  result[weishu]:=(jinwei+result[weishu]);

                  jinwei:=(result[weishu]) div 10;

                  result[weishu]:=(result[weishu]) mod 10;

          end;

         if weishu>max then begin writeln('error!');halt;end;{超过预定位数,出错}

     end;

     write(n,'*',m,'=');   {输出}

     for i:=weishu downto 1 do write(result[i]);readln;