catforce's blog

By catforce, history, 4 years ago, In Russian

Попробовал решить задачку на тернарный поиск (С. Поляна дров) https://codeforces.com/gym/100119/

В этой задаче предлагается вычислить ответ с точностью до 8-го знака. Я пробовал решить на Java 8 и на Python 3. Эталонный ответ на первый претест:

0.783310604

Если выполнять упрощённый алгоритм, то в первом же тесте не хватает точности в ответе (8-й знак отличается от эталонного на 1):

        double l = 0;
        double r = 1;
        double e = 1e-10;
        while (r-l > e) {
            double m1 = l + (r-l)/3;
            double m2 = r - (r-l)/3;
            double t1 = t(m1);
            double t2 = t(m2);
            if (t1 > t2) {
                l = m1;
            } else {
                r = m2;
            }
        }
        out.println((l+r)/2); // 0.7833105913161102

Если же использовать алгоритм с проверкой на равенство, то результат больше похож на ожидаемый

        double l = 0;
        double r = 1;
        double e = 1e-10;
        while (r-l > e) {
            double m1 = l + (r-l)/3;
            double m2 = r - (r-l)/3;
            double t1 = t(m1);
            double t2 = t(m2);
            if (t1 == t2) {
                l = m1;
                r = m2;
            } else if (t1 > t2) {
                l = m1;
            } else {
                r = m2;
            }
        }
        out.println((l+r)/2); // 0.783310600341931

Так как в Java 8 нет встроенного алгоритма вычисления квадратного корня для BigDecimal, не стал его использовать.

Такая же ситуация и с Python (при использовании float). Если же использовать Python с типом данных Decimal, то решение на обоих алгоритмах одинаковое и ближе к эталонному:

0.783310604150410451061410535

Кто-нибудь может объяснить что я делаю не так?

  • Vote: I like it
  • +13
  • Vote: I do not like it