Две задачи

Что вкладывается в понятие “мощный язык программирования”?

Это качество не означает, что язык позволяет вам писать программы, выполняющие что-либо, не доступное другим языкам. В этом смысле языки равноценны. Если вы можете написать программу на Лого, то так или иначе вы сможете написать ее на Паскале или Бейсике. Верно и обратное.

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

Brian Harvey

Задачи повышеного уровня сложности — олимпиадные или, скажем, третьей части ЕГЭ — составляются в расчете на три языка программирования: Паскаль, Бейсик, Си. Здесь разбираются решения на Лого для двух таких задач. Первая очень хорошо “ложится” на средства Лого. Вторая, казалось бы, должна демонстрировать ограниченные возможности Лого по сравнению с “настоящими” языками, но…

Версия среды — ЛогоМиры 2.0.

Итак, первая задача.

Симметричная последовательность (Московская олимпиада по информатике, очный тур, 2006).

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:

1 2 3 4 5 4 3 2 1

1 2 1 2 2 1 2 1

Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной. Элементы последовательности — N натуральных чисел от 1 до 9, 1 ? N ? 100. Выведите сначала число M — минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел (каждое — от 1 до 9).

Решение. Исходные данные — список. Сначала разделим список A пополам, на голову B и хвост C (вторая половина А при этом переворачивается).
И сравним B и C.

это симм? :A

make "B []

make "C []

; B — голова, а C — хвост списка

repeat 0.5 * count :A

[make "B se :B first :A

make "C se :C last :A

make "A bf :A

make "A bl :A]

op equal? :B :C

end

Это логическая функция для определения — является ли входной список A симметричной последовательностью. Теперь напишем рекурсивную процедуру для “накопления” списка, который надо дописать в хвост входному списку, чтобы он стал симметричной последовательностью.

это доп :A

if or empty? :A симм? :A [stop]

make "D se first :A :D

доп bf :A

end

Процедура на каждом шаге “откусывает” первый элемент входного списка и приписывает его в начало списка-дополнения D. Процесс продолжается до тех пор, пока “остаток” от входного списка не окажется симметричным или пустым. И, наконец, главная процедура:

это задача1 :A

ifelse симм? :A [pr 0]

[make "D []

доп :A

pr count :D pr :D]

end

Пример запуска процедуры

задача1 [1 3 4 2 5 5 6]

Результат в текстовом окне

6

5 5 2 4 3 1

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

Вторая задача — на обработку массива.

ЕГЭ, демоверсия-2009, задача C4.

На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В пер-
вой строке сообщается количество учащихся N, каждая из следующих N строк имеет формат: <Фамилия> <Инициалы> <номер школы>, где <Фамилия> — строка, состоящая не более чем из 20 символов, <Инициалы> — строка, состоящая из четырех символов (буква, точка, буква, точка), <номер школы> —
не более чем двузначный номер. <Фамилия> и <Инициалы>, а также <Инициалы> и <номер школы> разделены одним пробелом. Пример входной строки:

Иванов П.С. 57

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

Следует учитывать, что N 1000.

Критерии оценивания

Правильная программа, написанная на Паскале, Бейсике или Си, должна верно читать входные данные, не запоминая их все, а сразу подсчитывая в массиве, хранящем 99 целых чисел согласно номерам школ, количество участников олимпиады из каждой школы. Затем с использованием ненулевых элементов этого массива программа должна найти минимальный элемент, затем распечатать номера соответствующих школ.

Пример правильной программы на Паскале:

var a:array[1..99] of integer;

p:1..99; c:char;

i, k, N, min: integer;

begin

readln(N);

for i := 1 to 99 do a[i] := 0;

for i := 1 to N do

begin

repeat read(c)

until c = ' '; {считана фамилия}

repeat read(c)

until c = ' '; {считаны инициалы}

readln(p);

a[p] := a[p] + 1;

end;

min := N;

for i := 1 to 99 do

if a[i] > 0 then

begin

if a[i] < min then min := a[i]

end;

for i := 1 to 99 do

if a[i] = min then writeln(i);

readln

end.

Будем решать задачу на Лого. Сначала разберемся с вводом данных. Естественно предположить, что в работающей программе данные считываются из файла. Просто чтение из файла не требуется описывать. В среде ЛогоМиры текстовый файл можно загрузить в текстовое окно и дальше работать с этим текстом. В частности, брать строку за строкой по очереди. В текстовое окно можно загрузить довольно большие тексты. У меня, например, успешно поместился пробный текст с исходными данными к этой задаче, в котором было 4 тысячи строк. В среде MSWLogo можно вести побайтные чтение и запись в файл, то есть получится практически аналогично тому, как сделано на Паскале.

Двигаемся дальше: требуется создать массив. Массивов в Лого нет. Может быть, создать список из 99 элементов и использовать его как массив? Так сделать можно, но это не будет хороший вариант. Прочитать любой элемент списка не сложнее, чем элемент массива, но вот заменить какой-то элемент “внутри” списка хлопотно. Придется писать вспомогательную процедуру. И неэффективно получится.

Лучше мы создадим 99 переменных и будем работать с ними. Пусть они будут называться так:

a1 a2 a3 a4 … a99

Cначала надо будет присвоить каждой нулевое значение. Как это сделать? Наверное, вы не раз слышали (или сами думали): “Ну почему в Лого такая громоздкая запись для команды присваивания? Вот в Паскале a:=a+1, а в Лого MAKE "a :a + 1.”. Да, выглядит громоздко. Но, оказывается, возможности команды присваивания в Лого пошире, чем в Паскале или Бейсике. У команды присваивания два параметра. Первый — слово, а второй — любой. И чаще всего на месте первого параметра стоит константа. А может стоять любое выражение! Вот так можно обнулить все наши 99 переменных:

make "i 0

repeat 99 [make word "a :i 0

make "i :i + 1]

То есть в цикле 99 раз выполняется команда: записать ноль в переменную, имя которой — слово, состоящее из буквы a и значения переменной i. Получилось ненамного длиннее, чем на Паскале.

А как увеличить значение i-й переменной на единицу?

make word "a :i 1 + thing word "a :i

Операция thing сообщает значение названной переменной. То есть последняя часть инструкции “переводится” так: значение переменной, имя которой — слово, состоящее из буквы a и значения переменной i.

Здесь нам понадобилось узнать значение переменной, имя которой задано косвенно. Если имя переменной — константа, то для упрощения записи в Лого можно использовать знак двоеточия перед именем вместо thing. То есть полная, не упрощенная запись инструкции выглядит так:

make word "a thing "i

1 + thing word "a thing "i

Да, длинновато... Все-таки надо поблагодарить авторов языка за соглашение о двоеточии!

Таким образом, наш набор из 99 переменных работает, по сути, так же, как и массив в Паскале.

Напишем “косметическую” вспомогательную функцию — для сокращения текста программы:

это эл :i

op thing word "a :i

end

эл :i — это то же самое, что a[i] в программе на Паскале.

Подготовим пробный исходный текст, соответствующий заданию. Пусть имя файла C4_input.txt. Создадим текстовое окно на листе проекта. Его имя (по умолчанию) — текст1.

Текст программы (по принципу работы она не отличается от образца на Паскале).

это задача2

ct loadtext "c4_input

make "N textcount "текст1

; загрузили текст с исходными данными

; и подсчитали количество строк в нем

make "i 1

repeat 99 [make word "a :i 0 make "i :i + 1]

; создали и обнулили псевдомассив

make "i 1

repeat :N [

make "p last parse textitem :i "текст1

; выделили номер школы

; из очередной строки

make word "a :p 1 + эл :p

; увеличили значение соответствующего

; элемента псевдомассива

make "i :i + 1]

ct

make "i 1

make "min :N

repeat 99 [

if and 0 < эл :i :min > эл :i

[make "min эл :i]

make "i :i + 1]

; нашли минимум

make "i 1

repeat 99 [

if :min = эл :i [pr :i]

make "i :i + 1]

; сделали вывод результатов

end

Программа работает, конечно, медленнее, чем та, что написана на Паскале. Ведь любой Лого — интерпретатор. В MSWLogo будет побыстрее.

Итак, получается, что и такие задачи, с учетом таких условий можно успешно решать на Лого. Я совсем не призываю немедленно перейти к ЕГЭ на Лого. Но ведь интересно исследовать границы возможностей языка!