Cостязания по информатике (олимпиады)
Рефераты >> Программирование и компьютеры >> Cостязания по информатике (олимпиады)

Типичный прием построения задачи — запретить операцию, функцию и предложить реализовать ее любыми оставшимися средствами. Тем самым выполняется и внутрипредметное моделирование в стиле методики учебника А. Г. Кушниренко и др.

Пример1.

Составить алгоритм вычисления А´В (для простоты при В>=0. А и В - целые). Кроме указанных выше ограничений запрещается умножение и деление «в лоб».

Решение на «старом» Бейсике может быть таким

10 'Умножение А * В без циклов и goto и *

20 PRINT " Введите множители "

 

30 INPUT А, В

   

40 M1 = А

‘передать параметры

 

50 М2 = В

 

60 R = 0

‘накопитель произведения

 

70 GOSUB 110

 

80 PR = В

‘забрать ответ

 

90 PRINT " произведение = "; PR

   

100 END

   

110 IF М2 = 0 THEM RETURN

‘подпрограмма для R:=R+M1*M2

 

120 М2 = М2 – 1

   

130 R = R + Ml

‘умножение сводится сложению

 

140 GOSUB 110

‘цикл через рекурсию

 

150 RETURN

‘-----à

 

Едва ли это олимпиадная задача, скорее — иллюстрация стиля программирования в условиях «искусственных» ограничений.

Если не запретить использование функций, возможен обход «сверху» в таком стиле:

В = INT(ЕХР(LOG(A) + LOG(B) + 0.5))

что тоже неплохо, но не выявит умения алгоритмизации. Это уже противоположный подход — использование готовых алгоритмов. Другой пример – постановка явно рекурсивной задачи при запрете рекурсии. Формально запрещены вызовы из подпрограмм, все остальное — можно, и особенно — желанное для некоторых GOTO .

Ограничения на «программирование»

Признаком другого стиля мышления (назовем его пользовательским, в отличие от логико-алгоритмического «программистского») можно считать избегание программиро­вания, стремление применить к своей задаче готовые средства, а если они не годятся — найти нестандартное, оригинальное применение другим доступным средствам, ведущее к цели, снова проявить способность к творчеству.

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

Для такой деятельности необходимы:

1) образованность, знание явных инеявныхвозможностейразличных готовыхсредств,как в «любимом» языке, так и вне его;

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

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

Это почти противоположно по отношению к ограничениям первого типа: чтобы выявить способности и опыт творчества в области алгоритмизации, мы вынуждали участника составлять довольно изощренные алгоритмы для решения «простых» задач (в примере — операция умножения). Теперь же он получает в распоряжение средства, но — кроме нужных для программирования. Теперь логично разрешить только линейные алгоритмы. Ведь соответствующая деятельность «пользователя» — это построение последовательности шагов по преобразованию среды. Его легко обеспечить через запрет логических выражений: именно проверки условий «расщепляют» алгоритм на циклы и ветвления. Для избежания программирования снова запрещаем машинные коды и ассемблер. Всё остальное — можно. Команду типа НЦ ДЛЯ или FOR тоже необходимо разрешить; она нужна для ввода таблиц (теоретически и в будущем может выполняться на N параллельных процессорах одно временно, как бы за один шаг).

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

Уместно сказать теперь об электронных таблицах. Из встроенных в них циклов придется запретить итерационный цикл ДО заданной точности: он позволяет «почти все».

Приведем упрощенные примеры для иллюстрации задач второго типа. Первый пример — это умножение через логарифмы (см. выше).

Пример 2.

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

Решение (предложено школьниками).

Вывести цвет проверяемой точки, расположенной на экране.

Нарисовать на экране контур (цикл FOR!).

Залить его цветом.

Снова вывести цвет проверяемой точки.

Тонкие вопросы о «толстых» линиях контура на экране здесь не ставим: пример показывает нестандартное, лукавое и в то же время «наивное» решение через прямое моделирование задачи на экране,

Пример 3.

Нужно найти максимальное из двух чисел А и В. функции МАХ и MIN, естественно, запрещены.

Решение.

Max := (A+B+abs(A-B))/2.

Если забыть запретить функцию MIN, то возможен «обход сбоку»:

Max := A+B-min(A,B).

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

Проведение олимпиад по информатике на основе тестов


Страница: