|
|
師姐前幾天有個(gè)在線筆試，怕時(shí)間上來(lái)不及就找我給她幫下忙。做了幾道題目，覺得應(yīng)該是面試當(dāng)中常常用到的，大數(shù)相乘就是其中一個(gè)題目，覺得應(yīng)該是以后面試中經(jīng)常會(huì)用到的，所以記了下來(lái)。
我這里采取的方法是將大數(shù)保存在字符串中，然后將兩個(gè)字符串逐位相乘，再進(jìn)位和移位。應(yīng)該還有效率更高的代碼。
源代碼:- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define N 100
- /*
- *將在數(shù)組中保存的字符串轉(zhuǎn)成數(shù)字存到int數(shù)組中
- */
- void getdigits(int *a,char *s)
- {
- int i;
- char digit;
- int len = strlen(s);
- //對(duì)數(shù)組初始化
- 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",因此第一個(gè)字符應(yīng)該存在int數(shù)組的最后一個(gè)位置
- }
- }
- /*
- *將數(shù)組a與數(shù)組b逐位相乘以后存入數(shù)組c
- */
- void multiply(int *a,int *b,int *c)
- {
- int i,j;
- //數(shù)組初始化
- for(i = 0; i < 2 * N; ++i)
- *(c + i) = 0;
- /*
- *數(shù)組a中的每位逐位與數(shù)組b相乘，并把結(jié)果存入數(shù)組c
- *比如，12345*12345，a中的5與12345逐位相乘
- *對(duì)于數(shù)組c：*(c+i+j)在i=0,j=0,1,2,3,4時(shí)存的是5與各位相乘的結(jié)果
- *而在i=1,j=0,1,2,3,4時(shí)不光會(huì)存4與各位相乘的結(jié)果，還會(huì)累加上上次相乘的結(jié)果.這一點(diǎn)是需要注意的!!!
- */
- for(i = 0; i < N; ++i)
- for(j = 0; j < N; ++j)
- *(c + i + j) += *(a + i) * *(b + j);
- /*
- *這里是移位、進(jìn)位
- */
- for(i = 0; i < 2 * N - 1; ++i)
- {
- *(c + i + 1) += *(c + i)/10;//將十位上的數(shù)向前進(jìn)位，并加上原來(lái)這個(gè)位上的數(shù)
- *(c + i) = *(c + i)%10;//將剩余的數(shù)存原來(lái)的位置上
- }
- }
- 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;
- }
|
|
