標題: 大數(shù)相乘算法 [打印本頁]
作者: 51hei社區(qū)    時間: 2016-1-16 06:51
標題: 大數(shù)相乘算法
      師姐前幾天有個在線筆試，怕時間上來不及就找我給她幫下忙。做了幾道題目，覺得應(yīng)該是面試當中常常用到的，大數(shù)相乘就是其中一個題目，覺得應(yīng)該是以后面試中經(jīng)常會用到的，所以記了下來。
      我這里采取的方法是將大數(shù)保存在字符串中，然后將兩個字符串逐位相乘，再進位和移位。應(yīng)該還有效率更高的代碼。
源代碼:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  5. #define N 100

  7. /*
  8. *將在數(shù)組中保存的字符串轉(zhuǎn)成數(shù)字存到int數(shù)組中
  9. */
  10. void getdigits(int *a,char *s)
  11. {
  12.      int i;
  13.      char digit;
  14.      int len = strlen(s);

  16.      //對數(shù)組初始化
  17.      for(i = 0; i < N; ++i)
  18.            *(a + i) = 0;
  19.      for(i = 0; i < len; ++i){
  20.            digit = *(s + i);
  21.            *(a + len - 1 - i) = digit - '0';//字符串s="12345",因此第一個字符應(yīng)該存在int數(shù)組的最后一個位置
  22.      }
  23. }

  25. /*
  26. *將數(shù)組a與數(shù)組b逐位相乘以后存入數(shù)組c
  27. */
  28. void multiply(int *a,int *b,int *c)
  29. {
  30.      int i,j;

  32.      //數(shù)組初始化
  33.      for(i = 0; i < 2 * N; ++i)
  34.            *(c + i) = 0;
  35.          /*
  36.           *數(shù)組a中的每位逐位與數(shù)組b相乘，并把結(jié)果存入數(shù)組c
  37.           *比如，12345*12345，a中的5與12345逐位相乘
  38.           *對于數(shù)組c：*(c+i+j)在i=0,j=0,1,2,3,4時存的是5與各位相乘的結(jié)果
  39.           *而在i=1,j=0,1,2,3,4時不光會存4與各位相乘的結(jié)果，還會累加上上次相乘的結(jié)果.這一點是需要注意的!!!
  40.          */
  41.      for(i = 0; i < N; ++i)
  42.            for(j = 0; j < N; ++j)
  43.                  *(c + i + j) += *(a + i) * *(b + j);
  44.          /*
  45.           *這里是移位、進位
  46.          */
  47.      for(i = 0; i < 2 * N - 1; ++i)
  48.      {
  49.            *(c + i + 1) += *(c + i)/10;//將十位上的數(shù)向前進位，并加上原來這個位上的數(shù)
  50.            *(c + i) = *(c + i)%10;//將剩余的數(shù)存原來的位置上
  51.      }
  52. }

  54. int main()
  55. {
  56.     int a[N],b[N],c[2*N];
  57.     char s1[N],s2[N];
  58.     int j = 2*N-1;
  59.     int i;
  60.    
  61.     printf("input the first number:");
  62.     scanf("%s",s1);
  63.     printf("/ninput the second number:");
  64.     scanf("%s",s2);
  65.    
  66.     getdigits(a,s1);
  67.     getdigits(b,s2);
  68.    
  69.     multiply(a,b,c);
  70.    
  71.     while(c[j] == 0)
  72.                j--;
  73.     for(i = j;i >= 0; --i)
  74.            printf("%d",c[i]);
  75.     printf("/n");
  76.     return 0;
  77. }
復(fù)制代碼







歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1