Multiplicando duas longo longos ints C
-
13-09-2019 - |
Pergunta
Eu estou trabalhando em um programa em C como parte de Homework em que eu tenho que pegar o produto de dois números longos que são tomadas como cadeia de caracteres. por exemplo: 123456789021 e 132456789098. Uma vez que é tomada como uma corda, eu converti-los para long int longo para a multiplicação. Mas o produto resultante será muito grande (maior do que long long int eu acho). Alguém pode por favor me sugerir um método para executar esta multiplicação?
Solução
Aqui está uma abordagem: Pense em como você iria multiplicar esses números à mão, em papel. Implementar este método em C. Você terá que descobrir:
- como quebrar um inteiro (representada como uma string) em dígitos
- como converter cada volta dígitos para um número inteiro
0 <= d < 10
- como gerenciar conjuntos de dígitos (ou seja. Quão grande você deve fazer as matrizes?)
- como escrever o loop (s) que você pode precisar implementar multiplicação
- como gerenciar transportar produtos a partir de um dígito para o próximo
- como converter esses dígitos de volta para caracteres para saída
Outras dicas
geralmente grandes inteiros representados como matrizes de bytes. Você pode olhar para a implementação do Microsoft BigInteger no DLR. Eu acho que eles algoritmos usados ??desenvolvidos por Knuth
Marque esta BigInteger biblioteca e um código de exemplo muito básico de World of Seven.
Se você está interessado em algumas de minhas casas códigos cozidos em C (somente multiplicação):
////////////////////////////////////////////////////////////////////////////////
Code removed after I checked the home-work tag ;)
///////////////////////////////////////////////////////////////////////////////////////
Isso funciona em alguns dos concursos de programação anteriores eu havia participado;) Mas se você está procurando ainda mais rápida multiplicação algoritmo que você pode implementar Karatsuba algoritmo , eu pessoalmente usar este agora em concurso tempo real.
Ei, cara, verificar isso, eu só completou yester dia como uma parte da minha lição de casa:
#include<stdio.h>
#include<string.h>
int main()
{
char one[195];
char two[195];
char temp[195];
int a[195],c[195],b[195];
int x,i,j,k,l,p,add;
for(;;)/*determining the larger number...*/
{
printf("Input A:");
gets(one);
printf("Input B:");
gets(two);
k=strlen(one);
l=strlen(two);
if(l>k)
{
strcpy(temp,one);
strcpy(one,two);
strcpy(two,temp);
break;
}
else
{
break;
}
}
k=strlen(one);
l=strlen(two);
for(p=0;p<195;p++)/*assigning all initial values to 0*/
{
a[p]=0;
b[p]=0;
c[p]=0;
}
for(i=0;one[i];i++)/*converting char to integer(note:1,as a character assigned as 49.)*/
{
a[i]=((one[--k])-48);
}
for(i=0;i<two[i];i++)
{
b[i]=((two[--l])-48);
}
for(i=0;i<=strlen(two);i++)/*main algorithm*/
{
add=0;
p=0;
for(j=i;j<=(2*strlen(one)-1);j++)
{
x=c[j]+b[i]*a[p]+add;
c[j]=x%10;
add=x/10;
p++;
}
}
printf("\nMultiplication:");
for(p=(2*strlen(one)-1);p>=0;p--)
{
if(p>strlen(one)&&c[p]==0)
{
continue;
}
printf("%d",c[p]);
}
printf("\n");
}
Você pode usar uma biblioteca para grande arithmetik inteiro, a Wikipedia tem uma lista aqui .
Outra abordagem seria para multiplicar os números como float / double e Stip fora do decimal ao exibir os resultados.