Заготовки задач для проведения ЕГЭ по информатике
материал для подготовки к егэ (гиа) по информатике и икт по теме

Заготовки задач для проведения ЕГЭ по информатике

(раздел "теоретические основы информатики и программирование")

Задача 1. На первом месте в цепочке стоит одна из бусин  А, Б, В. На втором – одна из бусин Б, В, Г.  На третьем месте – одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте. Выписать все такие цепочки.

ОТВЕТ

АБВ  АБГ  АВГ  АГВ  ББА  ББВ  ББГ  БВА  БВГ  БГА  БГВ  ВБА  ВБГ  ВВА  ВВГ  ВГА

Задача 2. Для составления цепочек разрешается использовать 5 бусинок, помеченных буквами  А Б Е Ж И. Каждая цепочка должна состоять из k бусинок, где k∈ {3,4,5} - зависит от номера Варианта; при этом должны соблюдаться правила:

1) любая цепочка начинается буквой А

2) после гласной буквы не может снова идти гласная, а после согласной - согласная.

3) буквы в цепочке не должны повторяться

Задание:  Для заданного k выписать все допустимые цепочки.

Ответ (при k=3)     АБЕ    АБИ     АЖЕ     АЖИ

           (при k=4)     АБЕЖ    АБИЖ     АЖЕБ     АЖИБ

           (при k=5)     АБЕЖИ    АБИЖЕ     АЖЕБИ     АЖИБЕ

Задача 3. Для составления цепочек разрешается использовать 6 бусинок, помеченных буквами  А Б Е Ж И К. Каждая цепочка должна состоять из всех 6 бусинок, при этом должны соблюдаться правила:

1) любая цепочка начинается гласной буквой

2) после гласной буквы не может снова идти гласная, а после согласной - согласная.

3) буквы в цепочке не должны повторяться

Задание: Сколько всего существует таких цепочек?

Ответ: всего существует 36 таких цепочек

Задача 4. Имеется (неизвестное нам) слово из 8 букв. Оно подвергается шифрованию по следующим правилам:

1. На 1-м этапе буквы попарно меняются местами по следующей схеме:  

1↔3  2↔5  4↔7  6↔8 (т.е. меняются местами 1 и 3 буквы, 2 и 5 и т.д.)

2. На 2-м этапе для получившейся строки из 8 букв смотрим: если крайние буквы различны по гласности (одна из них - гласная, другая - согласная), то результат шифрования является окончательным, в противном случае получившуюся на предыдущем этапе строку преобразуем по схеме 1→2→3→4→5→6→7→8→1 (выполняем циклический сдвиг вправо, т.е. первая буква ставится на место второй, вторая - на место третьей, ... последняя - на место первой), после чего  снова выполняем этапы 1 - 2. Таким образом, для некоторых исходных слов этапы 1 - 2 могут повторяться многократно, пока на этапе 1 не получится окончательный результат шифрования.

Задание: В результате шифрования получена строка БИЛКРАКО.

Каким было исходное слово?

ОТВЕТ:

Задача 5. (упрощенный вариант задачи # 4)

Имеется исходный набор 8-буквенных слов:

КАРАНДАШ   МАРЦИПАН   МАРГАРИН   МАРТЫШКА   ТРЯПОЧКА

Выбрать из этого набора 8-буквенных слов два слова (по своему усмотрению) и зашифровать их по правилам, указанным в задаче # 4

Ответы: КАРАНДАШ  - надшрака   МАРЦИПАН - рмцапниа
МАРГАРИН - рмгарнаи   МАРТЫШКА - рамтшыка  ТРЯПОЧКА - яоткрапч
(т.е. быстрее всего шифруются "ТРЯПОЧКА" и "КАРАНДАШ", дольше всего -
"МАРТЫШКА").

Задача 6. В начальный момент в строке записана цифра 0 (ноль).

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

Для удобства в скобках пишется номер строки (начиная с 0). Ниже показаны первые строки, сформированные по описанному правилу:

(0)        0

(1)        001

(2)        0010012

(3)        001001200100123

..........................................

Задания:

1.  На какие 10 цифр заканчивается последняя строка?
2.  Сколько раз в последней строке встречается цифра 5?
3.  Какова длина последней строки (т.е. сколько всего в ней цифр)?

4. Какая цифра стоит в последней строке на 1012-м месте?

5. Сколько всего цифр в строках  (0)  -  (9)?

Ответы: 1. Последняя строка заканчивается цифрами 0123456789.

2. В последней строке цифра 5 встретится 16 раз.

3. В последней строке 1023 цифры.

4. В последней строке на 1012-м месте стоит цифра 1.

5. Всего в строках  (0) - (9) 2036 цифр

Задача 7. Выполнить нижеприведенную программу при х = 3, у = 7, z = 11:

начало

1) x := y+z

2) z := x+z

3) y := y+x

4) x := y-x

5) x := x*z

6) z := y+z

конец

Чему равны значения переменных  х, y, z  после выполнения программы?

Ответ: x = 203, y=25, z=54

Задача 8. Даны три кучи камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество  камней в какой-нибудь куче, или добавить по два камня в каждую из всех трех куч.

Выигрывает тот, после чьего хода в какой-нибудь куче становится ≥15 камней или во всех трех кучах суммарно становится ≥25 камней.

Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре - первый или второй игрок.

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

Задача 9. Имеется шахматная доска стандартного размера 8х8, со стандартным обозначением клеток (a1 - нижняя левая,.... h8 - верхняя правая).

Из некоторой начальной клетки Х (Х∈{c4, c5, d3, e3}) нужно проложить маршрут в клетку а1, соблюдая следующее правило:
каждый ход делается либо на одну клетку влево, либо на одну клетку вниз.

Перечислить все такие маршруты, ведущие из начальной клетки Х в клетку а1 (каждый маршрут должен начинаться клеткой Х, далее через запятую указываются промежуточные клетки маршрута, заканчивается маршрут клеткой а1)

ОТВЕТ(для примера взят Х=c5): c5,b5,a5,a4,a3,a2,a1; c5,b5,b4,a4,a3,a2,a1;
c5,b5,b4,b3,a3,a2,a1; c5,b5,b4,b3,b2,a2,a1; c5,b5,b4,b3,b2,b1,a1; c5,c4,b4,a4,a3,a2,a1;
c5,c4,b4,b3,a3,a2,a1; c5,c4,b4,b3,b2,a2,a1; c5,c4,b4,b3,b2,b1,a1; c5,c4,c3,b3,a3,a2,a1;
c5,c4,c3,b3,b2,a2,a1; c5,c4,c3,b3,b2,b1,a1; c5,c4,c3,c2,b2,a2,a1; c5,c4,c3,c2,b2,b1,a1;
c5,c4,c3,c2,c1,b1,a1  (всего 15 маршрутов).

Задача 10. (по мотивам задачи #9) Имеется шахматная доска стандартного размера 8х8, со стандартным обозначением клеток (a1 - нижняя левая,.... h8 - верхняя правая).

Из некоторой начальной клетки Х (Х∈.......) нужно проложить маршрут в клетку а1, соблюдая следующее правило:
каждый ход делается либо на одну клетку влево, либо на одну клетку вниз, либо "вниз-влево". Например, из клетки d3 допустимы ходы на клетки c3,d2,c2.

Для сокращения записи принята кодировка:

Л - ход ВЛЕВО

Д - ход по диагонали "ВНИЗ-ВЛЕВО"

Н - ход ВНИЗ

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

Задание: Перечислить все допустимые маршруты, ведущие из начальной клетки Х в клетку а1.

ОТВЕТ : (для примера взято Х=с3).

Задача 11. (продолжение серии задач о путях на шахматной доске).

Имеется шахматная доска, на которой обозначен участок "запретных" клеток (куда заходить нельзя) - он обозначен закраской.

Начальная клетка - поле Х.

Вариант А. Выяснить, сколько всего маршрутов существует из Х в клетку а1, если ходить разрешается по правилам, изложенным в задаче 9 (каждый ход делается либо на одну клетку влево, либо на одну клетку вниз)

Замечание: перечислять все маршруты не нужно, требуется только указать их количество.

Решение (ОТВЕТ):

(ответы записаны в соответствующих клетках шахматного поля)

Вариант Б. Выяснить, сколько всего маршрутов существует из Х в клетку а1, если ходить разрешается по правилам, изложенным в задаче 10 (каждый ход делается либо на одну клетку влево, либо на одну клетку вниз, либо "вниз-влево")

Замечание: перечислять все маршруты не нужно, требуется только указать их количество.

Решение (ОТВЕТ):

(ответы записаны в соответствующих клетках шахматного поля, кроме двух верхних клеток, где ответ > 1000)

Задача 12. (продолжение серии задач о путях на шахматной доске)

Имеется шахматная доска стандартного размера 8х8, со стандартным обозначением клеток (a1 - нижняя левая,.... h8 - верхняя правая).

Выяснить, сколько всего маршрутов существует из клетки Х через промежуточную клетку Y в клетку а1, если ходить разрешается по правилам, изложенным в задаче 9 (каждый ход делается либо на одну клетку влево, либо на одну клетку вниз). Предполагается, что указанные в задаче маршруты существуют.

Замечание: перечислять все маршруты не нужно, требуется только указать их количество.

ОТВЕТ (ПРИМЕР: пусть X=f6, Y=c4. Тогда общее количество искомых путей равно 100.)

Задача 13. (игра на шахматной доске)

Двое играют в игру, делая по очереди ходы на шахматной доске, по правилам, изложенным в задаче 9 (каждый ход делается либо на одну клетку влево, либо на одну клетку вниз). Начальная клетка - клетка Х. Выигрывает тот, кто приходит в клетку а1.

Выяснить, кто должен выиграть при правильной игре (в зависимости от того, какая начальная клетка Х задана).

Ответ: цифрой 1 обозначены поля, являющие "выигрышными" для 1-го игрока (если игра начинается с одного из этих полей, то игрок 1 выигрывает). Соответственно, остальные поля - "проиигрышные" для 1-го игрока.

Задача 14. Числа а=123 и b=132 перевели в двоичную запись, получили соответственно двоичные числа α и β. Эти двоичные числа сложили по правилам сложения в двоичной системе. Быстро (желательно - в уме) определить, какое двоичное число мы получим в результате сложения.

ОТВЕТ: получим 11111111

Задача 15.

Нарисовать блок-схему (логическую схему) программы, предназначенной для решения следующей задачи: известно целое число х1=2, являющееся начальным для последовательности х1, х2, х3, ....; также известен закон, по которому каждое следующее число в последовательности вычисляется через предыдущее: xi = 3*(xi-1) - 2, при i>1. (или xi := 3*(xi-1) - 2)

В программе требуется вычислить 12-й член последовательности { xi }  и сумму S перых 12 членов последовательности. Вывод полученных результатов (на экран или в файл) на блок-схеме можно обозначить в произвольном виде, например: Вывести "x12, S" (другой вариант - вывод результатов показывать не надо).

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

Задача 16. Известны целые числа x1,y1,x2,y2,x3,y3 - эти числа в прямоугольной системе координат задают вершины треугольника A (x1,y1), B(x2,y2), C(x3,y3). Нарисовать блок-схему программы, которая должна выяснить, лежит ли треугольник АВС строго внутри окружности радиуса 10 с центром в начале координат. Для ввода исходных чисел x1,y1,x2,y2,x3,y3 в начале блок-схемы предусмотреть блок "Ввод x1,y1,x2,y2,x3,y3". В конце блок-схемы предусмотреть блоки, выдающие надписи "Тр-к лежит внутри окружности"  или
"Тр-к не лежит внутри окружности", в зависимости от проведенных проверок.

Ответ: см. то же, что к задаче 15

Задача 17. (облегченный вариант одной из задач, связанных с шахматным полем). Имеется шахматная доска стандартного размера 8х8, со стандартным обозначением клеток (a1 - нижняя левая,.... h8 - верхняя правая). На ней можно прокладывать маршруты из одной клетки в другую, соблюдая следующее правило: каждый ход делается либо на одну клетку влево, либо на одну клетку вниз (для того, чтобы такие маршруты существовали, нужно, чтобы начальная клекта была раположена "выше-правее", чем конечная).

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

Задание: определить, сколько маршрутов заданного типа существует из клекти Х в клетку Y  (например, X=g6, Y=c3).

Решение и ОТВЕТ: количество маршрутов из g6 в c3 - такое же, как из e4 в a1, т.е. 35 (ответ интуитивно совершенно очевиден, но для дополнительного обоснования можно сказать следующее: маршрутов будет столько же, сколько программ для РОБОТА с 3 командами ВНИЗ и 4 командами ВЛЕВО, а их 35).

Задача 18. Тройка натуральных чисел a,b,c называется пифагоровой, если выполнено равенство a2+b2=c2 (как в прямоугольнои треугольнике с катетами a,b). Эти тройки можно формировать через параметры u,v по схеме:

a=u2-v2;  b=2uv;  c=u2+v2 , где u,v - также натуральные числа, причем u>v
(проверить выполнение равенства a2+b2=c2 можно одной строчкой алгебраических выкладок). Заданы следующие 5 пар значений u,v для формирования пифагоровых троек a,b,c:

u=2,v=1;  u=3,v=2;  u=4,v=3;  u=5,v=4;  u=6,v=5;

(в каждой паре u,v оба числа каждый раз увеличиваются на единицу).

Нарисовать блок-схему программы, которая должна сформировать соответствующие пифагоровы тройки a,b,c. В блок-схеме предусмотреть блок, выдаающий тройки a,b,c. (На блок-схеме в этом блоке поставить "Выдать a,b,c ")

Ответ: см. то же, что к задаче 15

Задача 19. Для составления цепочек длины k разрешается использовать две буквы: А и Б, причем никакая буква не должна стоять в цепочке подряд три или более раз.

 Перечислить все цепочки длины k=5, удовлетворяющие указанным выше правилам.

ОТВЕТ:

Задача 20. (парная к задаче 19)

 Для составления цепочек длины k разрешается использовать две буквы А и Б, причем одна из букв (А или Б) должна стоять в цепочке подряд три или более раз.

Сколько всего существует таких цепочек длины k=5?

 (Перечислять все такие цепочки не надо - только определить их количество).

Ответ: 16

ЗАДАЧА 21. 

Пошаговой (алгоритмической) записью вычисления выражения называется такая запись, при которой каждая выполняемая операция записывается отдельно (на новой строчке), результат каждой операции заносится в отдельную переменную (ячейку) - например y1, y2, y3, .... , и только окончательный результат записывается в переменную, которая стоит в левой части исходной записи.

ПРИМЕР.  

y :=(a-b)/(c+d) в пошаговой записи будет иметь вид:

1) y1 :=a-b

2) y2 :=c+d

3) y := y1/y2

При этом должно выполняться правило: если на каком-то шаге в принципе можно выполнить несколько разных операций, то следует выбирать "крайнюю левую" из возможных операций (следуя этому правилу, мы в приведенном примере поставили первой операцией вычисление a-b, хотя в принципе можно было бы начать с вычисления c+d).

Задание. Записать в пошаговой записи y :=(a+b)*(c-d)/(e+f)

ОТВЕТ:

1) y1:=a+b

2) y2:=c-d

3) y3:=y1*y2

4) y4:=e+f

5) y:=y3/y4

ЗАДАЧА 22. 

 Обычно знак операции ставится между операндами (числами или выражениями, над которыми производится операция) - это называется инфиксной записью операции. Существует другой, удобный для ЭВМ, способ записи - польская инверсивная запись (сокращенно - ПОЛИЗ), которая не требует скобок при записи любых выражений. При записи в ПОЛИЗ сначала указываются операнды (причем важно, какой операнд первый, какой - второй), а после указывается знак операции.

Например, вместо y:=c-d мы в ПОЛИЗ запишем y:=c d -

При записи в ПОЛИЗ могут стоять несколько знаков операций подряд - это значит, что при вычислении предшествующей части записи в ПОЛИЗ накопятся операнды для выполнения этих операций.

Пример: пусть запись в ПОЛИЗ имеет вид

y:= a b + c d - * e f + /

Перевести ее в пошаговую запись и в запись в обычном виде.

Продвигаясь слева направо, находим первую выполняемую операцию

 a b +

записываем ее в пошаговом виде

1) y1:=a+b, преобразуя ПОЛИЗ к вид y:= y1 c d - * e f + /

  Далее находим первую слева выполняемую операцию c d - , получаем

2) y2:=c-d, ПОЛИЗ получает вид y:= y1 y2 * e f + /

Далее действуя аналогично, получаем

3) y3:=y1*y2, ПОЛИЗ получает вид y:= y3 e f + /

Далее получаем

4) y4:=e+f, ПОЛИЗ получает вид y:= y3 y4 /

И окончательно

5) y:=y3/y4

Переводя пошаговую запись в обычную, мы видим, что исходная запись в ПОЛИЗ имеет запись в обычном виде y :=(a+b)*(c-d)/(e+f)

(но при записи в ПОЛИЗ не требует скобок !)

Задание. Записать в ПОЛИЗ   y :=(a-b+k)*(c-f)/(e+f)

Рекомендация: записать сначала вычисления в пошаговой записи, чтобы потом можно было проверить, что запись в ПОЛИЗ выполнена правильно.

ОТВЕТ:

 y :=a b - k + c f - * e f + /

ЗАДАЧА 23. 

Решить уравнение

c / (2 + a / (b+x)) = 5

относительно x; записать ответ в обычном виде и в пошаговой записи (для записи промежуточных рез-тов рекомендуется использовать y1, y2, ....).

ОТВЕТ (в одной из возможных форм записи): x= 5*a* (1 / (c -10) - b / (5*a))

ЗАДАЧА 24.

Некоторый Исполнитель-Робот находится в начальный момент в левом нижнем углу стандартной шахматной доски (размером 8х8).

Робот может выполнять команды ВПРАВО, ВЛЕВО, ВВЕРХ, ВНИЗ, сдвигаясь по соответствующей команде на 1 клетку в заданном направлении. ПРОГРАММА - это набор последовательных команд, причем считается, что каждая программа написана корректно, т.е. не выводит Робота за пределы доски.

Ниже представлена программа из 20 команд, в соответствии с которой Робот, начиная движение из клетки а1, проделал замкнутый маршрут, т.е. после исполнения 20-й команды снова оказался  в левом нижнем углу. К сожалению, некоторые команды случайно стерлись (команды 7,8,18,19), но зато известно, что всего команд ВПРАВО было 5, команд ВВЕРХ - тоже 5. Также известно, что ни одну из промежуточных клеток пути Робот не посещал дважды.

Задание.Требуется восстановить стертые команды так, чтобы путь Робота по-прежнему заканчивался в левом нижнем углу.

Примечание: решение данной задачи - неоднозначно, т.е. можно несколькими способами заполнить строчки  7,8.18,19, добиваясь поставленной цели; в качестве решения достаточно указать один из возможных вариантов.

ОТВЕТ (один из возможных вариантов):

7. ВВЕРХ        8. ВЛЕВО                 18. ВНИЗ        19. ВЛЕВО

ЗАДАЧА 25.

Дана последовательность, состоящая из смотрящих влево стрелок (левых стрелок)  и смотрящих вправо стрелок (правых стрелок). Нужно составить программу, состоящую из 3-х типов команд:

СЖАТЬ (по этой команде последовательность подряд идущих стрелок, смотрящих в одну и ту же сторону, заменяется одной стрелкой, смотрящей в ту же сторону)

УБРАТЬ (по этой команде все пары стрелок, глядящих друг на друга, удаляются)

ИНВЕРТИРОВАТЬ (по этой команде все стрелки заменяются на противоположные,т.е. левые стрелки - на правые и наоборот).

Цель программы - уничтожить все стрелки.

ПРИМЕР. Если к строке

А = { ← →  ← ← ← ← → →  ← → → ← ← }

применить команду СЖАТЬ, то получим строку

А1 = { ← →  ← →  ←  → ← }

Если к строке А применить команду УБРАТЬ, то получим строку

А2 = { ← ← ← ← → → ← }

Если к строке А применить команду ИНВЕРТИРОВАТЬ, то получим строку

А3 = { → ← → → → →  ← ← → ← ← → → }

Задание (а).  Дана строка

B = { ← ← →  ← ← ← ← → →  ← → → ← ←→  }

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

Возможный ОТВЕТ:

1. СЖАТЬ    (  ← →  ← →   ← →  ← → )

2, УБРАТЬ   (  ← → )

3. ИНВЕРТИРОВАТЬ  (→ ← )

4. УБРАТЬ        ( )

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

Возможный ОТВЕТ: все стрелки смотрят в одну сторону.

ЗАДАЧА 26.

Задан массив, состоящий из 10 чисел а1, а2, .... а10, расположенных в ячйках с соответствующими номерами:

(номера ячеек подписаны в нижней строчке)

Имеется команда УМЕНЬШИТЬ ЯЧЕЙКИ (k1,k2),

где в скобках указаны номера ячеек, содержимое которых изменяется по следующему правилу: большее из двух чисел а[k1], а[k2] заменяется на абсолютную величину их разности, а меньшее - заменяется нулем (если числа равны, то каждое из них заменяется нулем).

Например, если а3=8, а5=6, то после применения команы

УМЕНЬШИТЬ ЯЧЕЙКИ (3,5) мы получим а3=2, а5=0.

Задание (а). Дан массив

Требуется написать последовательность команд

УМЕНЬШИТЬ ЯЧЕЙКИ (k1,k2), обнуляющую весь массив длины 10.

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

Задание (б). Привести пример массива из пяти чисел, для которого невозможно обнуление массива с помощью последовательности команд УМЕНЬШИТЬ ЯЧЕЙКИ. Ответ (невозможность обнуления) обосновать.

Ответ (к пункту б): Массив состоит из чисел

1,2,3,4,5 - сумма всех чисел нечетна, а в процессе применения операции УМЕНЬШИТЬ ЯЧЕЙКИ мы всегда сохраняем чеиность суммы всех элементов массива, поэтому нулевой результат мы получить не можем.

Задача 27. Имеется слово "абракадабра" из 11 букв. Разрешается в этом слове вычеркнуть 8 букв, чтобы оставшиеся 3 буквы составили слово "аба" или слово "ада". Перечислить все такие 3-буквенные слова "аба" или "ада", указав, из каких (по номеру) букв исходного слова они образованы.

Например: аба - 1,2,4; .................................. ада - 1,7,8

ОТВЕТ: аба - 1,2,4; 1,2,6; 1,2,8; 1,2,11; 4,9,11; 6,9,11; 8,9,11.

                  ада - 1,7,8; 1,7,11; 4,7,8; 4,7,11; 6,7,8; 6,7,11.

Задача 28. Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух битов, для некоторых - из трех). Эти  коды представлены в таблице:

Определить, какой набор букв закодирован двоичной строкой

1100000100110    

ОТВЕТ: badde.

Задача 29. (усложненный вариант задачи 28).

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух битов, для некоторых - из трех). Эти  коды представлены в таблице:

Определить, какой набор букв может быть закодирован двоичной строкой

01111101100

(вариантов ответов может быть несколько - в этом случае выдать все возможные варианты).

ОТВЕТ: возможные варианты раскодировки - bare, baby

Задача 30.

В понедельник в одном из классов должно быть проведено 4 урока - по математике, физике, информатике и биологии. Учителя высказали свои пожелания для составления расписания. Учитель математики хочет иметь первый или второй урок, учитель физики - второй или третий урок, учитель информатики - первый или четвертый, учитель биологии - третий или четвертый.

Какие при этих условиях могут быть варианты расписания? (перечислить все возможные варианты).

Примем обозначения: М - математика, Ф - физика, И - информатика Б - биология. ОТВЕТ:     МФБИ   и    ИМФБ.

Задача 31 (усложнение задачи 30, применение метода декомпозиции).

В понедельник в одном из классов должно быть проведено 7 уроков - по математике, физике, информатике, биологии, английскому, географии и химии. Учителя высказали свои пожелания для составления расписания. Учитель математики хочет иметь первый или второй урок, учитель физики - второй или третий урок, учитель информатики - первый или четвертый, учитель биологии - третий или четвертый, учитель географии - пятый или шестой, учитель английского - шестой или седьмой, учитель химии - пятый или седьмой.

Какие при этих условиях могут быть варианты расписания? (перечислить все возможные варианты).

Примем обозначения: М - математика, Ф - физика, И - информатика Б - биология, Г - география, А - английский, Х - химия. ОТВЕТ:

МФБИГАХ,  МФБИХГА,  ИМФБГАХ, ИМФБХГА

Задача 32. Вычислить значения следующих булевских фунций от 4-х аргументов х1, х2, х3, х4, если х1=1, х2=0, х3=1, х4=0

("1" трактуется как true, "0" - как false)

a)   f(х1, х2, х3, х4) = х1∨х2

b)   f(х1, х2, х3, х4) = (х1∨х2) & (х3 & х4)

c)   f(х1, х2, х3, х4) =(х1&х2& х3  ∨ х1&х2& х3  ∨ х1&х2& х3) ∨ x4

     и т.п.

Ответы:  a) f=1    b) f=1    c) f=1

Задача 33. Дана булевская фунция от трех аргументов a,b,c:

f(a,b,c) = (a&b  ∨ b&c) ∨ ¬(a&b  ∨ b&c ∨ a&c),

где знак ¬ обозначает отрицание выражения, стоящего в скобках.

Выяснить, может ли эта функция принимать значение 0 (false) при каких-либо значениях своих аргументов?

ОТВЕТ: нет.

Задача 34. Дана булевская фунция от трех аргументов a,b,c:

f(a,b,c) = (a&b  ∨ b&c) & ¬(a&b  ∨ b&c ∨ a&c),

где знак ¬ обозначает отрицание выражения, стоящего в скобках.

Выяснить, может ли эта функция принимать значение 1 (true) при каких-либо значениях своих аргументов?

ОТВЕТ: нет.

Задача 35. Из точки А нужно построить лесенку из трех ступенек в точку В. Точка А имеет координаты (0,0) на координатной плоскости, а точка В - координаты (5,3). Каждая ступенька должна иметь одну единицу по высоте и целое количество единиц в длину. Одна из возможных лесенок показана ниже:

В

А

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

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

ОТВЕТ: 1,1,3;  1,2,2;  1,3,1;  2,1,2;  2,2,1;  3,1,1 - всего 6 лесенок.

-------------------------------------------------------------------------------------------------------

РЕШЕНИЯ

Задача 1. <Поиск решения с помощью графа (дерева) .>

Примечание 1: звездочками отмечены знакоместа, зарезервированные под буквы.

Примечание 2: курсивом отмечены цепочки, которые должны войти в окончательный ответ (всего их 16)

Задача 2. <Поиск решения с помощью дерева>

Задача 3. Решение (виртуально имеется в виду дерево):

1) Для 1-й буквы имеется 3 варианта (т.е. на 1-м уровне - 3 вершины)

2) 2-й буквой можем поставить любую из 3-х согласных (т.е. на 2-м уровне - 9 вершин)

3) Для 3-й буквы в каждом случае имеется 2 варианта, т.к. одна гласная уже занята выше (т.е. на 3-м уровне - 18 вершин)

4) Для 4-й буквы в каждом случае имеется 2 варианта, т.к. одна согласная уже занята выше (т.е. на 4-м уровне - 36 вершин)

5) На 5-м и 6-м уровнях - у нас единственные продолжения, т.е. число 36 сохраняется.

Задача 4. Решение

(Решение видно из таблицы, если читать ее снизу вверх)

Замечание: содержательное развлечение - придумать слово, процесс шифрования которого никогда не кончится (тривиальные решения - "слова" из одних гласных или одних согласных).

Задача 5. Решение

(Решение видно из приведенных ниже таблиц)

< замечание к задачам 4 - 5: остановку процесса шифрования (по критерию) можно производить не только после этапа типа 1, но и после этапа типа 2>

Задача 6 . Пояснения к решению

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

2. Цифра 5 первый раз появляется в строке (5), в следующей строке она встречается 2 раза и т. д., поэтому в последней строке цифра 5 встретится
16 раз.

3. В последней строке 1023 цифры. Можно считать количество вхождений каждой цифры, как это сделано для цифры 5 (для остальных - аналогично), а потом сложить, но экономнее обосновать, что при заданной рекуррентности получается di=2*di-1= 2i+1-1, откуда получаем, что для последней строки (9)
d9=210-1 = 1023. Здесь di - длина i-й строки

4. В последней строке последние 10 цифр мы знаем, а перед ними идет комбинация из цифр "10", поэтому на 1012-м месте стоит цифра 1 (далее - цифра 0, а затем 10 цифр от 0 до 9)

5. Используя результат п.3, получим, что суммарное количество цифр во всех строках есть

S=21-1+22-1+23-1+24-1+25-1+26-1+27-1+28-1+29-1+210-1 =
1+21+22+23+24+25+26+27+28+2210-119+210-11 = (211-1) - 11 = 2048 - 12 = 2036

Замечание. Хорошая задача по программированию: по заданному N найти N-й символ в последней строке. При этом, если в качестве "исходного сырья" использовать не цифры 0 - 9, а, например, латинские буквы (их 26, так что на использование массивов рассчитывать не приходится, что еще может как-то пройти при 10 цифрах), то задача становится совсем содержательной.

Задача 7 .

Решение:    Выполним программу по шагам:

Ответ: x = 203, y=25, z=54

Задача 8 .

Решение (цифры в верхнем ряду показывают уровень дерева игры):

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

Замечание: задач этого типа можно изготовить очень много (например, в условии выигрыша поставить связку И вместо связки ИЛИ, не говоря уже о вариации исходных данных). Важно лишь, чтобы анализ игры с использованием дерева можно было провести за разумное (небольшое) время.

Задача 9 .

РЕШЕНИЕ 1 (для примера взят Х=c5)

Пояснение: все пути перечислены в последнем столбце (всего 15 путей).

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

Замечание: вышеприведенное решение очень трудоемко (даже при ответе 15 путей). Использование "почти двоичного" дерева - менее трудоемко.

"Почти двоичное" дерево означает, что в общем случае имеется два продолжения (ВЛЕВО и ВНИЗ), кроме случаев, когда мы находимся на 1-й вертикали или на горизонтали "а" - здесь продолжение единственно.

Поэтому решение задачи 9 приведем в другом виде, где используем обозначения Л (ВЛЕВО) и Н (ВНИЗ), начальным полем возьмем Х=с4 - из таблицы видно, что мы должны получить 10 путей (что, очевидно, получается и из соображений комбинаторики).

РЕШЕНИЕ 2.  Дерево для построения всех путей из Х=с4 в клетку а1.

Примечание: в крайнем правом столбце показаны уровни дерева.

Решение (Ответ) запишем несколько в другом виде - будем указывать не клетки каждого маршрута, а последовательные ходы (ВЛЕВО, ВНИЗ) для каждого маршрута (которых, как мы знаем, должно получиться 10 - это число терминальных вершин в построенном дереве).

Ответ:

1) ВЛЕВО, ВЛЕВО, ВНИЗ, ВНИЗ, ВНИЗ

2) ВЛЕВО, ВНИЗ, ВЛЕВО, ВНИЗ, ВНИЗ

3) ВЛЕВО, ВНИЗ, ВНИЗ, ВЛЕВО, ВНИЗ

4) ВЛЕВО, ВНИЗ, ВНИЗ, ВНИЗ, ВЛЕВО

5) ВНИЗ, ВЛЕВО, ВЛЕВО, ВНИЗ, ВНИЗ

6) ВНИЗ, ВЛЕВО, ВНИЗ, ВЛЕВО, ВНИЗ

7) ВНИЗ, ВЛЕВО, ВНИЗ, ВНИЗ, ВЛЕВО

8) ВНИЗ, ВНИЗ, ВЛЕВО, ВЛЕВО, ВНИЗ

9) ВНИЗ, ВНИЗ, ВЛЕВО, ВНИЗ, ВЛЕВО

10) ВНИЗ, ВНИЗ, ВНИЗ,ВЛЕВО, ВЛЕВО

Все пути указаны в лексикографическом порядке по возрастанию(если считать, что Л<Н), т.к. выбран "левосторонний" обход дерева.

Задача 10 .

РЕШЕНИЕ (для примера взято Х=с3). Ниже - таблица с числом путей.

Анализируя дерево, дающее решение (выполнено на бумаге), получим ОТВЕТ:.

Задача 11 .  

Ответы приведены непосредственно после условий задач, решения - практически очевидны.

Задача 12 .

Решение получается по формуле C = C(X,Y)*C(Y,a1),

где С - общее количество искомых путей, C(X,Y) - количество путей из X в Y, C(Y,a1) - количество путей из Y в клетку а1, а отдельные сомножители мы вычислять умеем (как показано в предыдущих задачах).

ПРИМЕР: пусть X=f6, Y=c4. Тогда C = C(X,Y)*C(Y,a1) = 10 * 10 = 100.

Замечание: вариация задачи - если есть три возможности для каждого хода: "влево", "вниз" и "вниз-влево".

Задача 13 .  Решение - практически очевидно.

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

Замечание 2: вариация задачи - если есть три возможности для каждого хода: "влево", "вниз" и "вниз-влево" - она также легко решается просмотром "вверх","вверх-вправо", "вправо", начинающимся из клетки а1.(Для задачи в этом варианте также существует аналитическое правило, чуть более сложное: как, зная номер столбца и номер строки, сразу сказать, какой игрок выиграет  при правильной игре - первый или второй.)

Задача 14 .

Решение: поскольку 123 + 132 = 255 = 28-1, а число 28-1 записывается в двоичном виде как 11111111, то именно это двоичное число мы получим.

Для пояснения приводится двустрочная таблица, где в верней строчке приведены номера разрядов (начиная с нулевого разряда)

Задача 15.

РЕШЕНИЕ. (сама блок-схема будет нарисована несколько позже с помощью программы, специально для этого предназначенной, а пока приводится поблочное словесное описание, близкое к блок-схеме):

БЛОК 1.  i:=1; a:=2; S:=2:    {а - для предыдущего члена последователь                                        ности, b - для последующего }

БЛОК 2.  i:=i+1; b:=3*a - 2; S:= a+b; a:=b;

БЛОК 3. ЕСЛИ i<12  ТО Перейти на БЛОК 2 ИНАЧЕ Перейти на БЛОК 4

БЛОК 4  Выдача результатов - b, S (при необходимости) и окончание программы.

Примечание: вместо a,b можно пользоваться обозначениями xi ,xi+1 (это может быть намеком на то, что программист намерен пользоваться массивом х[1..12]).

Замечание: задачи, связанные с рисованием блок-схем, - плохо подходят для тестов, т.к. практически не поддаются механической проверке. Можно, конечно, оформить задачу в виде "теста с закрытым ответом" - т.е. несколько вариантов блок-схем, из которых только одна правильная (не содержащая алгоритмических ошибок) - именно ее должен ученик указать в качестве правильного ответа. Однако, придумывать для простых задач неправильные варианты блок-схем - непростое дело.

Задача 16.

РЕШЕНИЕ. (сама блок-схема будет нарисована несколько позже с помощью программы, специально для этого предназначенной, а пока приводится поблочное словесное описание, близкое к блок-схеме):

НАЧАЛО

БЛОК 1. Ввод x1,y1,x2,y2,x3,y3

БЛОК 2.  ЕСЛИ (x1*x1 + y1*y1) < 100  ТО Перейти на БЛОК 3

                ИНАЧЕ Перейти на БЛОК 6

БЛОК 3.  ЕСЛИ  (x2*x2 + y2*y2) < 100  ТО Перейти на БЛОК 4

                ИНАЧЕ Перейти на БЛОК  6

БЛОК 4.  ЕСЛИ  (x3*x3 + y3*y3) < 100  ТО Перейти на БЛОК 5

                ИНАЧЕ Перейти на БЛОК  6

БЛОК 5.  Выдать "Тр-к лежит внутри окружности"; Перейти на Конец пр-ммы;

БЛОК 6.  Выдать "Тр-к лежит вне окружности"

КОНЕЦ ПРОГРАММЫ

Замечания - в основном те же, что и к предыдущей задаче.

Возможнаяя переделка задачи (для обеспечения механической проверки): предъявляется блок-схема программы, задаются значения x1,y1,x2,y2,x3,y3, требуется выяснить - какой ответ даст программа (тут плохо только то, что, имея под рукой лист клетчатой бумаги, ученик может получить ответ просто "из чертежа", а не анализируя блок-схему или текст программы).Заметим, что для предыдущей программы этого недостатка нет.

Задача 17.

Решение приведено сразу же после текста задачи.

Задача 18.

РЕШЕНИЕ. (сама блок-схема будет нарисована несколько позже с помощью программы, специально для этого предназначенной, а пока приводится поблочное словесное описание, близкое к блок-схеме):

НАЧАЛО

БЛОК 1. u:=2; v:=1; i:=1;    {i - счетчик}

БЛОК 2. a:=u*u-v*v; b:=2*u*v; c:= u*u+v*v;

БЛОК 3. Выдать a,b,c

БЛОК 4. u:=u+1; v:=v+1; i:=i+1;

БЛОК 5. ЕСЛИ i<6 ТО Перейти на БЛОК 2

КОНЕЦ

Замечания - в основном те же, что и к предыдущим задачам, связанным с блок-схемами.

Задача 19.

Решение:

Примечания:

1. Правая ветка дерева (начинающаяся с буквы Б) не поместилась в таблицу, но ее можно получить из левой ветки путем формальной замены А <--> Б.

Для получения ответа нужно перечислить все ветви дерева.

2. В крайней правой колонке показаны уровни дерева.

Задача 20.

Решение:

Поскольку всего цепочек длины k=5, составленных из двух букв, есть 25=32
(что должно быть известно школьникам, или легко сообразить, если посмотреть на двоичное дерево с 5 уровнями), а число цепочек, где троекратное повторение не допускается, мы только что посчитали - получилось 16, то искомое число цепочек - это все оставшиеся цепочки, то есть их будет 32 - 16 = 16.

ЗАДАЧА 21.

Решение представлено приведенным ответом.

ЗАДАЧА 22.

Решение очевидно из разобранного примера.

ЗАДАЧА 23.

Решение:

c / (2 + a / (b+x)) = 5

c=10 +5a / (b+x)

5a / (b+x) = c -10

(b+x) / 5a = 1 / (c -10)

x / 5a = 1 / (c -10) - b / 5a

x= 5*a* (1 / (c -10) - b / (5*a)) - ОТВЕТ (в одной из возможных форм записи).

Пошаговая запись ответа:

1) y1:=5*a

2) y2:=c-10

3) y3:=1/y2

4) y4:=b/ y1

5) y5:=y3-y4

6) x:=y1*y5

Задача 24

Решение следует из того, что для обеспечения замкнутости маршрута команд ВВЕРХ должно быть столько же, сколько команд ВНИЗ, а команд ВЛЕВО - столько же, сколько команд ВПРАВО. Таким образом, в качестве ответа годится любой набор, в котором есть 2 команды ВЛЕВО, одна команда ВНИЗ и одна команда ВВЕРХ.

Некоторое усложнение ЗАДАЧИ 24: - задана та же таблица с 4 стертыми командами, но количество команд каждого типа - неизвестно

Задание - то же ( восстановить стертые команды так, чтобы путь Робота по-прежнему заканчивался в левом нижнем углу);

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

ЗАДАЧА 25.

Решение приведено в разделе "ОТВЕТ" сразу же за постановкой задачи.

ЗАДАЧА 26.

Идея решения состоит в том, что в программе каждая команда

УМЕНЬШИТЬ ЯЧЕЙКИ (k1,k2) должна иметь k1 из первой половины массива, а k2 - из второй половины массива (или наоборот).

Задача 27.

Замечание к Решению: чтобы не сбиться при перечислении троек, рекомендуется перечислять их в лексикографическом порядке (как это и сделано при выписывании ответа).

Задача 28.

РЕШЕНИЕ. Пользуясь тем что условие префиксности соблюдается (никакое кодовое слово не является начальной частью другого кодового слова), делим заданную строку на составные части

11  000  001  001  10

и получаем ОТВЕТ: badde.

Замечание. Облегченный вариант задачи - если все коды состоят из трех битов - тогда поиск решения выполняется еще быстрее: делим строку на группы по три бита, затем записываем соответствующие буквы.

Задача 29.

РЕШЕНИЕ. В данном случае условие префиксности не соблюдается (для букв  "r" и "b" ), поэтому возможна неоднозначность раскодировки. Варианты:

1)   01  111  101100 - не подходит, т.к. нет дальнейшей расшифровки

2)   011  111  01  100  -  bare                          

3)   011  111  011  00  -  baby

ОТВЕТ: возможные варианты раскодировки - bare, baby

Задача 30.

Обсудим разные решения (хорошие и плохие - "трудоемкие")

Решение 1 (плохое). Составим все возможные 4! = 24 перестановки - от

БИМФ до ФМИБ. Вычеркнем из них все, в которых пожелания какого-либо учителя нарушаются. Оставшиеся (если таковые будут) - составят набор приемлемых расписаний.

Решение 2 (рассмотрение на дереве)

Сначала составим вспомогательную табличку, наглядно отражающую пожелания учителей:

В следующей таблице будем строить дерево

Примечания: знак @ означает, что по этой ветке нет продолжения; в левой колонке - номера уроков (они же - номера уровней дерева для последней таблицы).

Анализируя построенное дерево, видим, что имеется только 2 возможных варианта расписания: МФБИ   и    ИМФБ.

Решение 3 (попытка использовать логические переменные

Пусть логические переменные:

x1 - "математик имеет 1-й урок"

x2 - "математик имеет 2-й урок"

x3 - "физик имеет 2-й урок"

x4 - "физик имеет 3-й урок"

x5 - "информатик имеет 1-й урок"

x6 - "информатик имеет 4-й урок"

x7 - "биолог имеет 3-й урок"

x8 - "биолог имеет 4-й урок"

Получим систему:

x1∨x2 = 1; x3∨x4 = 1; x5∨x6 = 1; x7∨x8 = 1;

x1x5 = 0; x2x3 = 0; x4x7 = 0; x6x8 = 0,

x1x2 = 0; x3x4 = 0; x5x6 = 0; x7x8 = 0,

которую еще надо решить каким-то способом (который в школе не проходят и вряд ли будут проходить).

Во всяком случае, зная Решение 2, можно проверить, что значения

x1=1, x3=1, x7=1, x6=1, а также x5=1, x2=1, x4=1, x8=1 - удовлетворяют системе (в каждом из двух решений неназванные переменные принимают нулевые значения).

Замечание. Задачу 30 можно формализовать (и сократить текст):

 сколько существует 4-буквенных цепочек из букв М, Ф, И, Б,если каждая буква должна входить в цепочку 1 раз и должны быть выполнены следующие условия:

буква М может стоять на 1 или 2 месте, буква Ф - на 2 или 3 месте, буква И - на 1 или 4 месте, буква Б - на 3 или 4 месте. Перечислить все такие цепочки.

 ОТВЕТ (естественно, тот же): МФБИ   и    ИМФБ.

Задача 31.  РЕШЕНИЕ:

Как и в предыдущей задаче, сначала составим вспомогательную табличку, наглядно отражающую пожелания учителей: