sotrud.ru 1 2 3 4

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

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


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


Ответ

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


Задача 2. Для составления цепочек разрешается использовать 5 бусинок, помеченных буквами А Б Е Ж И. Каждая цепочка должна состоять из k бусинок, где ki{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. (упрощенный вариант задачи N 4)

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

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

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


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


Задача 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 - верхняя правая).

a8


b8

c8

d8

e8

f8

g8

h8

a7

b7

c7

d7

e7

f7

g7

h7

a6

b6

c6

d6

e5

f6

g6

h6

a5

b5

c5

d5

e5

f5

g5

h5

а4

b4

c4

d4

e4

f4

g4

h4

а3

b3

c3

d3

e3

f3

g3

h3

а2

b2

c2

d2

e2


f2

g2

h2

а1

b1

c1

d1

e1

f1

g1

h1


Из некоторой начальной клетки Х (ХÎ{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. (по мотивам задачи N9) Имеется шахматная доска стандартного размера 8х8, со стандартным обозначением клеток (a1 - нижняя левая, ..., h8 - верхняя правая).

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

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

Л - ход ВЛЕВО

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

Н - ход ВНИЗ

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

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


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


1. ЛЛНН

2. ЛДН

3. ЛНЛН

4. ЛНД

5. ЛННЛ

6. ДЛН

7. ДД

8. ДНЛ

9. НЛЛН

10. НЛД

11. НЛНЛ

12. НДЛ

13. ННЛЛ


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

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


a8

b8

c8

d8

e8

f8

g8

h8

a7

b7

c7

d7

e7

f7

g7

h7

a6

b6

c6

d6

e5

f6

g6

h6

a5

b5


c5

d5

e5

f5

g5

h5

а4

b4

c4

d4

e4

f4

g4

h4

а3

b3

c3

d3

e3

f3

g3

h3

а2

b2

c2

d2

e2

f2

g2

h2

а1

b1

c1

d1

e1

f1

g1

h1

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

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

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

Решение (ОТВЕТ): (ответы записаны в соответствующих клетках шахматного поля)


1

8

15

22

29

36

71

226

1

7

7

7

7

7

35

155

1

6













28

120

1

5













28

92

1

4












28


64

1

3

6

10

15

21

28

36

1

2

3

4

5

6

7

8

a1

1

1

1

1

1

1

1


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

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


Решение (ОТВЕТ): (ответы записаны в соответствующих клетках шахматного поля)


1

15

52

100

148

196

390

1794

1

13

24

24


24

24

170

1234

1

11













146

918

1

9













146

636

1

7













146

344

1

5

13

25

41

61

85

113

1

3

5

7

9

11

13

15

a1

1


1

1

1

1

1

1


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

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

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

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


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


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

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

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


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


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


Ответ: получим 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" (другой вариант - вывод результатов показывать не надо).


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



следующая страница >>