Programowanie i algorytmy

Dodawanie wielkich liczb

Zad. 2. Napisz program, który doda do siebie dwie duże liczby naturalne.

Wejście

Dwie liczby naturalne składające się z maksymalnie 1000 cyfr.

Wyjście

Wynik sumy liczb podanych na wejściu.

 

 

Rozwiązanie

Łatwo zauważyć, że nie istnieje żaden wbudowany typ całkowity w C++, który przechowa tak duże liczby. W tym celu należy posłużyć się tablicą znaków (lub liczb całkowitych).

Wczytamy dwie liczby do tych tablic, następnie wykonamy dodawanie sposobem pisemnym:

 

#include<iostream>
#include<cstring>
 
using namespace std;
 
inline int max(int a,int b)
{
 
if(a>b)
   return a;
return b;
}
 
inline int min(int a,int b)
{
 
if(a<b)
   return a;
return b;
}
 
int main()
{
 
char l1[1001],l2[1001];
int wynik[1002],i,mx,mn;
 
int w;
short przeniesienie,dl1,dl2;
 
przeniesienie=0;
 
cout<<"Podaj pierwszą liczbę: ";
cin>>l1;
cout<<"Podaj durgą liczbę: ";
cin>>l2;
 
dl1=strlen(l1);
dl2=strlen(l2);
 
mx=max(dl1,dl2);
mn=min(dl1,dl2);
 
for(i=mx-1;i>=0;i--)
{
 
   if(dl1>=dl2)
   {
 
      if(mn)
      {
 
         mn--;
         w=(int)l1[i]+(int)l2[mn]-96+przeniesienie;
         wynik[i]=w%10;
         przeniesienie=w/10;
 
      }
      else
      {
         w=(int)l1[i]-48+przeniesienie;
         wynik[i]=w%10;
         przeniesienie=w/10;
 
      }
 
   }
   else
   {
      if(mn)
      {
            mn--;
            w=(int)l2[i]+(int)l1[mn]-96+przeniesienie;
            wynik[i]=w%10;
            przeniesienie=w/10;
      }
      else
      {
 
            w=(int)l2[i]-48+przeniesienie;
            wynik[i]=w%10;
            przeniesienie=w/10;
      }
 
   }
 
}
 
cout<<"Suma podanych liczb wynosi: ";
 
if(przeniesienie)
   cout<<1;
 
for(i=0;i<mx;i++)
   cout<<wynik[i];
 
cout<<endl;
 
system("PAUSE");
 
return 0;
}