Реферат: Cостязания по информатике олимпиады
1) отремонтировать велосипед, изготовив недостающие части из подручного материала (написать процедуры, расширяющие «зауженный» ограничениями язык);
2) проехать это расстояние на одном колесе, ничего не изобретая и неконструируя (нестандартно использовать имеющиеся средство);
3) вообще изобрести и изготовить новый велосипед (неожиданно для судей). Возвращаясь к информатике, отметим, что самая тривиальная задача может стать необычайно трудной, если условие дополнить рядом ограничений на используемые средства.
Такой прием порождения задач не только сильно упрощает условия, но и облегчает контроль. Но теперь при проверке нужно внимательно просмотреть и листинг. Это вообще поучительно для члена жюри любого уровня, но пока делалось, к сожалению, редко: надо было успеть протестировать задачи.
При введении ограничений важны уровень и полнота их системы: слишком сильные ограничения сделают задачу неразрешимой; слишком слабые — тривиальной, нетворческой; неполная система ограничений дает возможность найти «лазейку» — «законно» воспользоваться «незаконным» приемом (в нашем примере — уцепиться за бампер автобуса).
Ограничения на использование готовых средств
Признаком способностей к алгоритмизации мы полагаем умение обходиться малыми средствами, но комбинировать их свободно, расширяя свой арсенал, в сущности — язык.
Поэтому вместо очередной дискуссии о том, «чей» язык лучше, предлагаются ограничения, которые, во-первых, выравнивают условия для участников, а во-вторых, сами по себе являются источником задач, в том числе и олимпиадных. Так, например, при любом языке реализации можно запретить:
1) GOTO и любые команды циклов (FOR, WHILE, REPEAT, заодно «пострадают» и команды типа REPLACE .. FOR из сред DBASE);
2) все функции и процедуры с параметрами, кроме ввода-вывода;
3) ассемблер, машинные команды (во избежание обхода «снизу»);
4) непосредственное обращение к памяти (PEEK, MEM и др.).
Этим выравниваются возможности процедурных языков. Остаютсярекурсия без параметров и условные команды. Этого достаточно для реализации любой конструкции языка. Кроме того, это сближает возможности обычных языков программирования с «насквозь» рекурсивными средствами алгоритмизации для исполнителей проекта «Пилотные школы». В конкретных случаях эти ограничения могут быть ослаблены или расширены автором задачи. Но вводимые ограничения должны быть тщательно взвешены, совершенно прозрачны для жюри и участника и в совокупности однозначны и непротиворечивы.
Типичный прием построения задачи — запретить операцию, функцию и предложить реализовать ее любыми оставшимися средствами. Тем самым выполняется и внутрипредметное моделирование в стиле методики учебника А. Г. Кушниренко и др.
Пример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 параллельных процессорах одно временно, как бы за один шаг).