среда, 18 августа 2010 г.

Сравнение длинных чисел

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

Чтобы сравнить длинные числа необходимо и достаточно определить три операции: “больше”, “меньше” и “проверка на равенство”. Отметим важный факт: для реализации задуманного можно реализовать только только одну операцию (или “больше” или “меньше”). Остальные можно выразить из нее.

Но если же требуется реализовать какую-то отдельную операцию в отдельности, то нет необходимости реализовывать все 3 операции.

Ниже представлены все три операции по отдельности:
  1. bool operator == (const BigInt &a, const BigInt &b)
  2. {
  3.   if (a.amount!=b.amount)
  4.     return false;
  5.   for (int i=0;i<a.amount;i++)
  6.   {
  7.     if (a.digits[i]!=b.digits[i])
  8.       return false;
  9.   }
  10.   return true;
  11. }
  12. bool operator > (const BigInt &a, const BigInt &b)
  13. {
  14.   if (a.amount!=b.amount)
  15.     return a.amount>b.amount;
  16.   for (int i=a.amount-1;i>=0;i--)
  17.   {
  18.     if (a.digits[i]!=b.digits[i])
  19.       return a.digits[i]>b.digits[i];
  20.   }
  21.   return false;
  22. }
  23. bool operator < (const BigInt &a, const BigInt &b)
  24. {
  25.   if (a.amount!=b.amount)
  26.     return a.amount<b.amount;
  27.   for (int i=a.amount-1;i>=0;i--)
  28.   {
  29.     if (a.digits[i]!=b.digits[i])
  30.       return a.digits[i]<b.digits[i];
  31.   }
  32.   return false;
  33. }
* This source code was highlighted with Source Code Highlighter.

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

  1. Вроде бы ошибка в алгоритме определения большего/меньшего. Тут вы идете с конца числа до первого не совпадающего, и возвращаете результат. Соответственно, если будут отличаться старшие разряды, то это не учтется. Надо идти сначала.

    14554
    24553

    Например, эти числа будут посчитаны неправильно, этот алгоритм будет считать что 14554>24553 ибо 4>3

    ОтветитьУдалить
  2. Число хранится задом наперед. Об этом написано здесь: http://cppalgo.blogspot.com/2010/05/blog-post_28.html

    Во всем остальном ваша логика верна.

    ОтветитьУдалить
  3. а как выразить остальные операции через одну? например я выразил меньше, тогда остальные определяются как больше(!< && !=) и равно(!< && !>), но это же рекурсия

    ОтветитьУдалить
    Ответы
    1. 1. Пусть реализована операция <. Т.е. вы можете отвечать на вопрос a < b.
      2. Чтобы реализовать операцию >, т.е. ответить на вопрос a > b можно воспользоваться операцией меньше и ответить на вопрос b < a
      3. Чтобы реализовать операцию == нужно проверить условие (!< && !>)
      4. Чтобы реализовать операцию например >= нужно проверить условие !<.
      "но это же рекурсия" - а кто говорил, что будет легко? =)

      Удалить
    2. "а кто говорил, что будет легко?" - да в общем-то меня это не пугает, а вот прога работать отказывается))

      Спасибо большое, мысль, что можно b<a делать пролетела мимо =)

      Удалить