Для подготовки тренинга использовались материалы с сайта К.Ю. Полякова. - презентация

1 Для подготовки тренинга использовались материалы с сайта К.Ю. Полякова

2 Содержание 1. Теоретический материал 2. Разбор задач: Комбинаторика Комбинаторика Комбинаторика Анализ последовательностей (системы счисления) Анализ последовательностей (системы счисления)Анализ последовательностей Анализ последовательностей 3. Задачи для тренировки

3 Теоретический материал Что нужно знать : 1. русский алфавит 2. принципы работы с числами, записанными в позиционных системах счисления Количество цифр в алфавите системы счисления равно основанию системе счисления. Старшая цифра в алфавите системы счисления и её основание связаны следующим образом К=Р-1, где К – старшая цифра, Р –основание системы счисления 3. формулу для вычисления числа перестановок с повторениями 4. таблица степеней двойки, она же показывает, сколько вариантов Q можно закодировать с помощью K бит:

4 Разбор задач Комбинаторика Задача 1 Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)? Решение : согласно условию, алфавит содержит только два знака – точку и тире «не менее четырёх и не более пяти сигналов» означает, что нужно определить количество всех 4- и 5-буквенных слов в двоичном алфавите количество 4-буквенных слов равно 2 4 = 16, а количество 5- буквенных 2 5 = 32 поэтому общее количество 4- и 5-буквенных слов равно = 48 ответ: 48.

5 Задача 1 Какое наименьшее число символов должно быть в алфавите, чтобы при помощи всевозможных трехбуквенных слов, состоящих из символов данного алфавита, можно было передать не менее 9 различных сообщений? Задачи для тренировки Ответы

6 Задача 3 Сколько существует различных четырехзначных чисел, в записи которых используются только четные цифры? 1) 1252) 250 3) 5004) 625

7 Задача 4 Сколько существует четырехзначных чисел, в записи которых все цифры различны? 1) 35282) ) 50404) 9000

8 Задача 5 Сколько существует различных четырехзначных чисел, в записи которых ровно две девятки, стоящие рядом? 1) 2122) 225 3) 2434) 280

9 Задача 6 Сколько существует различных четырехзначных чисел, в записи которых не более двух различных цифр? 1) 4462) 5163) 5764) 640

10 Задача 7 Сколько существует различных четырехзначных чисел, в записи которых все цифры нечетные и хотя бы одна из них равна 5? 1) 2262) 3693) 6004) 625 Решение : все числа, состоящие только из нечетных цифр, можно разбить на две группы: те, в которых есть пятерка, и те, где ее нет общее число чисел, состоящих только из нечетных цифр, находим аналогично первой рассмотренной задаче; учитывая, что среди них нет нуля, получаем 5·5·5·5 = 625 вариантов теперь аналогично найдем количество чисел, состоящих только из цифр 1, 3, 7 и 9 (без пятерки); поскольку на каждом из 4-х мест может стоять одна из 4-х цифр, получаем 4·4·4·4 = 256 вариантов нужный нам результат – это разница 625 – 256 = 369 вариантов таким образом, правильный ответ – 2. Задачи для тренировки

11 Анализ последовательностей Задача 1 Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A? Решение (вариант 1, перебор): рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А: АА*** А*А**А**А* А***А Здесь звёздочка обозначает любой символ из набора {C, G, T}, то есть один из трёх символов. итак, в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 3 3 = 27 всего 4 шаблона, они дают 4 · 27 = 108 комбинаций теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три: *АА** *А*А**А**А они дают 3 · 27 = 81 комбинацию два шаблона, где первая по счёту буква А стоит на третьей позиции: **АА* **А*А они дают 2 · 27 = 54 комбинации и один шаблон, где сочетание АА стоит в конце ***АА они дают 27 комбинаций всего получаем ( ) · 27 = 270 комбинаций ответ: 270.

12 Задача 1

13 Задача 2 Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. Решение: первая буква слова может быть выбрана двумя способами (Е или Э), остальные – тремя общее число различных слов равно 2*3*3*3*3 = 162 ответ: 162. Решение (через формулы, А.Н. Носкин): Дано слово длиной 5 символов типа *****, где красная звездочка – гласная буква (Е или Э), а черная буква любая из трёх заданных. Общая формула количества вариантов: N = M L, где М – мощность алфавита, а L – длина кода. Так как положение одной из букв строго регламентировано (знак умножения в зависимых событиях), то формула всех вариантов примет вид: N = M 1 L 1 M 2 L2, Тогда M 1 = 2 (алфавит гласных букв), а L 1 = 1 (только 1 позиция в слове). M 2 = 3 (алфавит всех букв), а L 2 = 4 (оставшиеся 4 позиции в слове). В итоге получаем: N = = 2 81 = 162. ответ: 162.

14 Задача 3 Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. КККК 2. КККЛ 3. КККР 4. КККТ …… Запишите слово, которое стоит на 67-м месте от начала списка. Решение: самый простой вариант решения этой задачи – использование систем счисления; действительно, здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв) выполним замену К 0, Л 1, Р 2, Т 3; поскольку нумерация слов начинается с единицы, а первое число КККК 0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = Выполнив обратную замену (цифр на буквы), получаем слово ЛККР. Ответ: ЛККР.

15 Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААЛ 4. ААААО 5. ААААШ 6. АААКА …… На каком месте от начала списка стоит слово ШКОЛА? Решение: по аналогии с предыдущим решением будем использовать пятеричную систему счисления с заменой А 0, К 1, Л 2, О 3 и Ш 4 слово ШКОЛА запишется в новом коде так: переводим это число в десятичную систему: = = 2710 поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1, тогда… Ответ: Задача 4

16 Все 5-буквенные слова, составленные из букв А, О, У, записаны в обратном алфавитном порядке. Вот начало списка: 1. УУУУУ 2. УУУУО 3. УУУУА 4. УУУОУ …… Запишите слово, которое стоит на 240-м месте от начала списка. Решение (2 способ, троичная система, идея М. Густокашина): по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию) выпишем начало списка, заменив буквы на цифры так, чтобы порядок символов был обратный алфавитный (У 0, О 1, А 2): …… это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д. тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления переведем 239 в троичную систему: 239 = заменяем обратно цифры на буквы, учитывая обратный алфавитный порядок (0 У, 1 О, 2 А): АААОА Ответ: АААОА. Задача 5 Задачи для тренировки Ответы