1. Прибавь 1,

2. Умножь на 4.

Первая из них увеличивает число на экране на 1, вторая - увеличивает его в 4 раза.

Программа для Экса - это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 32?

Ответ обоснуйте.

Решение.

Будем строить дерево решений. Ребра в нем будут помечены допустимыми командами (на рисунке ребра, идущие вверх, соответствуют команде 1, а ребра идущие вниз, - команде 2). В каждом узле будет записано текущее число, т.е. число, полученное из числа 1 с помощью последовательности команд, которые соответствуют пути из корня в этот узел. В корне будет записано число 1. Нас интересует количество путей из корня в вершины, помеченные числом 32.

Если в вершине записано число п от 9 до 32, то из этой вершины есть ровно один путь в вершину с пометкой 32. Действительно, один такой путь всегда есть, он соответствует последовательности из 32-п ребер с пометкой 1 (т.е. выполнить команду «прибавь 1»). Если мы «свернем» с этого пути, т.е., находясь, в промежуточной точке, выполним команду «умножь на 4», то мы получим число, большее, чем 32. Т.к. обе наши операции увеличивают исходное число, то далее мы не сможем получить число 32. Поэтому можно останавливать построение дерева, попав в вершину с числом, большим или равным 9. Для удобства можно добавить «особое» ребро, которое из такой вершины ведет в новую вершину с пометкой 32 (это ребро будет представлять единственный путь, ведущий из этой вершины в вершину с пометкой 32). Количество программ будет равно количеству листьев в полученном дереве.

Это дерево изображено на рисунке Ответ: 15.

4. При оценке подобных решений нужно следовать указаниям по оцениванию. Отметим отдельно несколько ситуаций.

1. Оценка 3 балла ставится, если выполнены все требования, приведенные в пп. 1 и 2 (если нарисовано сокращенное дерево).

2. Если пояснения неполные (например, явно не сказано, что узлы дерева, соответствующие большим числам, не рисуются, потому что

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

3) Если выполнены требования п.2, но написан неправильный ответ (видимо, экзаменуемый ошибся при подсчете), то ставится 1 балд.

Задание с4

1. В решении может присутствовать опечатка, в результате которой оно становится синтаксически или логически неверным (a[i] вместо а[j], a[1] вместо a[i].x и т. п.). Если из анализа решения видно, что это именно опечатка (например, из комментариев, или если в большинстве аналогичных случаев автор программы не ошибся), то ее НЕ следует рассматривать как синтаксическую или логическую ошибку.

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

3. По невнимательности экзаменуемого решается не совсем та задача. Например, выводится, сколько каких букв встречается в тексте, а не ищется наиболее часто встречаемая буква. Те части решения, которые в программе отсутствуют (например, поиск максимума), следует приравнивать к логическим ошибкам в соответствующих алгоритмах.

4. Программа может быть написана на языке программирования, отличном от Бейсика или Паскаля, например, на алгоритмическом языке, языках С, С++, С#, Java, Perl, PHP и т.д. При этом допускается использование библиотек, описанных в стандартах языка. Например, при использовании языка С++ допускается использование средств стандартных библиотек (библиотеки STL). Могут использоваться и современные версии языков Паскаль и Бейсик. При необходимости эксперт может воспользоваться справочной литературой.

В тексте задания есть фраза «Перед текстом программы кратко опишите используемый вами алгоритм решения задачи». Отсутствие такого описания (при наличии правильной программы) не является основанием для снижения оценки, задание НЕ контролирует умение экзаменующегося составлять описания. Назначение описания -облегчить работу проверяющего эксперта. Согласно указаниям по оцениванию, эксперт должен решать, являются ли ошибки допущенные экзаменуемым случайными описками или они показывают некомпетентность экзаменуемого. Описание может помочь проверяющему понять текст программы, зная, что именно собирается в ней делать ученик. Хорошее описание может быть основанием для выставления 1 балла в случае плохой реализации. В критериях на 1 балл явно написано: «Программа, возможно, неверно работает при некоторых входных данных, но по приведённому тексту решения ясно, что экзаменуемый понимает, из каких этапов должно состоять решение задачи». Здесь «текст решения» включает в себя и описание, о котором идет речь. 6. В задании С4 использование учащимся в решении подпрограмм (функций) из стандартных библиотек вполне допустимо, при условии, что они правильно описаны (если это требуется правилами языка) и правильно вызываются, т.е. нет ошибок в количестве, порядке и типе аргументов.

Внимание! При выставлении баллов за выполнение задания в «Протокол проверки ответов на задания бланка № 2» следует иметь в виду, что если ответ отсутствует (нет никаких записей, свидетельствующих о том, что экзаменуемый приступал к выполнению задания), то в протокол проставляется «X», а не «0».