Задания 11 класс_простые задачи_информатика

Простые задачи графы и деревья

Задача 3.1.1. На рисунке приведен граф (множество вершин, соединенных ребрами). Сколько существует путей из вершины А в K?

Задача 3.1.1А. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Задача 3.1.2. Между населёнными пунк­та­ми A, B, C, D, E, F по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых при­ве­де­на в таб­ли­це. (От­сут­ствие числа в таб­ли­це озна­ча­ет, что пря­мой до­ро­ги между пунк­та­ми нет.)

Опре­де­ли­те длину крат­чай­ше­го пути между пунк­та­ми A и F (при усло­вии, что пе­ре­дви­гать­ся можно толь­ко по по­стро­ен­ным до­ро­гам).

Задача 3.1.3. На ри­сун­ке схема дорог изоб­ра­же­на в виде графа, в таб­ли­це со­дер­жат­ся све­де­ния о дли­нах этих дорог.

Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, то ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Опре­де­ли­те, ка­ко­ва длина до­ро­ги из пунк­та Д в пункт Е. В от­ве­те за­пи­ши­те целое число – так, как оно ука­за­но в таб­ли­це.

Задача 3.1.4. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Г. В ответе запишите целое число.

Задача 3.1.5. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Укажите кратчайший путь из пункта А в пункт К. В ответе перечислите все населённые пункты, через которые проходит путь. Например, путь из Г в Д через Е и К записывается как ГЕКД.

Задача 3.1.6. Пу­те­ше­ствен­ник при­шел в 08:00 на ав­то­стан­цию по­сел­ка ЛЕС­НОЕ и уви­дел сле­ду­ю­щее рас­пи­са­ние ав­то­бу­сов:

Опре­де­ли­те самое ран­нее время, когда пу­те­ше­ствен­ник смо­жет ока­зать­ся в пунк­те ПО­ЛЕ­ВОЕ со­глас­но этому рас­пи­са­нию.

Задача 3.1.7. Во фраг­мен­те базы дан­ных представлены све­де­ния о род­ствен­ных отношениях. На ос­но­ва­нии приведённых дан­ных определите ID дяди Кор­зу­н П. А.

Задача 3.1.8. В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите количество человек, у которых есть брат с разницей не более чем в 5 лет.

Количество программ и чисел

Задача 3.2.1. Исполнитель может выполнять только две команды, которым присвоены номера:

1. Прибавь 1

2. Возведи во вторую степень

Напишите самую короткую программу, которая из числа 1 получает 37. Если таких программ несколько, напишите любую из них.

Задача 3.2.2. У исполнителя «Троечник» две команды, которым присвоены номера:

1. прибавь 3,

2. умножь на 3.

Первая из этих команд увеличивает число на экране на 3, вторая умножает его на 3. Программа - это последовательность номеров команд. Например, 121 - это программа прибавь 3, умножь на 3, прибавь 3. Эта программа преобразует число 1 в число 15. 

Запишите программу, которая преобразует число 6 в число 69 и содержит не более 5 команд. Если таких программ более одной, то запишите любую из них.

Задача 3.2.3. Исполнитель может выполнять только две команды, которым присвоены номера:

1. Прибавь 1

2. Умножь на 2

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

Задача 3.2.4. Исполнитель может выполнять только две команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 2

Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 4 команд? 

Задача 3.2.5. Исполнитель может выполнять только две команды:

1. Прибавь 3

2. Вычти 2

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

Задача 3.2.6. У исполнителя Калькулятор две команды: 

1. умножь на 15,

2. подели на 2.

Первая из них увеличивает число на экране в 15 раз, вторая – уменьшает его в 2 раза. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 4096 с помощью программы, которая содержит ровно 12 команд?

Задача 3.2.7. У исполнителя Калькулятор две команды: 

1. прибавь 2

2. прибавь 3.

 Первая из них увеличивает число на экране на 2, вторая — на 3. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 10 команд?

Задача 3.2.8. Исполнитель может выполнять только три команды:

1. Прибавь 2

2. Прибавь 4

3. Прибавь 5

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

Задача 3.2.9. Исполнитель Фибо преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2.

Программа для исполнителя Фибо — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 3 в число 20, и при этом траектория вычислений содержит число 9 и не содержит числа 15?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 9, 10, 12.