Работа с дълги числа – Уроци по програмиране

Дълги числа

Дълги цели числа се наричат такива, които не се “вместват” в целочислена променлива от стандартен тип. Когато искаме да работим с такива числа, трябва сами да програмираме съответните операции.

Ако се наложи обработка на число, което надвишава диапазона на допустимите в езика С++ числови стойности е подходящо да се използват стрингове. Числото се запомня като низ от символи и впоследствие се обработва символ по символ. За да бъде преобразуван символ в цифра може да се ползва един от следните варианти:

masiv[i]= niz[i]-48;
или
masiv[i]=niz[i]-‘0’;

След така направената трансформация масивът ще съдържа цифрите на числото.

Събиране на дълги числа

Нека x и y са два масива, съдържащи две дълги числа. Нека елементите с нулеви номера от тези масиви да съдържат младшите цифри. Номерът на най-старшите цифри на двете дълги числа се пази съответно в променливите nx и ny. Броят на цифрите е с единица по-голям от стойностите в тези променливи, защото броенето на елементите на масивите започва от нула. Приемаме, че стойностите на nx и ny са равни. Ако това не е така, трябва елементите на по-късия масив, които са с номера, по-големи от минимума на nx и ny, да бъдат запълнени с нули.
В масива z се пресмята сумата на двете дълги числа, като броят на цифрите на тази сума се записва в nz. Променливата с служи за запомняне на преноса към по-горен разред.

c=0;
for(i=0; i<=nx; i++)
{
  z[i]=x[i]+y[i]+c;
  if(z[i]>9)
  {
    z[i]=z[i]-10;
    c=1;
  }
  else c=0;
}
if(c)
{
  nz=nx+1;
  z[nz]=1;
}
else nz=nx;

Задача

Сбор (Пролетен турнир, Пловдив, 2002, зад. D1).

Напишете програма, която въвежда от клавиатурата един ред ( с дължина най-много 80 знака), на който са написани две естествени числа, разделени със знак плюс, намира сбора на двете числа и извежда резултата на екрана.

Пример:
Вход                                                                     Изход
2+2                                                                        4
12345678+87654321                                        99999999
99999999999999999999+1                             100000000000000000000

Решение: Програмата реализира метода за преобразуване на дълго число от низ в масив и след това прилага идеята за събиране на две дълги числа.

char s[200];
int a[100], b[100], r[100];
void main()
{
  int c, i, j, n;
  cin>>s;
  n=strlen(s);
  i=n-1;  
  j=0;
  while(s[i]!= '+')
  {
    a[j]=s[i]-'0';
    i--;
    j++;
  }
  i--;  
  j=0;
  while(i>=0)
  {
    b[j]=s[i]-'0';
     i--;
     j++;
  }
  c=0;
  for(i=0; i<99; i++)
  {
    r[i]=a[i]+b[i]+c;
    if(r[i]>9)
    {
      r[i]=r[i]-10;
      c=1;
    }
    else c=0;
  }
  i=99;
  while(r[i]==0) i- -;
  for(j=i; j>=0; j- -)
  cout <<r[j];
  cout<<"\n";
}