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:

//algorytm.edu.pl
#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;
int 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;

	return 0;
}

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;
}