Что такое ошибка представления

Общий принцип

В систему посылаются только файлы с исходным кодом, а сама посылаемая программа должна состоять только из одного файла: *.dpr, *.cpp, *.java, *.pas и т. д. Нельзя отправить в систему скомпилированный exe-файл, файл проекта Visual Studio и т. п.

В решениях запрещается:

• осуществлять доступ к сети;
• выполнять любые операции ввода/вывода, кроме открывания, закрывания, чтения и записи стандартных потоков stdin, stdout, stderr и файлов с именами, явно прописанными в условии задачи;
• сознательно «ломать» тестирующую систему;
• выполнять другие программы и порождать новые процессы;
• изменять права доступа к файловой системе;
• работать с поддиректориями;
• создавать и манипулировать ресурсами GUI (окна, диалоговые сообщения и т. д.);
• работать со внешними устройствами (звук, принтер и т. д.);
• выполнять прочие действия, призванные нарушить ход учебного процесса.

Решения выполняются в специальном окружении, обеспечивающем безопасный запуск, и попытка выполнить какие-либо из указанных действий закончится, скорее всего, получением вердикта «Ошибка во время выполнения».

Ввод и вывод данных

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

Можно считать, что изначально при запуске решения выходной файл будет отсутствовать, и решение должно его создать и записать туда ответ.

Внимательно проверяйте имена файлов в решениях на соответствие условию задачи.

Если в коде решения имена файлов указаны неверно, это может приводить к непредсказуемым последствиям. Так, если имя выходного файла указано неверно и требуемый по условию файл не создаётся, система, скорее всего, выдаст вердикт «Ошибка представления».
В случае, когда в решении на Java перепутано имя входного файла и делается попытка открыть несуществующий файл, выбрасывается исключение. Если автор решения не перехватывает его, программа завершается с вердиктом «Ошибка во время выполнения». Если же исключение обрабатывается, то вполне возможны и другие вердикты в зависимости от того, отработает ли программа и что окажется в выходном файле. Если в решении на C++ неправильно указан входной файл и ошибки специально не обрабатываются, чтение из файла может приводить к чтению произвольных данных («мусора»). Если в программе вместо чтения из файла делается попытка считать данные со стандартного ввода (stdin, который обычно связан с клавиатурой консоли), программа заблокируется («повиснет») в ожидании ввода и будет завершена с вердиктом «Превышен предел времени».

Решение может выводить произвольные данные «в консоль», то есть в стандартные потоки stdout, stderr, которые обычно связаны с консольным окном (например для отладки). Это не запрещается и не влияет на результат. Проверяется только содержимое выходного файла. Следует помнить, что на вывод тратится дополнительное время, поэтому большой объём отладочной информации может критически замедлить вашу программу. Вывод в stderr медленнее, чем в stdout, поскольку не буферизируется.

Тестирование решений

Каждое отправленное решение проходит на сервере проверку на нескольких тестах. Задача считается решённой только в случае прохождения всех тестов. Решение запускается на всех тестах, которые есть по задаче, и процесс тестирования не прерывается на первом непройденном тесте, как это делается в соревнованиях типа ACM.

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

Тесты по каждой задаче не упорядочены по сложности, по размеру входных данных, по какому-то иному критерию, а следуют в исторически сложившемся порядке их добавления в систему.

Не гарантируется, что первый тест в системе будет совпадать с тестом из условия (зачастую это не так).

Результатом проверки является итоговое сообщение системы и, возможно, в скобках номер первого теста, вызвавшего ошибку (если таковая имела место). Например, вердикт «Неправильный ответ (43)» означает, что решение успешно скомпилировалось и прошло без ошибок первые 42 теста по задаче, но на тесте под номером 43 выдало неверный ответ.

Далее опишем все допустимые сообщения тестирующей системы и укажем возможные причины их появления.

CE — Ошибка компиляции (Compilation Error)

Не удалось скомпилировать решение и получить исполняемый файл для запуска. Решение в таком случае, очевидно, не может быть проверено ни на одном тесте.

Посмотреть вывод компилятора и понять, почему код не удаётся скомпилировать, можно путём нажатия на иконку в таблице с вашими решениями. Наиболее частые причины ошибки компиляции: выбран неверный компилятор (для другого языка программирования или же несовместимая версия, например Java v7 вместо Java v8), отправляется не тот файл (файл проекта IDE вместо файла с исходным кодом).

Время работы компилятора ограничено 30 секундами. Если он не успел отработать по каким-либо причинам, также будет выставлен вердикт «Ошибка компиляции».

TLE — Нарушен предел времени (Time Limit Exceeded)

Для каждого теста установлено своё ограничение по времени (Time Limit) в секундах. Для разных тестов по одной задаче ограничение по времени может быть разным.

Тестирующая система учитывает так называемое процессорное время (CPU Time) выполнения процесса в операционной системе. Нет смысла делать решение задачи многопоточным, потому что распараллеливание хоть и позволяет сократить реальное время работы (Wall Time), но не уменьшает процессорное время.

Процесс-решение запускается на тесте, и если процесс не успевает завершиться в течение отведённого времени, он принудительно завершается и выставляется вердикт «Нарушен предел времени». В качестве времени работы решения на тесте указывается то время, которое процесс фактически проработал до того, как был приостановлен. Нет возможности узнать, сколько бы программа проработала, если бы не была снята по времени. Если при ограничении по времени на тест в 1 секунду вы видите, что решение получает вердикт «Нарушен предел времени» и работает 1015 мс, то нельзя это понимать как «решение чуть-чуть не успевает, надо ускорить его на 15 мс». Если решение останавливается по времени, то вывод программы никак не проверяется на предмет его правильности.

Возможные причины появления ошибки «Нарушен предел времени»:

• неэффективный алгоритм (например, в решении реализован алгоритм с временной сложностью Ω(n²), хотя задача предполагает решение за O(n log n));
• недостаточно эффективная программная реализация (идея и алгоритм правильные, но код написан не очень хорошо: например, ввод данных из файла осуществляется медленно, чрезмерно часто выделяется и освобождается память);
• попытка чтения данных с консоли (std::cin, scanf(), getchar() в C++, System.in в Java), тогда как нужно читать входные данные из файла (в этом случае программа блокируется в ожидании ввода и зависает, не расходуя при этом CPU Time, поэтому такой случай тестирующая система обрабатывает отдельно);
• ошибка в программе (например, программа входит в бесконечный цикл).

Не рекомендуется «пропихивать» медленное решение, отправляя его многократно, пока система не «согласится» его принять. Решение в любой момент может быть перетестировано и, соответственно, может перестать быть принятым из-за нарушения предела времени.

ILE — Нарушен предел ожидания (Idleness Limit Exceeded)

Программа зависла в ожидании, не потребляя при этом ресурсы процессора.

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

MLE — Нарушен предел памяти (Memory Limit Exceeded)

Программа использует слишком много оперативной памяти, стоит проанализировать использование памяти и оптимизировать его.
Также причиной чрезмерного использования памяти может быть ошибка в программе, например, вечный цикл в теле которого на каждой или некоторых итерациях выделяется дополнительная память. К используемой памяти относится не только память с данными, но также память с кодом и программным стеком.

Ограничение по памяти есть не для всех задач. Гарантируется, что для всех тестов в рамках одной задачи ограничение по памяти одинаково.

Как и в случае нарушения ограничения по времени, программа при нарушении ограничения по памяти аварийно завершается тестирующей системой, её вывод не проверяется на правильность. Точно так же не следует воспринимать размер памяти, использованной до момента аварийного завершения, как объём, которого решению хватило бы для успешной работы. Более точно, вердикт MLE, полученный с использованием 257 МБ памяти, говорит о том, что приложение успело использовать 257 МБ памяти и было принудительно остановлено, но ничего не говорит о том, сколько памяти использовало бы приложение, не будучи принудительно остановленным.

В некоторых случаях при разовом выделении чрезмерно большого блока в памяти, этот запрос может быть не выполнен операционной системой, что в результате может привести к ошибке во время выполнения или (значительно реже) другому результату неопределённого поведения в случае с языком C++.

RTE — Ошибка во время выполнения (Run-time Error)

В операционной системе есть такое понятие, как код завершения процесса (Exit Code). Этот подход используется как в Windows, так и в ОС семейства UNIX. Это целое число, которое остаётся после прекращения выполнения программы. Общепринятое соглашение гласит, что нулевой код завершения свидетельствует о нормальном завершении процесса без ошибок, любой другой — об ошибке. Тестирующая система проверяет код завершения вашего решения, и если он не равен нулю, выставляет вердикт «Ошибка во время выполнения». При этом никак не проверяется то, что решение успело вывести в выходной файл.

Укажем типичные причины ошибок во время выполнения.

• Использована директива package в коде программы на Java.

  В результате программа на Java находится не в пакете по умолчанию. Компилятор Java сгенерировал класс в некотором пакете (ошибки компиляции нет), а при запуске виртуальная машина Java не смогла найти этот класс, потому что искала в пакете по умолчанию (возникло исключение ClassNotFoundException с сообщением Could not find or load main class).

• Выход за границы допустимой области памяти в программе на C++.

  Выход за границы массива, разыменование неправильного указателя, обращение к нулевому указателю.

• Переполнение системного стека.

  Эта причина является частой в случае рекурсии. Вообще, системный стек используется для размещения параметров функций, локальных переменных. Его размер, как правило, невелик и по умолчанию равен 1 МБ. При вызове функции стековая структура позволяет естественным образом сохранить текущие состояния всех локальных переменных и вернуться к ним, когда вызов завершится и управление вернётся в исходную точку. Если в алгоритме используется глубокая рекурсия, то размера стека может не хватить для хранения контекстов всех вызовов. Решений этой проблемы два:

  1. переписать алгоритм нерекурсивно (например с использованием своего стека, а не системного);
  2. увеличить размер системного стека, что делается по-разному для разных языков программирования (см. примеры для C++ (Visual Studio) и Java).

• Ошибка ввода-вывода (попытка открыть несуществующий входной файл).

  Нужно проверить правильность имени входного файла.

• Программа целенаправленно была завершена с ненулевым кодом выхода.

  В программе на C++ это может быть, если функция main() в C++ вернула ненулевой код (return (non-zero) в функции main()). Рекомендуется завершать функцию main() оператором return 0 (в старых компиляторах C++ это обязательно, современные компиляторы же подразумевают возврат нулевого кода автоматически). Также программу на C++ с произвольным кодом завершает вызов exit().

  В программе на Java можно завершить процесс с произвольным кодом с помощью System.exit().

• Необработанное исключение.

  Причин возникновения исключений может быть масса. Например, если в Java функции Integer.parseInt() / Double.parseDouble() была передана строка, содержащая пробельные символы (ASCII-коды 9, 10, 13, 32), выбрасывается исключение NumberFormatException.

• Целочисленное деление на ноль.

  При выполнении деления нужно всегда думать, а не может ли делитель оказаться равным нулю. В то же время стоит отметить, что вещественное деление на ноль (в типах с плавающей точкой double, float) по умолчанию не приводит к завершению программы, а даёт специальные значения +Inf, -Inf или NaN.

PE — Ошибка представления (Presentation Error)

Наиболее частая причина возникновения этой ошибки — не найден выходной файл. Возможно, вы забыли создать выходной файл и выводите ответ в консоль (он в таком случае игнорируется). Проверьте имена входного и выходного файла в вашей программе на соответствие условию задачи. Исторически сложилось, что в разных задачах входной и выходной файл именуются по разным правилам: input.txt и output.txt, in.txt и out.txt, input.in и output.out (обратите внимание, что нет расширения txt), [задача].in и [задача].out…

Для некоторых задач программа проверки (checker) дополнительно удостоверяется, что ваш вывод соответствует определённому формату, и выдаёт ошибку представления в случае, если это не так. Например, если в задаче нужно вывести число, а вы выводите строку. Или если в задаче нужно вывести сначала число k, затем k чисел, а ваше решение выводит число k и далее (k + 1) чисел (то есть решение выводит в файл лишние данные).

Также имейте в виду, что отлавливание исключений и других ошибок не должно быть самоцелью. Если исключение не обрабатывается каким-либо образом, обычно нет смысла его ловить по следующей причине. Аварийное завершение работы программы в результате ошибки во время выполнения приводит к вердикту «Ошибка во время выполнения», только если соответствующее исключение было «проброшено» наружу, а не «заглушено» на каком-то этапе. Если исключение отлавливается, но никак не обрабатывается, то в результате возникновения соответствующей ошибки следует ожидать вердикт «Ошибка представления» или же «Неправильный ответ» (реже).

WA — Неправильный ответ (Wrong Answer)

Для многих задач ответ однозначен, и проверяется просто побайтовое совпадение вашего выходного файла и сохранённого правильного ответа. Такая проверка требует строгого соблюдения формата файла, не допускает незначащих пробелов и пустых строк. Например, если правильный ответ имеет вид (пробелы обозначены символом ␣)

5
1␣2␣3␣4␣5

и решение вывело

5
1␣2␣3␣4␣5␣

(лишний пробел в конце второй строки), то будет получен вердикт «Неправильный ответ». Для некоторых задач написаны проверяющие программы (checker), которые к таким различиям лояльны и засчитывают ответы с лишними пробелами как правильные. Всегда точно следуйте формату файла и не выводите лишних пробелов, и проблем не будет.

После последней строки файла можно выводить или не выводить перевод строки — не важно. Есть две точки зрения в зависимости от того, с какой стороны смотреть на символ перевода строки:

1. каждая строка завершается переводом строки, поэтому n в конце файла нужен;
2. перевод строки является разделителем между соседними строками, поэтому n в конце файла не нужен.

Первая точка зрения является общепринятой. Так, компилятор gcc, система контроля версий git и многие другие программы выдают предупреждение no newline at the end of file, если в самом конце файла нет символов новой строки. Обсуждение вопроса можно почитать на stackoverflow.

Поэтому рекомендуется придерживаться первого подхода и завершать все строки переводами строк.

Другие очевидные причины получения неправильного ответа:

• неверный алгоритм;
• ошибка в программе.

Бывает такое, что решение от запуска к запуску даёт разные ответы, или же правильно работает на одном компьютере и неправильно на другом. Такие случаи, как правило, связаны с ошибками в решениях.

OK — Принято (Accepted)

Программа работает правильно и прошла все тесты с соблюдением всех ограничений.

Если решение принято системой, это ещё не означает, что в его основе лежит правильный алгоритм. В любой момент могут появиться новые наборы входных данных, на которых будут заново протестированы все решения по задаче. Если ваше решение на самом деле не полностью верно и прошло только из-за недостаточно сильного набора тестов, оно может в будущем потерять статус «Принято».

CF — Ошибка тестирования (Check Failed)

Если указан номер теста, то программа успешно завершается на предложенном тесте (укладывается в отведённые время и память и не совершает ошибок во время выполнения), но результат не удаётся проверить из-за ошибок в программе проверки. Вашей ошибки в этом случае, возможно, никакой нет и после исправления программы проверки будет получен вердикт OK. Не исключены ещё два варианта: WA, PE.

Имейте в виду, что если ошибка тестирования возникает на первом же тесте, то на остальных Ваше решение не запускается вовсе. Соответственно, в этом случае после устранения ошибок программы проверки вердикты TLE, MLE, RTE также могут возникнуть в любом тесте, кроме первого.

Если же номер теста, на котором возникает ошибка тестирования, не указан, значит, программа проверки не была скомпилирована, а Ваше решение не запускалось вовсе. В этом случае правильным может быть любой вердикт, отличный от CF.

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

SV — Нарушение безопасности (Security Violation)

Ошибка означает, что программа попыталась выполнить запрещённые действия.

К их числу относится попытка создания новых процессов. Вашим решениям запрещено запускать на выполнение другие программы. Например, в коде

порождается новый процесс командной оболочки cmd.exe и в нём выполняется команда pause. Пожалуйста, не пишите так, для достижения аналогичного эффекта можно использовать другие приёмы.

Особенности языков программирования

У каждого конкретного языка программирования есть свои особенности, о которых полезно знать. Далее рассмотрены отдельные особенности написания решений на разных языках программирования:

• C++;
• Java;
• C#;
• Python.

Выбор языка программирования

Разные задачи можно решать на разных языках. Часто для конкретной задачи тот или иной язык оказывается предпочтительным. Например, если в задаче требуются тяжёлые вычисления, то её может быть проще сдать на C++, чем на Java, за счёт более быстрой работы программы на C++ (для кода на Java могут потребоваться более изощрённые оптимизации, чтобы он прошёл по времени). С другой стороны, если задача требует проведения вычислений с большими целыми числами, выходящими за пределы диапазона 64-битных переменных, то есть «длинной арифметики», то решение существенно проще написать на Java, воспользовавшись готовым качественно написанным классом BigInteger для операций с числами произвольной длины.

Конфигурация тестирующего сервера

Сервер, на котором осуществляется запуск решений, является виртуальной машиной, выполняющейся внутри Microsoft Hyper-V Server 2012 R2. Виртуальный компьютер работает под управлением Windows 7 Professional x64, оснащён процессором Intel® Core™ i3-4130 (Haswell, кэш 3 МБ, 3,40 ГГц, доступно только одно ядро) и 4 ГБ оперативной памяти. Для хранения входных и выходных файлов используется RAM-диск, чтобы обеспечить максимальную производительность ввода-вывода.

Языки программирования

На странице учебного курса в системе на вкладке «Компиляторы» можно ознакомиться с актуальным списком доступных языков программирования, версиями компиляторов и параметрами командной строки их вызова.

Размер системного стека явно не задаётся (используется размер по умолчанию). При компиляции кода на C++ включен режим оптимизации O2.

К старту курса по Fullstack-разработке на Python делимся решениями классической проблемы неточности чисел с плавающей точкой. В материале вы найдёте примеры работы с функциями и классами, предназначенными специально для решения проблем чисел с плавающей точкой.

Числа с плавающей точкой — быстрый и эффективный способ хранения чисел и работы с ними. Но он связан с рядом трудностей для начинающих и опытных программистов! Вот классический пример:

>>> 0.1 + 0.2 == 0.3
False

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

Компьютер обманывает вас

Вы видели, что 0.1 + 0.2 не равно 0.3, но безумие на этом не заканчивается. Вот ещё пара примеров, сбивающих с толку:

>>> 0.2 + 0.2 + 0.2 == 0.6
False

>>> 1.3 + 2.0 == 3.3
False

>>> 1.2 + 2.4 + 3.6 == 7.2
False

Проблема касается и сравнения:

>>> 0.1 + 0.2 <= 0.3
False

>>> 10.4 + 20.8 > 31.2
True

>>> 0.8 - 0.1 > 0.7
True

Что происходит? Когда вы вводите в интерпретатор Python число 0.1, оно сохраняется в памяти как число с плавающей точкой и происходит преобразование. 0.1 — это десятичное число с основанием 10, но числа с плавающей точкой хранятся в двоичной записи. То есть основание 0.1 преобразуется из 10 в 2.

Получающееся двоичное число может недостаточно  точно представлять исходное число с основанием 10. 0.1 — один из примеров. Двоичным представлением будет 0.0(0011). То есть 0.1 — это бесконечно повторяющееся десятичное число, записанное с основанием 2. То же происходит, когда в виде десятичного числа с основанием 10 записывается дробь ⅓. Получается бесконечно повторяющееся десятичное число 0.3(3).

Память компьютера конечна, поэтому бесконечно повторяющееся представление двоичной дроби 0.1 округляется до конечной дроби. Её значение зависит от архитектуры компьютера (32- или 64-разрядная).

Увидеть значение с плавающей точкой, которое сохраняется для 0.1, можно с помощью метода .as_integer_ratio(). Представление с плавающей точкой состоит из числителя и знаменателя:

>>> numerator, denominator = (0.1).as_integer_ratio()
>>> f"0.1 ≈ {numerator} / {denominator}"
'0.1 ≈ 3602879701896397 / 36028797018963968'

Чтобы отобразить дробь с точностью до 55 знаков после запятой, используем format():

>>> format(numerator / denominator, ".55f")
'0.1000000000000000055511151231257827021181583404541015625'

Так 0.1 округляется до числа чуть больше, чем его истинное значение.

Узнайте больше о числовых методах, подобных .as_integer_ratio(), в моей статье 3 Things You Might Not Know About Numbers in Python («3 факта о числах в Python, которые вы могли не знать»).

Эта ошибка представления чисел с плавающей точкой встречается куда чаще, чем может показаться.

Ошибка представления числа очень типична

Существуют три причины, почему число округляется при его представлении в виде числа с плавающей точкой:

1. В числе больше значащих разрядов, чем позволяет плавающая точка.

2. Это иррациональное число.

3. Число рациональное, но без конечного двоичного представления. 

64-разрядные числа с плавающей точкой имеют 16 или 17 значащих разрядов. Любое число, у которого значащих разрядов больше, округляется. Иррациональные числа, такие как π и e, нельзя представить конечной дробью с целочисленным основанием. И, опять же, иррациональные числа в любом случае округляются при сохранении в виде чисел с плавающей точкой.

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

А как на счёт бесконечных рациональных чисел, например 0.1 с основанием 2? Именно здесь вам встретится большинство связанных с плавающей точкой трудностей и благодаря математике — позволяющей определять, конечная дробь или нет, — вы будете сталкиваться с ошибками представления чаще, чем думаете.

С основанием 10 дробь можно представить как конечную, если её знаменатель — произведение степеней простых множителей 10. Два простых множителя 10 — это 2 и 5, поэтому дроби ½, ¼, ⅕, ⅛ и ⅒ — конечные, а ⅓, ⅐ и ⅑ — нет. У основания 2 только один простой множитель — 2.

Конечные дроби здесь только те, знаменатель которых равен степени числа 2. В результате дроби ⅓, ⅕, ⅙, ⅐, ⅑ и ⅒ — бесконечные, когда представлены в двоичной записи.

Теперь наш первый пример должен стать понятнее. 0.1, 0.2 и 0.3 при преобразовании в числа с плавающей точкой округляются:

>>> # -----------vvvv  Display with 17 significant digits
>>> format(0.1, ".17g")
'0.10000000000000001'

>>> format(0.2, ".17g")
'0.20000000000000001'

>>> format(0.3, ".17g")
'0.29999999999999999'

При сложении 0.1 и 0.2 получается число чуть больше 0.3:

>>> 0.1 + 0.2
0.30000000000000004

А поскольку 0.1 + 0.2 чуть больше, чем 0.3, и 0.3 представлено числом, которое чуть меньше 0.3, выражение 0.1 + 0.2 == 0.3 оказывается False.

Об ошибке представления чисел с плавающей точкой должен знать каждый программист на любом языке — и уметь с ней справляться. Она характерна не только для Python. Результат вывода 0.1 + 0.2 на разных языках можно увидеть на сайте с подходящим названием 0.30000000000000004.com.

Как сравнивать числа с плавающей точкой в Python

Как же справляться с ошибками представления чисел с плавающей точкой при сравнении таких чисел в Python? Хитрость заключается в том, чтобы избегать проверки на равенство. Вместо ==, >= или <= всегда используйте с числами с плавающей точкой функцию math.isclose():

>>> import math
>>> math.isclose(0.1 + 0.2, 0.3)
True

В math.isclose() проверяется, достаточно ли близок первый аргумент ко второму. То есть проверяется расстояние между двумя аргументами. Оно равно абсолютной величине разницы обоих значений:

>>> a = 0.1 + 0.2
>>> b = 0.3
>>> abs(a - b)
5.551115123125783e-17

Если abs(a — b) меньше некоего процента от большего значения a или b, то a считается достаточно близким к b, чтобы считаться «равным» b. Этот процент называется относительной погрешностью и указывается именованным аргументом rel_tol функции math.isclose(), который по умолчанию равен 1e-9.

То есть если abs(a — b) меньше 0.00000001 * max(abs(a), abs(b)), то a и b считаются «близкими» друг к другу. Это гарантирует, что a и b будут приблизительно с девятью знаками после запятой.

Если нужно, можно изменить относительную погрешность:

>>> math.isclose(0.1 + 0.2, 0.3, rel_tol=1e-20)
False

Конечно, относительная погрешность зависит от ограничений задачи, но для большинства повседневных приложений стандартной относительной погрешности должно быть достаточно. Проблема возникает, если a или b равно нулю, а rel_tol меньше единицы. Тогда, как бы ни было близко ненулевое значение к нулю, относительной погрешностью гарантируется, что проверка на близость будет неудачной. В качестве запасного варианта здесь применяется абсолютная погрешность:

>>> # Relative check fails!
>>> # ---------------vvvv  Relative tolerance
>>> # ----------------------vvvvv  max(0, 1e-10)
>>> abs(0 - 1e-10) < 1e-9 * 1e-10
False

>>> # Absolute check works!
>>> # ---------------vvvv  Absolute tolerance
>>> abs(0 - 1e-10) < 1e-9
True

В math.isclose() эта проверка выполняется автоматически. Абсолютная погрешность определяется с помощью именованного аргумента abs_tol. Но abs_tol по умолчанию равен 0.0, поэтому придётся задать его вручную, если нужно проверить близость значения к нулю.

В итоге в функции math.isclose() возвращается результат следующего сравнения — с относительными и абсолютными проверками в одном выражении:

abs(a - b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol)

math.isclose() появилась в PEP 485 и доступна с Python 3.5.

Когда стоит использовать math.isclose()?

В целом math.isclose() следует применять, сравнивая значения с плавающей точкой. Заменим == на math.isclose():

>>> # Don't do this:
>>> 0.1 + 0.2 == 0.3
False

>>> # Do this instead:
>>> math.isclose(0.1 + 0.2, 0.3)
True

Со сравнениями >= и <= нужно быть осторожным. Обработаем равенство отдельно, используя math.isclose(), а затем проверим строгое сравнение:

>>> a, b, c = 0.1, 0.2, 0.3

>>> # Don't do this:
>>> a + b <= c
False

>>> # Do this instead:
>>> math.isclose(a + b, c) or (a + b < c)
True

Есть альтернативы math.isclose(). Если вы работаете с NumPy, можете использовать numpy.allclose() и numpy.isclose():

>>> import numpy as np

>>> # Use numpy.allclose() to check if two arrays are equal
>>> # to each other within a tolerance.
>>> np.allclose([1e10, 1e-7], [1.00001e10, 1e-8])
False

>>> np.allclose([1e10, 1e-8], [1.00001e10, 1e-9])
True

>>> # Use numpy.isclose() to check if the elements of two arrays
>>> # are equal to each other within a tolerance
>>> np.isclose([1e10, 1e-7], [1.00001e10, 1e-8])
array([ True, False])

>>> np.isclose([1e10, 1e-8], [1.00001e10, 1e-9])
array([ True, True])

Имейте в виду: стандартные относительные и абсолютные погрешности — не то же самое, что math.isclose(). Стандартная относительная погрешность для numpy.allclose() и numpy.isclose() равна 1e-05, а стандартная абсолютная погрешность — 1e-08.

math.isclose() особенно удобна для модульных тестов, хотя и здесь имеются альтернативы. Во встроенном модуле unittest в Python есть метод unittest.TestCase.assertAlmostEqual().

Но в нём применяется только проверка абсолютной разницы. А это ещё и утверждение, то есть при сбоях возникает ошибка AssertionError, из-за которой оно непригодно для сравнений в бизнес-логике.

Отличная альтернатива math.isclose() для модульного тестирования — это функция pytest.approx() из pytest pytest. Как и в math.isclose(), здесь принимаются два аргумента и возвращается, равны они или нет в пределах некой погрешности:

>>> import pytest
>>> 0.1 + 0.2 == pytest.approx(0.3)
True

Как и в math.isclose(), в pytest.approx() для задания относительной и абсолютной погрешностей есть именованные аргументы rel_tol и abs_tol. Но стандартные значения различаются. У rel_tol оно 1e-6, а у abs_tol — 1e-12.

Если первые переданные в pytest.approx() два аргумента подобны массиву (то есть это итерируемый объект Python, такой же, как список или кортеж или даже массив NumPy), тогда в pytest.approx() поведение подобно numpy.allclose() и возвращается то, равны эти два массива или нет в пределах погрешностей:

>>> import numpy as np                                                          
>>> np.array([0.1, 0.2]) + np.array([0.2, 0.4]) == pytest.approx(np.array([0.3, 0.6])) 
True

Для pytest.approx() сгодятся даже значения словаря:

>>> {'a': 0.1 + 0.2, 'b': 0.2 + 0.4} == pytest.approx({'a': 0.3, 'b': 0.6})
True

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

Точные альтернативы числам с плавающей точкой

В Python есть два встроенных числовых типа, которые обеспечивают полную точность в ситуациях, когда числа с плавающей точкой не подходят: Decimal и Fraction.

Тип Decimal

В типе Decimal могут храниться десятичные значения именно с той точностью, какая нужна. По умолчанию в нём сохраняются 28 значащих цифр (это число можно изменить согласно конкретной решаемой задаче):

>>> # Import the Decimal type from the decimal module
>>> from decimal import Decimal

>>> # Values are represented exactly so no rounding error occurs
>>> Decimal("0.1") + Decimal("0.2") == Decimal("0.3")
True

>>> # By default 28 significant figures are preserved
>>> Decimal(1) / Decimal(7)
Decimal('0.1428571428571428571428571429')

>>> # You can change the significant figures if needed
>>> from decimal import getcontext
>>> getcontext().prec = 6  # Use 6 significant figures
>>> Decimal(1) / Decimal(7)
Decimal('0.142857')

Больше узнать о типе Decimal можно в документации Python.

Тип Fraction

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

>>> # import the Fraction type from the fractions module
>>> from fractions import Fraction

>>> # Instantiate a Fraction with a numerator and denominator
>>> Fraction(1, 10)
Fraction(1, 10)

>>> # Values are represented exactly so no rounding error occurs
>>> Fraction(1, 10) + Fraction(2, 10) == Fraction(3, 10)
True

У типов Fraction и Decimal много преимуществ по сравнению со стандартными значениями с плавающей точкой. Но есть и недостатки: меньшая скорость и повышенное потребление памяти.

Если абсолютная точность не нужна, лучше оставаться с числами с плавающей точкой. А вот в случае с финансовыми и критически важными приложениями эти недостатки типов Fraction и Decimal могут оказаться приемлемыми.

Заключение

Значения с плавающей точкой — это и благо, и проклятие одновременно. Они обеспечивают быстрые арифметические операции и эффективное потребление памяти за счёт неточного представления. Из этой статьи вы узнали:

• Почему числа с плавающей точкой неточны.

• Почему ошибка представления с плавающей точкой типична.

• Как корректно сравнивать значения с плавающей точкой.

• Как точно представлять числа, используя типы Fraction и Decimal. 

Узнайте о числах в Python ещё больше. Например, знаете ли вы, что int — не единственный целочисленный тип в Python? Узнайте, какой есть ещё, а также о других малоизвестных фактах о числах в моей статье.

А мы поможем вам прокачать скиллы или с самого начала освоить профессию, востребованную в любое время:

• Профессия Fullstack-разработчик на Python

• Профессия Data Analyst

Выбрать другую востребованную профессию.

Числа с плавающей точкой представлены в компьютерах в виде двоичных дробей. Например, десятичная дробь 0.125 имеет значение 1/10 + 2/100 + 5/1000, и таким же образом двоичная дробь 0.001 имеет значение 0/2 + 0/4 + 1/8. Эти две дроби имеют одинаковые значения, единственное реальное отличие состоит в том, что первая записана в дробной записи с основанием 10, а вторая — с основанием 2.

Сначала проблему легче понять из базы 10. Рассмотрим дробь 1/3. Вы можете приблизить это как основную 10 фракцию: 0.3 или лучше, 0.33или лучше, 0.333 и так далее. Независимо от того, сколько цифр вы хотите записать, результат никогда не будет ровно 1/3, но будет все более приближенным к 1/3.

Таким же образом, независимо от того, сколько цифр из 2-х оснований вы хотите использовать, десятичное значение 0,1 не может быть представлено в точности как дробь из 2-х оснований. В базе 2 1/10 — бесконечно повторяющаяся дробь 0.0001100110011001100110011...

Остановитесь на любом конечном количестве битов, и вы получите приближение. На большинстве современных машин числа с плавающей запятой аппроксимируются с использованием двоичной дроби, а числитель использует первые 53 бита, начиная с самого старшего бита, а знаменатель — как степень двух. В случае 1/10 двоичная дробь равна 3602879701896397/2 ** 55, что близко, но не точно равно истинному значению 1/10.

Многие пользователи не знают о приближении из-за способа отображения значений. Python печатает только десятичное приближение к истинному десятичному значению двоичного приближения, хранящегося на машине. На большинстве машин, если бы Python должен был печатать истинное десятичное значение двоичного приближения, хранящегося для 0.1, он должен был бы отображать

>>> 0.1
# 0.1000000000000000055511151231257827021181583404541015625

Это больше цифр, чем большинство людей считают полезным, поэтому Python сохраняет количество цифр управляемым, отображая округленное значение вместо

Просто помните, что хотя напечатанный результат выглядит как точное значение 1/10, фактическое сохраненное значение является ближайшей представимой двоичной дробью.

Интересно, что существует много разных десятичных чисел, которые имеют одну и ту же ближайшую приблизительную двоичную дробь. Например, числа 0.1 и 0.10000000000000001 и 0.1000000000000000055511151231... все приблизительно равны 3602879701896397/2 ** 55. Поскольку все эти десятичные значения имеют одинаковую аппроксимацию, любое из них может отображаться при сохранении инварианта eval(repr(x)) == x.

Исторически Python и встроенная функция repr() выбирали функцию с 17 значащими цифрами, 0.10000000000000001. Начиная с Python 3.1 в большинстве систем теперь может выбирать самый короткий из них и просто отображать 0.1.

Обратите внимание, что это по своей природе двоичное число с плавающей точкой: это не ошибка в Python и не ошибка в вашем коде. Вы увидите то же самое на всех языках, которые поддерживают арифметику с плавающей запятой.

Для более приятного вывода вы можете использовать форматирование строки для получения ограниченного числа значащих цифр:

>>> import math
>>> format(math.pi, '.12g')
# '3.14159265359'
>>> format(math.pi, '.2f')
# '3.14'
>>> repr(math.pi)
# '3.141592653589793'

Важно понимать, что в действительности это иллюзия: вы просто округляете отображение истинного значения.

Одна иллюзия может породить другую. Например, поскольку 0,1 не является точно 1/10, суммирование трех значений 0,1 может также не дать точно 0,3:

>>> 0.1 + 0.1 + 0.1 == 0.3
# False

Кроме того, поскольку 0,1 не может приблизиться к точному значению 1/10, а 0,3 не может приблизиться к точному значению 3/10, предварительное округление функцией round() может не помочь:

>>> round(0.1, 1) + round(0.1, 1) + round(0.1, 1) == round(0.3, 1)
# False

Двоичная арифметика с плавающей точкой содержит много сюрпризов, подобных этому. Проблема с 0.1 подробно объясняется в разделе «Ошибка представления». Смотрите также «Опасности с плавающей точкой» для более полного описания других распространенных сюрпризов.

Как говорится, «простых ответов нет». Тем не менее, не следует чрезмерно опасаться чисел с плавающей запятой! Ошибки в операциях с плавающей запятой Python наследуются от аппаратного обеспечения чисел с плавающей запятой, и на большинстве машин они имеют порядок не более одной части в 2 ** 53 на операцию. Это более чем достаточно для большинства задач, но вам нужно помнить, что это не десятичная арифметика и что каждая операция с плавающей запятой может подвергаться новой ошибке округления.

Несмотря на то, что патологические случаи существуют, для наиболее случайного использования арифметики с плавающей запятой вы увидите ожидаемый результат в конце, если просто округлите отображение окончательных результатов до ожидаемого количества десятичных цифр. str() обычно достаточно, и для более точного управления смотрите спецификаторы формата метода str.format().

Для случаев использования, которые требуют точного десятичного представления, попробуйте использовать модуль decimal, который реализует десятичную арифметику, подходящую для приложений бухгалтерского учета и высокоточных приложений.

Другая форма точной арифметики поддерживается модулем fractions, который реализует арифметику, основанную на рациональных числах, поэтому числа, такие как 1/3 могут быть представлены точно.

Если вы большой пользователь операций с плавающей запятой, вам следует взглянуть на пакет Numeric Python и многие другие пакеты для математических и статистических операций, предоставляемых проектом SciPy.

Python предоставляет инструменты, которые могут помочь в тех редких случаях, когда вы действительно хотите узнать точное значение числа с плавающей точкой. Метод float.as_integer_ratio() выражает значение типа float в виде дроби:

>>> x = 3.14159
>>> x.as_integer_ratio()
# (3537115888337719, 1125899906842624)

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

>>> x == 3537115888337719 / 1125899906842624
# True

Метод float.hex() выражает число с плавающей запятой в шестнадцатеричном формате (основание 16), снова давая точное значение, сохраненное компьютером:

>>> x.hex()
# '0x1.921f9f01b866ep+1'

Это точное шестнадцатеричное представление может быть использовано для точного восстановления значения с плавающей точкой:

>>> x == float.fromhex('0x1.921f9f01b866ep+1')
True

Поскольку представление является точным, оно полезно для надежного переноса значений между различными версиями Python и обмена данными с другими языками, поддерживающими тот же формат, например Java.

Другим полезным инструментом является функция math.fsum(), которая помогает уменьшить потерю точности во время суммирования. Она отслеживает «потерянные цифры», когда значения добавляются в промежуточный итог. Это может повлиять на общую точность, так что ошибки не накапливаются до такой степени, что бы влиять на итоговую сумму:

>>> import math
>>> sum([0.1] * 10) == 1.0
False
>>> math.fsum([0.1] * 10) == 1.0
True

Ошибка представления.

В этом разделе подробно объясняется пример 0.1 и показано, как вы можете выполнить точный анализ подобных случаев самостоятельно. Предполагается базовое знакомство с двоичным представлением чисел с плавающей точкой.

Ошибка представления относится к тому факту, что фактически большинство десятичных дробей не могут быть представлены точно как двоичные дроби (основание 2) . Это главная причина, почему Python или Perl, C, C++, Java, Fortran и многие другие языки часто не будут отображать точное десятичное число, которое ожидаете.

Это почему? 1/10 не совсем представимо в виде двоичной дроби. Почти все машины сегодня используют арифметику IEEE-754 с плавающей точкой, и почти все платформы отображают плавающие значения Python в IEEE-754 с «двойной точностью». При вводе, компьютер стремится преобразовать 0,1 в ближайшую дробь по форме J / 2 ** N, где J — целое число, содержащее ровно 53 бита.

Перепишем 1 / 10 ~= J / (2**N) как J ~= 2**N / 10 и напоминая, что J имеет ровно 53 бита, это >= 2**52, но < 2**53, наилучшее значение для N равно 56:

>>> 2**52 <=  2**56 // 10  < 2**53
# True

То есть 56 — единственное значение для N, которое оставляет J точно с 53 битами. Наилучшее возможное значение для J тогда будет округлено:

>>> q, r = divmod(2**56, 10)
>>> r
# 6

Поскольку остаток больше половины от 10, наилучшее приближение получается округлением вверх:

>>> q+1
# 7205759403792794

Поэтому наилучшее возможное приближение к 1/10 при двойной точности 754: 7205759403792794 / 2 ** 56. Деление числителя и знаменателя на два уменьшает дробь до: 3602879701896397 / 2 ** 55

Обратите внимание, поскольку мы округлили вверх, то значение на самом деле немного больше, чем 1/10. Если бы мы не округлили, то значение был бы немного меньше 1/10. Но ни в коем случае это не может быть ровно 1/10!

Таким образом, компьютер никогда не «видит» 1/10: то, что он видит, это точная дробь, указанная выше, наилучшее двоичное приближение 754, которое он может получить:

>>> 0.1 * 2 ** 55
# 3602879701896397.0

Если мы умножим эту дробь на 10 ** 55, мы увидим значение до 55 десятичных цифр:

>>> 3602879701896397 * 10 ** 55 // 2 ** 55
# 1000000000000000055511151231257827021181583404541015625

Это означает, что точное число, хранящееся в компьютере, равно десятичному значению полученному выше. Вместо отображения полного десятичного значения многие языки, включая более старые версии Python округляют результат до 17 значащих цифр:

>>> format(0.1, '.17f')
'0.10000000000000001'

>>> from decimal import Decimal
>>> from fractions import Fraction
>>> Fraction.from_float(0.1)
# Fraction(3602879701896397, 36028797018963968)
>>> (0.1).as_integer_ratio()
# (3602879701896397, 36028797018963968)
>>> Decimal.from_float(0.1)
# Decimal('0.1000000000000000055511151231257827021181583404541015625')
>>> format(Decimal.from_float(0.1), '.17')
# '0.10000000000000001'

Краткое условие задачи
По координатам двух клеток шахматной доски, определить какие фигуры могут перейти с первой на вторую клетку.
Если нужны подробности, вот:

Тесты из примеров моя программа проходит. Еще проверял на A1 H8 и подобных где ответ Bishop или Pawn
Сделал максимально понятно с функциями для каждой фигуры. В описании ошибок нашел что ошибки типа Presentation Error возникают, если неправильный формат вывода. Не понимаю что у них там в тестах и каким образом может быть неправильный формат вывода. Может ошибка в чём-нибудь не том?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

function Rook(c1,c2:string):boolean;
begin
  if (c1[1]=c2[1]) or (c1[2]=c2[2]) then Rook:=True else Rook:=False;
end;
 
function Bishop(a,b:string):boolean;
begin
  if (abs(ord(a[1])-ord(b[1]))=abs(ord(a[2])-ord(b[2]))) then Bishop:=True else Bishop:=False;
end;
 
function Knight(a,b:string):boolean;
begin
  if ((abs(ord(a[1])-ord(b[1]))=1) and (abs(ord(a[2])-ord(b[2]))=2)) or
  ((abs(ord(a[2])-ord(b[2]))=1) and (abs(ord(a[1])-ord(b[1]))=2)) then  Knight:=True else Knight:=False;
end;
 
function Queen(a,b:string):boolean;
begin
  if Bishop(a,b) or Rook(a,b) then Queen:=True else Queen:=False;
end;
 
function King(a,b:string):boolean;
begin
  if ((abs(ord(a[1])-ord(b[1]))=0) or (abs(ord(a[1])-ord(b[1]))=1)) and
  ((abs(ord(a[2])-ord(b[2]))=0) or (abs(ord(a[2])-ord(b[2]))=1)) then King:=True else King:=False;
end;
 
function Pawn(a,b:string):boolean;
begin
  if a[2]='2' then
  begin
    if (a[1]=b[1]) and (((ord(b[2])-ord(a[2])=1)) or ((ord(b[2])-ord(a[2])=2))) then Pawn:=True else Pawn:=False;
  end
  else if (a[1]=b[1]) and (ord(b[2])-ord(a[2])=1) then Pawn:=True else Pawn:=False;
end;
  var s1,s2:string[2]; input:string;
begin
  readln(input);
  s1:=copy(input,1,2); s2:=copy(input,4,2);
  if Rook(s1,s2) then writeln('Rook');
  if Bishop(s1,s2) then writeln('Bishop');
  if Knight(s1,s2) then writeln('Knight');
  if Queen(s1,s2) then writeln('Queen');
  if King(s1,s2) then writeln('King');
  if Pawn(s1,s2) then writeln('Pawn');
  if not(Rook(s1,s2) or Bishop(s1,s2) or Knight(s1,s2) or Queen(s1,s2) or King(s1,s2) or Pawn(s1,s2)) then writeln('Nobody');
end.

Программа