Lab04_2010

Сохраните и запустите программу на выполнение. В консоли появятся запросы, на которые понадобится ответить (например, так, как на рис. 58), после чего будет сформирован входной файл (начало его приведено на рис. 59).

Рис. 58. Ответьте на запрос программы

Рис. 59. Начальные элементы файла input.txt

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

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

Рис. 60. Начальные элементы файла output.txt

Можете выполнить еще несколько запусков программы и сохранить (по крайней мере) один из «больших случайных» тестов в папке test (как input.10 и output.10).

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

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

Рис. 61. Перед отправкой на проверку «лишний» метод нужно закомментировать

Наконец, вердикт Accepted получен (рис. 62), т.е., программа успешно прошла все тесты, имеющиеся в проверяющей системе.

Рис. 62. Все тесты, имеющиеся в проверяющей системе, программа прошла.

После этого программу можно попробовать сдать преподавателю.

Примечание.

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

проверяющая система сообщает об ошибке на каком-либо тесте (отличном от первого), можете обратиться к преподавателю с просьбой перепроверить тесты.

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

поправок приобрел вид нагромождения условных операторов и выглядит некрасиво. Конечно, это может не показаться Вам весомым аргументом, но изящный код легче отлаживать, поддерживать… (и если «переиграть» цитату, приписываемую и А.Н. Туполеву, и А.С. Яковлеву, и многим другим авиаконструкторам – «некрасивый самолет не полетит»; то – «некрасивая программа не заработает»).

Поэтому задачей следующего параграфа будет превратить этот код в «достаточно красивый».

§ 13. Меняем последовательность действий (и немного – их логику)

Вернемся к нашим исходным рассуждениям, которые проводились при наличии, по крайней мере, двух минимумов и двух максимумов. Чтобы определить максимально удаленную друг от друга пару «минимум – максимум», мы сравнивали значения разностей (iRightMax – iLeftMin) и (iLeftMax – iRightMin) по абсолютной величине. По результатам этого сравнения определялись значения границ выводимой части последовательности: в первом случае делался вывод, что минимум расположен левее максимума, во втором – наоборот, максимум левее минимума.

Тогда можно отказаться от сравнения по абсолютной величине и сравнивать только сами разности, записав вторую как (iRightMin – iLeftMax): ведь в случае «превосходства» мы вычитаем из большего значения меньшее. В таблице 1 приводятся соответствующие значения для некоторых тестов (1 обозначена разность iRightMax – iLeftMin, а 2 –

разность iRightMin – iLeftMax):

Таблица 1. Значения разностей для некоторых тестов (в скобках в графе «Знак» указывается, какая из разностей должна быть выбрана).

Как можно видеть, в случае, когда минимум и максимум в последовательности единственны (тесты с 06 по 09), их взаимное расположение определяется вполне однозначно: та разность, которая принимает положительное значение, и задает «правильный порядок». В случае же равенства разностей (тесты 03 и 04) для различающихся минимумов и максимумов выбирается всегда пара «правый максимум и левый минимум». Это означает, что мы сможем обойтись одним сравнением для всех этих

случаев, и выделять отдельно ситуацию, когда минимум и максимум единственны, нет необходимости.

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

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

Напишем новый метод – solution2() (рис. 63), в котором и реализуем приведенные выше рассуждения.

Рис. 63. Код метода solution2()

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

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

Индивидуального задания эта лабораторная работа не содержит. Вам предстоит выполнить такое задание в качестве зачетной задачи по курсу «Языки программирования». Конечно, Вы можете «потренироваться» самостоятельно, воспользовавшись разделами «Для подготовки», «Архив задач» и «Соревнования». Задачи в официальных соревнованиях (их легко отличить по «длинным» названиям) обычно сформулированы более точно, нежели тренировочные задачи. Большое количество сданных решений часто свидетельствует о том, что задача не слишком сложная.

Задание (общее).

В лабораторной работе № 3 рассматривалось использование в качестве хранилища данных объекта класса ArrayList. Измените программу так, чтобы вместо «обычного» массива был использован именно объект класса ArrayList.

Контрольные вопросы.

1.Что означает модификатор static для поля? А для метода?

2.Что означает модификатор final для поля? Для метода?

3.Можно ли в конструкторе Task39() было обойтись без переменных Min и Max? Если да, то как?

4.Сообщение о какой ошибке проверяющая система может выдать, если написать

иотправить на проверку «наивное» решение (описанное в параграфе 1)?

5.Сообщение о какой ошибке Вы получите от проверяющей системы, если отправите на проверку решение, в котором не закомментирована строка, генерирующая входной файл?

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

a.в последовательности 10000 элементов; причем все они либо равны 100, либо равны 1000

b.в последовательности 10000 элементов, причем один из них равен 100, а все остальные равны 1000

c.в последовательности 10000 элементов, причем один из них равен 1000, а все остальные равны 100

d.в последовательности 10000 элементов, причем это числа от 1 до 10000 в порядке возрастания

e.в последовательности 3 элемента, причем два крайних равны между собой

f.в последовательности 100 элементов, минимумов и максимумов в ней одинаковое количество, при этом в последовательности они всегда встречаются в сочетании «минимум, за ним сразу максимум»

g.в последовательности произвольное количество элементов (не самое маленькое и не самое большое); максимумов и минимумов поровну,

причем в последовательности сначала располагаются все максимумы, а затем все минимумы

h.в последовательности произвольное количество элементов, при этом на всех нечетных позициях расположены минимумы, а на всех четных – максимумы

7.Предложите правильную формулу для len, учитывающую случай нулевой длины последовательности и использующую только переменные startIndex и stopIndex

8.Предложите, как можно обойтись без переменной outputDirection

9.Изучите класс Random.

a.чем отличаются его методы nextInt() и nextInt(int n)?

b.как можно получить последовательность случайных целых чисел в диапазоне от –m до n? (m, n > 0)

c.как можно получить случайные вещественные числа в диапазоне от R до S (R, S > 0)? А в диапазоне от –R до S?

d.какую последовательность случайных чисел можно получить, используя метод nextGaussian()?

e.каково назначение метода setSeed()?

f.как можно воспользоваться методом nextBytes()?

10.Предложите, как можно доработать метод createRandomInputFile(), чтобы он

a.генерировал входной файл, содержащий последовательность желаемой пользователем длины

b.генерировал входной файл, в котором данные произвольным образом (в смысле количества) размещались бы по строчкам, количество которых задано пользователем

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

d.генерировал входной файл, который содержал бы только максимумы и минимумы

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

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

11.Как можно просмотреть свое решение задачи в проверяющей системе?