суббота, 21 августа 2010 г.

Длинное DIV короткое & Длинное MOD короткое

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

При упоминании операции деления на длинных числах молодые олимпиадники резко меняются в лице, меняя веселые гримасы на хмурые лица. Скорее всего причиной тому являются разговоры более опытных товарищей, когда последние в красках обсуждают деление длинного на длинное. Об этой операции мы поговорим чуть позже. А пока спешу успокоить, т.к. деление длинного на короткое не сложнее, чем умножение длинного на короткое):

  1. BigInt operator / (const BigInt &a, const int &n)
  2. {
  3.   BigInt res;
  4.   res.amount = a.amount;
  5.   int ost = 0;
  6.   for (int i=res.amount-1;i>=0;i--)
  7.   {
  8.     int cur = ost * osn + a.digits[i];
  9.     res.digits[i] = cur / n;
  10.     ost = cur % n;
  11.   }
  12.   if (!res.digits[res.amount-1] && res.amount != 1)
  13.     res.amount--;
  14.   return res;
  15. }
  16. int operator % (const BigInt &a, const int &n)
  17. {
  18.   BigInt res;
  19.   res.amount = a.amount;
  20.   int ost = 0;
  21.   for (int i=res.amount-1;i>=0;i--)
  22.   {
  23.     int cur = ost * osn + a.digits[i];
  24.     res.digits[i] = cur / n;
  25.     ost = cur % n;
  26.   }
  27.   return ost;
  28. }
* This source code was highlighted with Source Code Highlighter.

Как вы уже успели заменить я привел реализации сразу двух операций: взятие целого от деления (DIV или /) и взятие остатка от деления (MOD или %). Дело в том, что если присмотреться, то можно заменить, что тела функций практически идентичны. Они отличаются только возвращаемым аргументом. Поэтому, если того требует задача, эти функции можно объединить в одну.

8 комментариев:

  1. В реализации оператора "%" переменная res вообще не нужна.

    ОтветитьУдалить
  2. Это да). res остался после копипаста операции /.

    ОтветитьУдалить
  3. Ошибка. Делим 2047/23, получается 089. Длина числа 89 ставится в 3. Для исправления в строке 12 заменить if на while

    ОтветитьУдалить
  4. Ошибки здесь нет. Коротким число считается, если оно меньше osn. Соответственно, 23 считается коротким для osn >= 100. if на while заменять не нужно, так как при делении на число n < osn размер числа уменьшится на 1, либо останется тем же. Деление 2047 на 23 с основанием osn=10 - это длинное DIV длинное.

    ОтветитьУдалить
  5. А в какой статье у вас osn становиться 100? Ведь Ввод длинных чисел вы расматриваете для osn=10, а сейчас уже делите для osn=100, непорядок, товарищи...

    ОтветитьУдалить
    Ответы
    1. osn может быть и 10 и 100 и 1000 и 10000. Ввод длинного числа: http://cppalgo.blogspot.ru/2010/08/blog-post.html Там рассматривается ввод числа с osn=10 и osn=10000.

      Удалить
    2. Этот комментарий был удален автором.

      Удалить
    3. Спасибо) Просто немного запутался после комментария Данила Сагунова.. Делаю по вашему примеру, используя vector...

      Удалить