Блог пользователя Squire

Автор Squire, 13 лет назад, По-русски
Всем доброго здоровья.
Наверное, каждый из нас когда-то (а может, и на вчерашнем соревновании) при решении задач имел проблемы с погрешностями. Думаю, что для каждого из нас это очень неприятно, когда при правильном алгоритме (если можно так выразится) Ваше решение не засчитывается из-за такого рода "ошибок". Моя идея - давайте в этом форуме будем выкладывать разные задачи, реализация решений которых и заключается в нахождении такого рода погрешностей. Ну и, конечно же, будем обсуждать, чем же вызваны эти погрешности.
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
ну все тригонометрические, корни, степени невозможно посчитать точно в общем случаи... ну отсюда и погрешности... 
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну, например, как ты лично вчера "боролся" с погрешностью в задаче А?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да я с ней не боролся... я с кривыми руками боролся...

      Ну из того что я делал было понятно, что ошибка может быть порядка квадрата координат(там только asin был,привык я к этому в задачах на геометрию), ну и числа не очень большие... подумал что поставить между 1e-7..1e-9 и поставил 1e-9...
»
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Есть неплохой обзор типов с плавающей точкой от misof (правда на английском). Там многие вопросы объясняются, также есть примеры задач с топкодера:

Part 1
Part 2
»
13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Мне всегда говорили, что стоит ставить EPS = 1e-9. Такой EPS достаточно часто ставят авторы задач.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Соверши туже ошибку, что и автор!
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится
      Сути наезда не понял.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Ну надо уметь понимать почему именно такой eps надо ставить, а не потому что "так все делают".
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится -15 Проголосовать: не нравится
          Моя логика простая:
          Если ты поставишь EPS, отличный от авторского:
          - если автор поставил правильный EPS, ты в проигрыше
          - если автор поставил неправильный EPS, контест будет нерейтинговый, ты ничего не приобретаешь и не теряешь.

          Если ты поставил авторский EPS:
          - если автор поставил правильный EPS, ты в выигрыше
          - если автор поставил неправильный EPS, контест будет нерейтинговый, ты ничего не приобретаешь и не теряешь. 
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            У автора может быть немного другая идея, которая будет требовать несколько иного epsa.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +44 Проголосовать: не нравится
            Убедительно. Отныне буду на контестах ставить eps исключительно такой же как у авторов.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится -8 Проголосовать: не нравится
            (про пресловутые тарелки, вроде уже кто-то спрашивал, или у меня дежа вю):

            Можно записать:

            pi / n - angle > 0 + eps

            или

            pi  - angle * n > 0 + eps

            очевидно, eps должен различаться в этих выражениях на порядок-два при n до 100... Нехорошо лепить везде 1e-9 просто так, от балды, не вдумываясь в характерные значения... "Авторская" идея тут вроде не при чём... %)
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вот эта задача у меня никак не хочет сдаваться ни с double на C++, ни с extended на Pascal, какой бы eps ни брал. Решал итерациями и Гауссом.
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Она итерациями решается... правда, там ещё надо как-то nan обходить...

    и нормировать кажется

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Где там nan может возникнуть? Вроде же делений на ноль там быть не может.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В свое время на дорешке опенкапа решил с BigDecimal с 50 знаками. Решал итерациями.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А там ограничение тоже было полсекунды? BigDecimal отваливается по таймлимиту. Вообще, какое вы использовали условие остановки итерирования?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        просто итерировал какое-то количетсво раз. 2 ^ 40 вроде.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну допустим не 2^40 все-таки :) Ограничивать число итераций я почему-то не подумал, спасибо.
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Написал первое, что взбрело в голову на С++, зашло на тимусе.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Хм. Вы итерации делали по-другому - через возведение матрицы в степень. Я в лоб пытался - после гаусса, чтобы повысить точность ответа :)
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Так а как еще делать итерации? У нас же неоднородность нулевая.
        X = AX,
        X_1 = AX, X_2 = A*X_1=A*A_X;
        X_N = (A^N)X;
        начальное приближение такое - в клетке d6 1, в остальных нули. потому в конце можно и не умножать на вектор, потому что получим всего лишь строку матрицы. как-то так.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

          Тупо в лоб: зная вероятности на текущем шаге, можно посчитать вероятность на следующем. То, что при этом происходит простое перемножение матриц, а следовательно можно нужно сперва перемножить сами матрицы, я как-то упустил из виду :) Поэтому я и удивился насчет 2^40.

          UPD: А почему именно в этой клетке, а не в любой другой?

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            А, согласен, у нас экспоненциально теряется зависимость от начальных данных, поэтому любую строку матрицы можно выводить, если достаточно больше число итераций произошло.
»
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
В некоторых задачах с целочисленными входными данными можно избежать плавающей точки, если немного подумать и избежать соответствующих вычислений. Например, при вычислении расстояния между двумя точками, если их координаты целочисленные, можно не вычислять корень из суммы квадратов, если, конечно, этого достаточно. Другой пример: изменение масштаба иногда позволяет также отказаться от плавающей точки, просто домножив на степень десяти.
»
13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Аналогичная тема возникла после моего прошлого 60-го раунда. Вот она.