БЛОК «АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ»

Данный блок содержит самый объемный и сложный материал курса информатики, знания и умения по которому представлены на всех трех уровнях сложности.

На уровне воспроизведения знаний проверяется фундаментальный теоретический материал, такой как:

- понятие алгоритма, его свойств, способов записи;

- основные алгоритмические конструкции;

- основные элементы программирования.

Материал на проверку сформированности умений применять свои знания в стандартной ситуации входит во все три части экзаменационной работы. По данному тематическому блоку это следующие умения:

- использовать стандартные алгоритмические конструкции при программировании;

- формально использовать алгоритмы, записанные на естественных и алгоритмических языках, в том числе на языках программирования.

Материал на проверку сформированности умений применять свои знания в новой ситуации входит во вторую и третью части работы. Это следующие сложные умения:

- анализировать текст программы с точки зрения соответствия записанного алгоритма поставленной задаче и изменять его в соответствии с заданием;

- реализовывать сложный алгоритм с использованием современных систем программирования.

Задания занимают следующие позиции в вариантах КИМ: А6, А7, А8, А20, В3, В6, С1-С4.

 

Проанализировав КИМ по информатике можно отметить, что знания и умения, связанные с использованием основных алгоритмических конструкций, выявлялись как заданием на исполнение и анализ отдельных алгоритмов, записанных в виде блок-схемы, на алгоритмическом языке или на языках программирования, так и заданиями на составление алгоритмов для конкретного исполнителя (задание с кратким ответом) и анализ дерева игры.

Приведем пример решения типичного задания на исполнение алгоритма, сформулированного на естественном языке.

Пример:

Цепочки символов (строки) создаются по следующему пра­ вилу.

Первая строка состоит из одного символа — цифры «1».

Каждая из последующих цепочек создается такими действия­ми: в очередную строку дважды записывается цепочка цифр из предыдущей строки (одна за другой, подряд), а в конец приписы­вается еще одно число — номер строки по порядку (на i -м шаге дописывается число « i »).

Вот первые 4 строки, созданные по этому правилу:

1)1 2)112    3)1121123 4)112112311211234

Какая цифра стоит в седьмой строке на 121-м месте (считая слева направо)?

Решение:

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

Получается, что длина строк составит:

1)   1 элемент в строке;

2)   1x2 + 1 = 3 элемента в строке;

3)   3x2 + 1 = 7;

4) 7x2 + 1 = 15;

5)  15x2+1 = 31;

6) 31x2 + 1=63;

7)  63x2 + 1 = 127 элементов в строке.

Требуется найти 121-й элемент в строке длиной в 127 симво­лов. Это означает, что нам нужен седьмой элемент с конца. По­скольку в конец строки на каждом шаге добавляется его номер (совпадающий с номером формируемой строки), то последние семь символов 7-й строки будут 1234567. Таким образом, седьмой символ с конца — единица.

Ответ: 1.

 

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

Важное замечание:

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

 

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

Пример:

Два игрока играют в следующую игру. Имеются три кучки камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество камней в какой-нибудь кучке, или добавить по два камня в каж­дую из трех куч. Предполагается, что у каждого игрока имеется неограниченный запас камней. Выигрывает тот игрок, после чьего хода в какой-нибудь кучке становится  не менее 15 камней или во всех трех кучках суммарно ста­новится  не менее 25 камней. Игроки ходят по очереди. Выясните, кто выигрывает при пра­вильной игре, — первый или второй игрок.

Решение (развернутый ответ):

Для решения задачи составим таблицу (дерево развития игры при разных продолжениях).

В колонке 0 показано начальное со­стояние игры (вершина дерева игры), в колонке 1 показаны 4 возможных состояния игры после 1-го хода 1-го игрока, в колонке 2 показано 16 возможных состояний игры после 1-го хода 2-го игрока, далее дерево игры не ведется, а проводится анализ уже рассчитанных состояний игры.

Если 1-й игрок сделает свой первый ход 2,3,4 —>4,3,4, то 2-й игрок при правильной игре сделает ход 4,3,4 —>4,6,4, что при­водит к проигрышу 1-го игрока (т.к. из состояния (4,6,4) 1-й игрок может своим ходом перевести игру в одно из четырех со­стояний — (8,6,4), (4,12,4), (4,6,8), (6,8,6), и для любого из этих состояний найдется ход 2-го игрока, дающий ему выигрыш, на­пример, по критерию S>25 ).

Если 1-й игрок сделает свой первый ход 2,3,4 —>2,6,4, то 2-й игрок при правильной игре сделает ход 2,6,4 —> 4,6,4, что, как мы только что видели, приводит к выигрышу 2-го игрока.

Если 1-й игрок сделает свой первый ход 2,3,4 —>2,3,8, то его проигрыш очевиден, так как 2-й игрок, как указано в таблице, добьется выигрывающего состояния игры 2,3,16.

Наконец, если 1-й игрок сделает свой первый ход 2,3,4 —> 4,5,6, то он выигрывает игру, т.к. на любой из четырех возмож­ных ответов 2-го игрока (см. табл.) есть выигрывающий ход 1-го игрока.

Таким образом, при правильной игре выигрывает 1-й игрок (при этом его первый ход должен быть 2,3,4 —>4,5,6)

 

Начальное состояние	1-й ход первого игрока	1-й ход второго игрока	2-й ход первого игрока
2,3,4	4,3,4	4,6,4 Приводит к выигрышу второго игрока при любом втором ходе первого игрока
	2,6,4	4,6,4 Приводит к выигрышу второго игрока при любом втором ходе первого игрока
	2,3,8	2,3,16 Выигрыш второго игрока
	4,5,6	8,5,6	16,5,6 Выигрыш первого игрока
		4,10,6	4,20,6 Выигрыш первого игрока
		4,5,12	4,5,24 Выигрыш первого игрока
		6,7,8	6,7,16 Выигрыш первого игрока

 

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

Пример:

Исполнитель Черепашка перемещается на экране компьюте­ра, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:

Вперед n, вызывающая передвижение Черепашки на п шагов в направлении движения.

Направо т, вызывающая изменение направления движения на т градусов по часовой стрелке. 0  т  180.

(Вместо п и т должны стоять целые числа).

Запись:

Повтори 5 [Команда1 Команда2] означает, что последова­тельность команд в квадратных скобках повторится 5 раз.

Какое число необходимо записать вместо п в следующем ал­горитме:

Повтори 6 [Вперед 40 Направо п], чтобы на экране появился правильный пятиугольник.

 

Решение:

Сумма внутренних углов правильного пятиугольника вы­числяется по формуле (р-2)х180/р, где р =5. Поэтому величина одного внутреннего угла будет равна (5 - 2) х 180/5 = 108°. А угол поворота Черепашки в вершине пятиугольника будет равен углу, смежному с внутренним углом, т.е. 180-108=72°.

Черепашка прочертит на экране 6 отрезков, но последний от­резок полностью совпадет с первым, так как после пятого выпол­нения цикла Черепашка полностью обернется вокруг своей оси (72x5 = 360°) и окажется в той же точке, что и изначально. Так что на экране появится правильный пятиугольник.

Ответ: 72.

 

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

Пример:

Определите значение переменной т после выполнения фраг­мента алгоритма:

 

 

 

Примечание: знаком :=обозначена операция присваивания.
1) 1               2) 2         3) 3         4) 33

Решение

Способ 1

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

 

N шага	Значе­ние т	Значе- ­ние п	т =п	т>п
0	81	48
1	81	48	81 = 48 — нет (выполняем тело цикла)
2	81	48		81>48 - да
3	33	48
4	33	48	33= 48 — нет (выполняем тело цикла)
5	33	48		33>48-нет
6	33	15
7	33	15	33=15 — нет (выполняем тело цикла)	i
8	33	15		33>15 - да
9	18	15	18=15 — нет (выполняем тело цикла)
10	18	15		18>15 - да
11	3	15
12	3	15	3 = 15 — нет (выполняем те­ло цикла)
13	3	15		3 > 15 - нет
14	3	12
15	3	12	3 = 12 — нет (выполняем те­ло цикла)
16	3	12		3>12 - нет
17	3	9
18	3	9	3 = 9 — нет (выполняем тело цикла)
19	3	9		3 > 9 - нет
20	3	6
21	3	6	3 = 6 — нет (выполняем тело цикла)
22	3	6		3 > 6 - нет
23	3	3
24	3	3	3 = 3 — да (выход из цикла и завершение алгоритма)

 

Ответ: 3.

 

 

Способ 2

Внимательно проанализировав блок-схему, можно сделать вывод, что она реализует известный алгоритм Евклида нахож­дения наибольшего общего делителя двух чисел, который для 81 и 48 равен трем. (81 = 3⁴, 48 =3x16.)

Ответ: 3.

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

Пример:

Определите значение целочисленных переменных а и b после выполнения фрагмента программы:

 

Бейсик	Паскаль	Алгоритмический
а=2468	а:=2468;	а:=2468
b= (a MOD 1000)*10	b:=(a mod 1000)ПО;	b:=mod(a, 1000)*10
а=а\1000 + 6	а:=а div 1000 + 6;	a:=div(a, 1000) +b
'\ и MOD — опера-	{div и mod — опера-	|div и mod — функ-
ции, вычисляющие	ции, вычисляющие	ции, вычисляющие
результат деления	результат деления	результат деления
нацело первого ар-	нацело первого ар-	нацело первого ар-
гумента на второй и	гумента на второй и	гумента на второй и
остаток от деления	остаток от деления	остаток от деления
соответственно	соответственно}	соответственно

1)a =22, b=20

2)a =4682, b=4680

3)a =8246, b=246

4)a =470, b=468

Решение:

Составим таблицу переменных:

N шага	Значение a	Значение b
0	2468	не определено
1	2468	468*10=4680
2	2 + 4680=4682	4680

Ответ: 2.

 

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

Пример:

В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные а, b , с имеют тип «строка», а переменные i , k — тип «целое». Используются следующие функ­ции:

Длина (а) — возвращает количество символов в строке а. (Тип «целое».)

Извлечь (а, i) — возвращает i-тый (слева) символ в строке а. (Тип «строка».)

Склеить (а, b)— возвращает строку, в которой записаны сна­чала все символы строки а, а затем все символы строки b . (Тип «строка».)

Значения строк записываются в одинарных кавычках.

(На­пример, а :='дом'.)

 

Фрагмент алгоритма:

i := Длина (а)

k :=1

b:= ‘П’

пока i>0

нц

с := Извлечь ( a , i )

b := Склеить (b, с )

i:=i - k

кц

 

Какое значение будет у переменной b после выполнения выше­приведенного фрагмента алгоритма, если значение переменной а было 'РОЗА'?

1) 'ПАЗ'          2) 'ПАЗОР'     3) 'ПОЗА'       4) 'ПРОЗА'

 

Решение:

В данном случае для решения задачи достаточно знания обычного алгоритмического языка и описания функций, при­веденного в условии. Выполним программу по шагам, занося значения переменных в таблицу:

 

Выполняемый оператор	Значение а	Значение b	Значение с	Значение i	Значение k
	‘РОЗА’	не определено	не определено	не определено	не определено
i := Длина (а)	‘РОЗА’	не определено	не определено	4	не определено
k:=1	‘РОЗА’	не определено	не определено	4	1
b:=’П’	‘РОЗА’	‘П’	не определено	4	1
с := Извлечь (а, i)	‘РОЗА’	‘П’	‘А’	4	1
b := Склеить ( b, с)	‘РОЗА’	‘ПА’	‘А’	4	1
i:=i — k	‘РОЗА’	‘ПА’	‘А’	3	1
с := Извлечь (а , i)	‘РОЗА’	‘ПА’	‘З’	3	1
b := Склеить ( b, с)	‘РОЗА’	‘ПАЗ’	‘З’	3	1
i:=i - k	‘РОЗА’	‘ПАЗ’	‘З’	2	1
с := Извлечь (а , i)	‘РОЗА’	‘ПАЗ’	‘О’	2	1
b := Склеить ( b, с)	‘РОЗА’	‘ПАЗО’	‘О’	2	1
i:= i - k	‘РОЗА’	‘ПАЗО’	‘О’	1	1
с := Извлечь (а, i)	‘РОЗА’	‘ПАЗО’	‘Р’	1	1
b := Склеить ( b, с)	‘РОЗА’	‘ПАЗОР’	‘Р’	1	1
i:= i - k	‘РОЗА’	‘ПАЗОР’	‘Р’	0	1

Ответ: 2.

 

К теме «Алгоритмизация и программирование» относятся также задания на проверку умения написать корот­кую (10—15 строк) простую программу обработки массива на языке программирования или записать алгоритм на естествен­ном языке.

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

Для решения этой группы заданий полезно усвоить следующие элементарные алгоритмы:

1) Поиск минимального и максимального элементов в массиве с определением их номеров.

2) Поиск в массиве элемента, удовлетворяющего заданному условию с определением его номера.

3) Подсчет числа элементов массива, удовлетворяющих за данному условию:

4) Вычисление суммы элементов числового массива.

5) Вычисление суммы элементов числового массива, удовлетворяющих заданному условию.

6) Поиск в массиве подпоследовательности убывающих (возрастающих) элементов.

После того как алгоритм начерно написан, рекомендуется его протестировать на небольших (4—5 элементов) массивах исходных данных. Желательно проверить корректность работы алгоритма в следующих ситуациях:

1)элементы массива различны и не упорядочены;

2)элементы массива различны и упорядочены по возрастанию;

3)элементы массива различны и упорядочены по убыванию;

4)элементы массива равны между собой;

5)иные «экстремальные» случаи.

 

БЛОК «ОСНОВЫ ЛОГИКИ»

 

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

Материалы на проверку сформированности умений применять свои знания в стандартной ситуации входит в первый две части экзаменационной работы. Это умения:

- составлять и преобразовывать логические выражения;

Формировать для логической функции таблицу истинности и логическую схему.

Материал на проверку сформированности умений применять свои знания в новой ситуации входит во вторую часть работы. Это умение преобразовывать сложные логические высказывания.

Задания занимают следующие позиции в варианте: А9-А11, В2, В4.

 

Для успешного выполнения заданий ЕГЭ по основам логики, учащиеся должны твердо усвоить символику и определения (таблицы истинности) трех основных логических операций (инверсия, конъюнкция, дизъюнкция), а также импликации. Кроме того, необходимо знать и уметь применять при работе с логическими выражениями основные законы логики.

Полезно знать также формулу для выражения импликации через отрицание и логическое сложение:

 

Кроме того, желательно знать следующие свойства конъюнк­ции, дизъюнкции и импликации:

 

Пример:

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X , Y , Z .

Дан фрагмент таблицы истинности выражения F :

 

X	Y	Z	F
0	1	0	0
0	1	1	1
1	1	0	0

Какое выражение соответствует F?

1)

2)

3)

4)

Решение

Способ 1

Последовательно подставим первую строку таблицы истин­ности во все варианты ответов:

l) , а по условию F для этого набора значений равно 0. Первый ответ не подходит.

2) , по условию F = 0. Второй ответ пока под­ходит.

3) , по условию F =0. Третий ответ пока под­ходит.

4) , по условию F = 0. Четвертый ответ пока под­ходит.

Отбросив первый вариант ответа, подставим теперь вторую строку во все оставшиеся:

2) , по условию F = 1. Второй ответ отпадает.

3) , по условию F =1. Третий ответ пока под­ходит.

4) , по условию F = 1. Четвертый ответ пока под­ходит.

Подставим теперь третью строку в оставшиеся два варианта ответов:

3) , по условию F = 0. Третий ответ подходит для всех строк.

4) , по условию F = 0. Четвертый ответ не под­ходит.

Ответ: 3.

 

Способ 2

Составим фрагмент таблицы истинности всех перечисленных в ответах логических выражений для различных наборов переменных X, Y, Z:

X	Y	Z	F
0	0	0	1	0	1	1	0
0	0	1	0	1	1	0	1
0	1	0	1	0	1	1	1

Заметим, что значения истинности одинаковы для логических выражений F и  при любых значениях аргументов X, Y, Z из данного фрагмента, следовательно, эти логические выражения равносильны. Ответ № 3.