Cостязания по информатике (олимпиады)
Категория реферата: Рефераты по информатике, программированию
Теги реферата: менеджмент, бесплатные дипломные работы
Добавил(а) на сайт: Карев.
Предыдущая страница реферата | 1 2 3 4 5 6 | Следующая страница реферата
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...
Ограничения на «программирование»
Признаком другого стиля мышления (назовем его пользовательским, в отличие от логико-алгоритмического «программистского») можно считать избегание программирования, стремление применить к своей задаче готовые средства, а если они не годятся — найти нестандартное, оригинальное применение другим доступным средствам, ведущее к цели, снова проявить способность к творчеству.
Характерной чертой такой деятельности является преобразование задачи, переход к другим типам данных, программ и команд. Например, целому числу
можно сопоставить отрезок числовой оси или последовательность единиц.
Для такой деятельности необходимы:
образованность, знание явных и неявных возможностей различных готовых
средств, как в «любимом» языке, так и вне его;
сформированность системно-комбинаторных мыслительных операций — видение
предметов и явлений в целостности, взаимосвязях; умение строить несколько
взаимодополняющих точек зрения на один и тот же объект, умение оперировать
понятийными и орудийными средствами из различных дисциплин (так, например, с точки зрения алгебры функция есть соответствие, с точки зрения геометрии
— кривая, с точки зрения информатики — алгоритм вычисления результата по
заданному аргументу).
Для того чтобы проявить эти качества участника, нужно, так сказать, запретить ему программировать.
Это почти противоположно по отношению к ограничениям первого типа:
чтобы выявить способности и опыт творчества в области алгоритмизации, мы
вынуждали участника составлять довольно изощренные алгоритмы для решения
«простых» задач (в примере — операция умножения). Теперь же он получает в
распоряжение средства, но — кроме нужных для программирования. Теперь
логично разрешить только линейные алгоритмы. Ведь соответствующая
деятельность «пользователя» — это построение последовательности шагов по
преобразованию среды. Его легко обеспечить через запрет логических
выражений: именно проверки условий «расщепляют» алгоритм на циклы и
ветвления. Для избежания программирования снова запрещаем машинные коды и
ассемблер. Всё остальное — можно. Команду типа НЦ ДЛЯ или FOR тоже
необходимо разрешить; она нужна для ввода таблиц (теоретически и в будущем
может выполняться на N параллельных процессорах одно временно, как бы за
один шаг).
В идеале решение задачи теперь должно быть представлено в виде линейной последовательности обращений к библиотечным и стандартным функциям, процедурам и программам (или даже в виде командного файла).
Уместно сказать теперь об электронных таблицах. Из встроенных в них циклов придется запретить итерационный цикл ДО заданной точности: он позволяет «почти все».
Приведем упрощенные примеры для иллюстрации задач второго типа. Первый пример — это умножение через логарифмы (см. выше).
Пример 2.
Нужно выяснить, лежит ли точка внутри контура, заданного координатами звеньев.
Рекомендуем скачать другие рефераты по теме: пример курсовой работы, решебники скачать бесплатно.
Предыдущая страница реферата | 1 2 3 4 5 6 | Следующая страница реферата