пятница, 20 августа 2010 г.

Длинное – длинное (беззнаковое вычитание)

[Вся длинная арифметика]

Рассмотрим случай беззнакового вычитания, когда вычитаемое не превосходит уменьшаемого(A-B, A>=B):
  1. BigInt operator - (const BigInt &a, const BigInt &b)
  2. {
  3.   BigInt res = a;
  4.   int r = 0;
  5.   for (int i = 0;i<res.amount;i++)
  6.   {
  7.     res.digits[i] -= b.digits[i] + r;
  8.     if (res.digits[i]<0)
  9.     {
  10.       res.digits[i]+=osn;
  11.       res.digits[i+1]--;
  12.     }   
  13.   }
  14.   int pos = res.amount;
  15.   while (pos && !res.digits[pos])
  16.     pos--;
  17.   res.amount = pos+1;
  18.   return res;
  19. }
* This source code was highlighted with Source Code Highlighter.

В реализации данной операции необходимо корректно учесть случай, когда a=b.

P.S: В первой версии выводились лишние ведущие нули. Эту ошибку обнаружил Privalov, за что выражаю ему благодарность.

4 комментария:

  1. ну хочется написать вместо if while потому что очевидно на варианте 1111111111111111-1111111111111110 программа даст не правильную длину... возможно решение не самое оптимальное, но по крайней мере рабочее

    ОтветитьУдалить
  2. Спасибо! Это был ценный комментарий!
    Заодно выявили слабости тестов проверяющей системы. По этому поводу создал ветку в форуме:
    http://informatics.mccme.ru/moodle/mod/forum/discuss.php?d=828

    По поводу оптимальности решения я полностью согласен. Практически во всех операциях присутствуют лишние копирования массивов, некоторые операции можно оформить в виде функций и записывать ответ в первый операнд. НО! Все эти оптимизации люди осуществляют с пониманием дела, когда за плечами имеется определенный опыт работ с длинными числами. Моей же задачей было помочь с пониманием на начальном этапе, когда этого опыта практически нет.

    ОтветитьУдалить
  3. я, кажется, обнаружил тут одну лишнею переменную... по-моему r тут лишняя, вам так не кажется?

    ОтветитьУдалить
  4. Анатоле одобряет =). Действительно r не нужна. Скорее всего, когда писал, на фоне думал про длинное + длинное.

    ОтветитьУдалить