Добавлен: 20.10.2018
Просмотров: 803
Скачиваний: 9
10_графы. Домашнее задание
1. На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой
дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует
различных путей из города А в город М, не проходящих через город Г?
2. На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой
дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует
различных путей из города А в город Л?
3. На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой
дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует
различных путей из города А в город Н, не проходящих через город М?
4. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М. По каждой дороге можно
двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей,
ведущих из города А в город М и проходящих через город В?
5. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, O, Т. По каждой
дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует
различных путей, ведущих из города А в город Т и проходящих через город И?
А
К
Л
М
Б
В
Г
Д
Е
Ж
З
И
А
М
П
Л
Н
Б
В
Г
Д
Е
Ж
З
И
К
А
М
П
Л
Н
Б
В
Г
Д
Е
Ж
З
И
К
А
Б
Д
Е
З
И
К
Л
М
В
Г
Ж
А
Б
Д
Е
З
И
К
Н
Т
В
Г
Ж
Л
М
O
10_графы. Домашнее задание
6. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, O, Т. По каждой
дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует
различных путей, ведущих из города А в город Т и проходящих через город К?
7. У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. умножь на 2
Сколько есть программ, которые число 1 преобразуют в число 16?
8. У исполнителя Калькулятор три команды, которым присвоены номера:
1. прибавь 1
2. умножь на 2
3. возведи в квадрат
Сколько есть программ, которые число 2 преобразуют в число 38?
9. У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. увеличь число десятков на 1
Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2
вторая с конца цифра равна 9, она не изменяется.
Сколько есть программ, которые число 12 преобразуют в число 36?
10. У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. умножь на 1,5
Первая из них увеличивает на 1 число на экране, вторая увеличивает это число
в 1,5 раза, если число чётное. К нечётным числам вторая команда неприменима. Сколько есть
программ, которые число 2 преобразуют в число 22?
11. У исполнителя Калькулятор три команды, которым присвоены номера:
1. прибавь 1
2. сделай чётное
3. сделай нечётное
4. умножь на 10
Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит
число x в число 2x + 1, четвертая умножает на 10. Например, вторая команда переводит число 10 в число
20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность
команд. Сколько существует программ, которые число 1 преобразуют в число 15?
12. Исполнитель А23S преобразует целое число, записанное на экране. У исполнителя три команды, каждой
команде присвоен номер:
1. Прибавь 2
2. Прибавь 3
3. Прибавь предыдущее
Первая команда увеличивает число на экране на 2, вторая увеличивает это число на 3, третья
прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10
и т. д.). Программа для исполнителя А23S – это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 11?
А
Б
Д
Е
З
И
К
Н
Т
В
Г
Ж
Л
М
O
10_графы. Домашнее задание
13. По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи
используется двоичный код, удовлетворяющий условию Фано. Для букв А и Б используются такие
кодовые слова: А – 1; Б – 011. Укажите сумму длин кратчайших кодовых слов для букв В и Г, при
котором код будет допускать однозначное декодирование.
14. По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи
используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое
слово: А – 1. Укажите сумму длин кратчайших кодовых слов для букв Б, В и Г, при котором код будет
допускать однозначное декодирование.
15. Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили
неравномерный двоичный код. Для кодирования цветов используются кодовые слова.
Белый – 0, Зелёный – 11111, Фиолетовый – 11110, Красный – 1110, Чёрный – 10.
Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код будет допускать
однозначное декодирование.