poj2389---大数乘法

#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)数组

上一篇:js每隔一段时间执行函数


下一篇:js setInterval每隔一段时间执行一次