師姐前幾天有個在線筆試，怕時間上來不及就找我給她幫下忙。做了幾道題目，覺得應該是面試當中常常用到的，大數相乘就是其中一個題目，覺得應該是以后面試中經常會用到的，所以記了下來。
我這里采取的方法是將大數保存在字符串中，然后將兩個字符串逐位相乘，再進位和移位。應該還有效率更高的代碼。
源代碼:- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define N 100
- /*
- *將在數組中保存的字符串轉成數字存到int數組中
- */
- void getdigits(int *a,char *s)
- {
- int i;
- char digit;
- int len = strlen(s);
- //對數組初始化
- for(i = 0; i < N; ++i)
- *(a + i) = 0;
- for(i = 0; i < len; ++i){
- digit = *(s + i);
- *(a + len - 1 - i) = digit - '0';//字符串s="12345",因此第一個字符應該存在int數組的最后一個位置
- }
- }
- /*
- *將數組a與數組b逐位相乘以后存入數組c
- */
- void multiply(int *a,int *b,int *c)
- {
- int i,j;
- //數組初始化
- for(i = 0; i < 2 * N; ++i)
- *(c + i) = 0;
- /*
- *數組a中的每位逐位與數組b相乘，并把結果存入數組c
- *比如，12345*12345，a中的5與12345逐位相乘
- *對于數組c：*(c+i+j)在i=0,j=0,1,2,3,4時存的是5與各位相乘的結果
- *而在i=1,j=0,1,2,3,4時不光會存4與各位相乘的結果，還會累加上上次相乘的結果.這一點是需要注意的!!!
- */
- for(i = 0; i < N; ++i)
- for(j = 0; j < N; ++j)
- *(c + i + j) += *(a + i) * *(b + j);
- /*
- *這里是移位、進位
- */
- for(i = 0; i < 2 * N - 1; ++i)
- {
- *(c + i + 1) += *(c + i)/10;//將十位上的數向前進位，并加上原來這個位上的數
- *(c + i) = *(c + i)%10;//將剩余的數存原來的位置上
- }
- }
- int main()
- {
- int a[N],b[N],c[2*N];
- char s1[N],s2[N];
- int j = 2*N-1;
- int i;
-
- printf("input the first number:");
- scanf("%s",s1);
- printf("/ninput the second number:");
- scanf("%s",s2);
-
- getdigits(a,s1);
- getdigits(b,s2);
-
- multiply(a,b,c);
-
- while(c[j] == 0)
- j--;
- for(i = j;i >= 0; --i)
- printf("%d",c[i]);
- printf("/n");
- return 0;
- }
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
