Задание 21

1. Общие сведения
2. Пример задания

3. Решения задач с сайта ege.yandex.ru
4. Краткие сведения по алгебре
5. История

1. Общие сведения

Сложность: повышенная.
Примерное время решения (для тех, кто будет выполнять часть 2):  5 ,минут
Тема: Алгоритмы и программирование
Подтема: Анализ алгоритма, записанного на алгоритмическом языке c использованием вспомогательных алгоритмов
Что проверяется: Умение формально выполнить алгоритм, использующий вспомогательные алгоритмы, и записанный на одном из предусмотренных в ЕГЭ 2012 алгоритмических языков. Умение понять, что делает алгоритм, не выполняя полную трассировку. Умение распознавать стандартные алгоритмы обработки данных (поиск экстремума, суммирование и т.п., см. Кодификатор элементов содержания и требований к уровню подготовки выпускников общеобразовательных учреждений для проведения в 2012 году единого государственного экзамена по информатике и ИКТ)
Примечание. При выполнении этого задания (равно, как и других заданий ЕГЭ) ученик должен использовать знания из базового курса математики.

Общий вид задания:
Дается описание алгоритма на четырех алгоритмических языках. В алгоритме используется несложный (несколько строк) вспомогательный алгоритм. Требуется определить значение указанной в условии переменной после выполнения алгоритма.

2. Пример задания

2.1. Условие задачи.
Задача 2012-B14-1.
Определите, какое число будет напечатано в результате выполнения следующего алгоритма, изображенного на рис.1 (для Вашего удобства алгоритм представлен на четырех языках программирования).

Рис.1. Запись алгоритма на четырех языках программирования.

2.2. Набросок решения

Для краткости мы ограничимся анализом записи алгоритма на Школьном Алгоритмическом Языке, см. Рис.2. Для удобства - перенумеруем строки (при использовании системы Кумир они будут перенумерованы так же).
1. В алгоритме используется вспомогательный алгоритм-функция F, этот алгоритм имеет единственный аргумент типа цел.  Значение F(x) при значении аргумента x - это значение квадратичного многочлена 4*(x-1)*(x-3). См. строки 15 - 18.
2. Алгоритм перебирает все целочисленные значения t от a=-20 до b=20. См. цикл от строки 6 до строки 11.
3. До начала цикла переменной M присваивается значение a, а переменной R - значение F(a). См. строку 5. Внутри цикла вычисляется значение F(t) для очередного значения переменной t. Если выполнено условие F(t) < M, то перевычисляются значения R и M, см. строки 7 - 10. Это означает, что переменная R хранит текущее минимальное значение величин F(t), а переменная M - первое (т.е. наименьшее) значение t, при котором был достигнут этот минимум. То, что хранится именно первая точка минимума, определяется тем, что в строке 7 проверяется строгое неравенство.
4. Таким образом, после выполнения цикла в строках 6 - 11 значение переменной M равно первой из точек минимума значений функции F(x) в целочисленных точках x=-20, …, 20.
5. Из курса алгебры (9 класс) известно, что квадратичная функция

F(x) = 4*(x-1)*(x-3)

достигает минимума в точке 2, см. ниже. Поэтому после завершения выполнения цикла переменная M будет иметь значение 2 и при выполнении команды вывод в строке 12 будет напечатано 2.
Ответ: 2

1     алг
2     нач
3       цел a, b, t, R, M
4       a:= -20; b:= 20
      M:= a; R:= F(a)
6       нц для t от a до b
7         если F(t)< R
8           то
9             M:= t; R:= F(t)
10         все
11       кц
12       вывод M
13     кон
14
15     алг цел F(цел x)
16     нач
17       знач := 4*(x-1)*(x-3)
18     кон

Рис.2.

2.3. Какие знания/умения/навыки нужны ученику, чтобы решить эту задачу

Ученик должен уметь:

1)    распознавать записанные на языке программирования стандартные алгоритмы обработки данных (в данном задании – это алгоритм поиска минимального элемента в наборе чисел);

2)    распознавать вспомогательный алгоритм и понимать, что он делает;

3)    разобравшись в отдельных элементах программы, понять, что делает программа в целом.

Чтобы овладеть этими умениями необходим опыт практической работы в той или иной среде программирования.

2.4. Рекомендации для учителей: как разбирать задачу с учениками

Эти рекомендации – не догма, а попытка сделать выводы из собственного опыта. Ждем комментариев и Ваших рекомендаций.

Придумывайте свои подходы, применяйте их и сообщайте нам.

А. Относительно сильные ученики, имеющие достаточный опыт работы в среде программирования.

Эта задача не должна представлять для них трудностей, особенно, если Вы проведете разбор решения, например, по схеме, приведенной в п.2.2. Может понадобиться небольшой тренинг, чтобы «набить руку».

В качестве тренинга по распознаванию стандартных алгоритмов можно, например, давать задачи, в которых приведен алгоритм и 4 варианта описания того, что он делает. Пример набора вариантов ответов (не стоит использовать именно эти тексты, они могут оказаться излишне конспективными): 1) ищет минимальное значение, 2) ищет первую точку минимума, 2) ищет последнюю точку минимума, 4) ищет количество минимумов. Такие задачи перекликаются с заданием А12. См. примеры в материалах к заданию А12.

Полезно дать ученикам возможность попробовать решить задачу подобного типа, а потом проверить себя, выполнив программу в реальной среде программирования. Примеры подобных программ на школьном алгоритмическом языке, предназначенные для выполнения в среде КуМир, версия 1.8.0 и выше, находятся здесь. В архиве есть файл ReadMe.txt. Инсталлятор для среды КуМир для Windows можно скачать здесь. Чтобы получить КуМир для Linux. Нужно пойти сюда. .

Мы с удовольствием разместим на сайте материалы (или ссылки на них) для других языков программирования и программных сред. Присылайте!.

Б. Ученики, не имеющие достаточного опыта работы в среде программирования.

Тактика может быть примерно той же. Отличие в том, что вместо закрепления уже известного, придется изучить стандартные алгоритмы и, возможно, вспомогательные алгоритмы. Материалы для этого см. в  разделе «Темы» основного горизонтального меню.

Замечание о математике. 

2.5. Рекомендации для учеников: как решать подобные задачи

 

3. Другие задачи

Хорошая подборка тренировочных заданий на Паскале есть на сайте К.Ю. Полякова. А вот здесь находится архив программ на КуМире. В каждой из них требуется определить, что будет напечатано в результате выполнения программы. В архиве есть файл ReadMe.txt

 
 

4 комментария

  1. Т.С.:

    Пожалуйста, исправьте текст программы на Бейсике:
    a = -20: b = 20
    M = a: R = F(a)
    FOR t = a TO b
    IF F(t) < R THEN
    M = t
    R = F(t)
    END IF
    NEXT t
    PRINT M
    FUNCTION F (x)
    F = (x — 1) * (x — 3)
    END FUNCTION

  2. vikva:

    http://infoegehelp.ru/index.php?option=com_content&view=article&id=134&Itemid=97
    тут решение задачи B14 2012 с иллюстрациями

 
 

Ответить Т.С.

 




 
 

 
 
Яндекс.Метрика