#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define MAX 100 int main()
{
char s1[MAX],s2[MAX];
int len1,len2,i,j,result[MAX]={};
scanf("%s %s",s1,s2);
len1=strlen(s1);
len2=strlen(s2);
for(i=;i<len1;i++)
{
for(j=;j<len2;j++)
{
result[i+j]+=(s1[i]-'')*(s2[j]-'');
}
}
for(i=len1+len2-;i>=;i--)//因为最后一项result[len1-1+len2-1]
{
if(result[i]>)
{
result[i-]+=(result[i]/);
result[i] %= ;
}
}
//当i=1,result[0]是进了位的,他有可能大于9,甚至result[1]给他进几十,所以直接输出
for(i=;i<=len1+len2-;i++)
{
printf("%d",result[i]);
}
return ;
}
算法思路:输入如:3456
789
用3分别乘7、8、9,用4分别乘7、8、9,5分别乘7、8、9,
0 | 1 | 2 | 3 |
3 | 4 | 5 | 6 |
7 | 8 | 9 |
6分别乘7、8、9
若按照res[i+j]=s1[i]*s2[j],得到res:
0 | 1 | 2 | 3 | 4 | 5 |
21 | 24 | 27 | |||
28 | 32 | 36 | |||
35 | 40 | 45 | |||
42 | 48 | 54 |
res数组本身是1维的,只有一排,外部的for循环每进完一次,res数组就被更新一次
发现规律:len1=4,len2=3,最后一位是res[len1-1+len2-1]
将得到的res数组从最后一位开始进位,巧妙的是,逻辑上if(res[]>9)更好,不加,也没问题
result[i-]+=(result[i]/);
result[i] %= ;
让前一位进好位,又保留这一位的余数,我只让这段代码做到了res[1],但在res[0]处进了位
联系大数加法:poj1503
同样的定义一个res(fin)数组