Lab04_2010

Рис. 18. Скопируем их в папку test

Переименовать файлы в папке test можно либо с помощью пункта контекстного меню Rename (рис. 19 и 20), либо просто выделив файл и нажав кнопку F2 на клавиатуре (рис. 21). Конечно, предлагаемая система именования файлов не единственно возможная. Не исключено, что Вы найдете более удобным создать, например, в папке test подпапки Test01, Test02, Test03 и т.д. и в каждой из них сохранять очередную пару input.txt и output.txt. В этом случае, когда Вам потребуется «вернуть» тесты для проверки на них программы в каталог проекта, переименовывать их не потребуется (можно, разумеется, менять путь к файлу и / или имя этого файла непосредственно в тексте программы, однако делать так сейчас мы не будем).

Рис. 19. Переименовать файл можно с помощью контекстного меню

Рис. 20. Новое имя нужно будет набрать в диалоговом окне

Рис. 21. Можно переименовать файл «обычным образом», выделив его и нажав кнопку F2

Теперь, когда тест из примера к задаче сохранен, попробуем несколько изменить файл input.txt в каталоге проекта и проверить, будет ли программа выдавать верный ответ. Вы уже наверняка заметили, что в тесте из примера самое большое «расстояние» между «самым левым» максимумом и «самым правым» минимумом, при этом максимум расположен левее минимума. Вывод элементов же должен (согласно условию задачи) осуществляться по направлению от минимума к максимуму. Поэтому полезно проверить, будет ли вывод элементов осуществляться в правильном направлении, если максимум окажется правее минимума. Все, что нужно сделать для формирования такого теста, – удалить первое (самое левое) число 8 в последовательности. В этом случае наиболее удаленными друг от друга окажутся «самый левый» минимум (первая единица) и «самый правый» максимум (наиболее близкое к концу последовательности число 8). Файл input.txt будет выглядеть так, как на рис. 22.

Сохраните файл input.txt (с помощью главного меню или панели инструментов) и запустите приложение на выполнение.

Рис. 22. Удалим из файла первое число 8 и сохраним его

Переключитесь на вкладку output.txt. Ответ, который сообщает программа, теперь изменился (рис. 23), его легко проверить вручную и убедиться, что он правильный.

Рис. 23. Ответ программы на второй тест

Вновь скопируйте файлы input.txt и output.txt в каталог test и переименуйте их в input.02 и output.02 (рис. 24).

Рис. 24. Скопируем новый тест в папку test

Наконец, можно удостовериться, что из двух «равноудаленных» друг от друга пар программа будет выбирать всегда именно ту, в которой минимум находится левее. Для этого в файл input.txt добавим еще одно число 8 – непосредственно перед самой левой единицей (рис. 25). Это число 8 станет «самым левым» максимумом, парой которому будет «самый правый» минимум – самая правая единица. Как можно видеть, между ними также будет расположено 8 чисел, как и в предыдущем случае. Если наша программа написана в соответствии с условием задачи, то ответ должен остаться таким же, как и во втором тесте. Сохраните измененный файл input.txt и вновь запустите приложение на выполнение.

Рис. 25. Еще один входной файл для проверки работоспособности программы

Переключитесь на вкладку output.txt и Вы увидите, что выходной файл действительно остался таким же, как и в предыдущем тесте. Скопируйте и эту пару входных и выходных файлов в папку test под именами input.03 и output.03 (рис. 26).

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

Примечание.

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

Рис. 26. Набор тестов снова пополнился

§ 7. Отправка решения на проверку

Перейдите по ссылке «Сдать задачу» на страницу отправки решения (ссылка будет видна лишь в том случае, если Вы зарегистрировались в системе и вошли в нее, используя свои регистрационные данные). Выберите в списке компиляторов Sun Java 1.6 (рис. 27, если он не выбран), после чего скопируйте текст Вашей программы в большое окно для отправки (рис. 28; подсказка: чтобы выделить весь текст в окне NetBeans, можно воспользоваться клавиатурной комбинацией Ctrl + A.). Никакие другие поля в форме заполнять не нужно.

По желанию, Вы можете также пользоваться интерфейсом выбора файла (вместо копирования содержимого файла в форму для отправки). Никакое имя класса указывать не нужно (это требование касается только «неофициального» компилятора GCJ, разработка которого в данный момент приостановилась).

Рис. 27. Выберите компилятор Java из раскрывающегося списка

Рис. 28. Текст программы помещен в форму для отправки (часть комментариев удалена, чтобы показать в окне больший фрагмент кода).

Нажмите на кнопку «Отправить на проверку» и спустя небольшое время (зависит от загруженности системы) Вы увидите сообщение о результате проверки. Сообщение для нашего решения приведено на рис. 29.

Ошибка Runtime Error, возникшая на 5-ом тесте, свидетельствует о следующем. Вопервых, тесты с номерами от 1-го до 4-го программа проходит успешно. Первый тест, на котором происходит ошибка – тест № 5. Вполне возможно, что программа неверно работает и на каких-либо других, последующих тестах – но пользователь системы получает сообщение только о номере первого из тестов, на котором произошла ошибка, и об общем характере ошибки.

Рис. 29. Результат проверки программы автоматизированной системой

§ 8. Возможные сообщения проверяющей системы

Система может выдать одно из следующих сообщений (NN – номер теста; если в дальнейшем набор сообщений изменится, эта лабораторная работа будет обновлена):

Compilation error – ошибка компиляции. Убедитесь, что

а) Ваша программа компилируется в среде, установленной у Вас на компьютере, б) текст программы был скопирован в форму для отправки от начала до конца,

в) Ваша программа начинается со слова package (без учета комментариев; если это не так, и в среде разработки Вы использовали так называемый пакет по умолчанию для своего проекта, допишите package <имя пакета> перед предложениями импорта, <имя пакета> – любой допустимый и не используемый в программе идентификатор)

г) при отправке решения Вы выбрали именно компилятор SUN Java, а не С++ или

Delphi, например.

Runtime error on test NN – ошибка времени выполнения на тесте NN. Стоит проверить, что:

а) фигурная скобка, открывающая описание главного (public) класса стоит на той же строчке, что и имя класса (в силу особенностей скрипта, собирающего jar-файл)

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

в) Ваша программа действительно пытается прочитать данные из файла input.txt, расположенного в каталоге проекта. Если Вы прописали в программе «точный путь с указанием диска, где расположен файл» или назвали его как-нибудь наподобие InPuT.TxT

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

Time limit exceeded on test NN – превышение допустимого времени выполнения, отведенного на программу. По умолчанию на один тест в системе отводится 1 секунда. Если это не так, то в условии задачи явно указано максимальное время, за которое Ваша программа должна пройти один тест. Если Вы получили сообщение о такой ошибке, подумайте

а) не ожидает ли Ваша программа ввода с консоли (особенно если ошибка происходит на первом же тесте) – автоматизированная система тестирования может предоставить ей только файл input.txt и ни на какие запросы «Введите число N» реагировать не будет

б) не возникает ли в программе бесконечного цикла в) впрочем, наиболее частая причина такой ошибки – использование

неэффективного алгоритма. А это значит, что мелкими поправками ситуацию изменить не удастся, придется придумывать новую логику работы.

Wrong answer on test NN – неверный ответ на тесте NN. Ваша программа компилируется, запускается, но, по крайней мере на одном из тестов, имеющихся в системе, выдает ответ, не совпадающий с ответом автора задачи. Вполне возможно, что ошибается автор задачи, а не Вы. Однако если под заголовком задачи в условии Вы

видите строчку «сдано K решений», где K > 2, то высока вероятность, что ошибается все же не автор. Нередко помогает:

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

б) проверка, действительно ли Вы выводите ответ именно в файл ouput.txt, название которого записано строчными латинскими буквами, а не на консоль и не в какой-либо другой показавшийся удобным Вам файл

в) внимательное чтение условия задачи. Подумайте, в частности, что нужно выводить в «крайних» случаях

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

Accepted – решение успешно прошло все тесты, с точки зрения автоматизированной проверяющей системы задача считается решенной. Возможно, преподавателя Вам тоже удастся в этом убедить . В учебных задачах часто накладываются дополнительные требования на решение – например, использовать (или не использовать) некоторые структуры данных или же языковые конструкции. Если Вам представляется, что эти задачи скучны, а требования излишни – попробуйте решить не менее 75% заданий какого-либо студенческого чемпионата (важно, чтобы это были задачи из одного набора – тогда распределение по сложности будет адекватным; не обязательно это должны быть задачи с http://contest.samara.ru, замечательный архив олимпиадных задач есть, например, на http://acm.timus.ru). Если Вы успешно справились с этим, то, наверное, Вы уже посещаете семинар по олимпиадному программированию, а у Вашего преподавателя не слишком много сомнений относительно того, стоит ли выставить Вам зачет.

§ 9. Пополнение тестового покрытия

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

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

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

Когда мы составляли набор из трех тестов, то фактически оставили без внимания следующие вопросы: как поведет себя программа, если

а) во входных данных будет только один минимум? б) во входных данных будет только один максимум? в) минимумов и максимумов будет по одному?

г) входные данные будут содержать последовательность минимальной длины? д) входные данные будут содержать последовательность максимальной длины?

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

Чтобы получить тест, в котором будет только один минимум, удалим из текущего input.txt (который является копией input.03) все единицы, кроме средней (рис. 30).

Рис. 30. Изменим входной файл так, чтобы в нем остался единственный минимум

Сохраните файл и вновь запустите приложение. В файле output.txt будет сформирована выходная последовательность из трех чисел: 8, 4, 2 (рис. 31) – что вполне соответствует ожиданиям. От единственного минимума есть два одинаково удаленных максимума, и выбран из них тот, который находится ближе к концу последовательности.

Рис. 31. Выходная последовательность для случая единственного минимума в последовательности

Скопируйте эти файлы под именем input.04 и output.04 соответственно в папку test

– по этим результатам поправок не требуется, однако input.04 «исследует» два аспекта: что происходит, если в последовательности один минимум, и верно ли выбирается подпоследовательность, если максимумов два и они равноудалены от этого минимума.

Теперь поступим «обратным образом» – уберем из входных данных все максимумы, кроме одного, но «возвратим» минимумы (рис. 32):

Рис. 32. В новом входном файле только один максимальный элемент

Сохранение этого файла и запуск приложения вновь приводят к ожидаемым результатам в output.txt (рис. 33). Полученные файлы скопируйте в папку test как input.05

и output.05.

Рис. 33. Выходная последовательность получается такой, как ожидалась

Оставим теперь в последовательности один минимум и один максимум. Сначала проверим работу программы в случае, если минимум расположен левее максимума (рис. 34):

Рис. 34. Входная последовательность с одним минимумом и одним максимумом (минимум левее)

Полученная программой последовательность отвечает условию задачи (рис. 35):

Рис. 35. Выходная последовательность для единственных минимума и максимума

Аналогичную проверку выполним для ситуации, когда левее расположен максимум (рис. 36), предварительно сохранив входной и выходной файлы в test (с номером 06):