Кодирование информации. Последовательности. Подготовка к ЕГЭ
Кодирование информации. ПоследовательностиВ. И. Долженкова по материалам сайта К. Полякова http://kpolyakov.spb.ru/school/ppt.htm и Д. Гущина http://inf.reshuege.ru/
Задача № 1Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A?
рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:АА*** А*А** А**А* А***АЗдесь звёздочка обозначает любой символ из набора {C, G, T}, то есть один из трёх символов.в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 33 = 27 всего 4 шаблона, они дают 4 · 27 = 108 комбинаций
теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три:*АА** *А*А* *А**Аони дают 3 · 27 = 81 комбинациюдва шаблона, где первая по счёту буква А стоит на третьей позиции: **АА* **А*А они дают 2 · 27 = 54 комбинациии один шаблон, где сочетание АА стоит в конце: ***АА они дают 27 комбинацийвсего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций
Задача № 2Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.Решение:первая буква слова может быть выбрана двумя способами (Е или Э), остальные – тремя
{69CF1AB2-1976-4502-BF36-3FF5EA218861}Гласная (по условию)!Гласных в предложен-ном списке 2- «Е» и «Э»Любаяиз 3-х предложен-ных букв (их три!): «Е», «Г», «Э»Любаяиз 3-х предложен-ных букв (их три!): «Е», «Г», «Э»Любаяиз 3-х предложен-ных букв (их три!): «Е», «Г», «Э»Любаяиз 3-х предложен-ных букв (их три!): «Е», «Г», «Э»{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}2 * 3 * 3 * 3 * 3 = =162
Задача № 3Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:1. КККК2. КККЛ3. КККР4. КККТ……Запишите слово, которое стоит на 67-м месте от начала списка.
РЕШЕНИЕ МЕТОДОМ СИСТЕМ СЧИСЛЕНИЯ:Из условия: «Все 4-буквенные слова…»4-чная система счисления:К0, Л1, Р2, Т3Из условия: « …Вот начало списка:1. КККК2. КККЛ3. КККР4. КККТ…»нумерация слов начинается с единицы, а первое число КККК0000 равно 0
РЕШЕНИЕ МЕТОДОМ СИСТЕМ СЧИСЛЕНИЯ:номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 1002 четверичное Выполнив обратную замену (цифр на буквы), получаем слово ЛККР
Задача № 4Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке.Вот начало списка:1. ААААА2. ААААО3. ААААУ4. АААОА……Запишите слово, которое стоит на 240-м месте от начала списка.
РЕШЕНИЕ МЕТОДОМ ПЕРЕБОРА С КОНЦАСколько всего 5-буквенных слов можно составить из трех букв?есть всего 3 однобуквенных слова (А, О, У); Двух буквенных слов уже 33=9 (АА, АО, АУ, ОА, ОО, ОУ, УА, УО и УУ);Есть всего 35= 243 слова из 5 буквочевидно, что последнее, 243-е слово – это УУУУУВАЖНО: идём назад: предпоследнее слово УУУУО (242-е), затем идет УУУУА (241-е) и, наконец, УУУОУ (240-е)
Задача № 5Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке.Вот начало списка:1. ААААА2. ААААК3. ААААЛ4. ААААО5. ААААШ6. АААКА……На каком месте от начала списка стоит слово ШКОЛА?
РЕШЕНИЕ МЕТОДОМ СИСТЕМ СЧИСЛЕНИЯ:будем использовать пятеричную систему счисления с заменой А 0, К 1, Л 2, О 3 и Ш 4слово ШКОЛА запишется в числовом коде так: 413205переводим это число в десятичную систему: 413205 = 454 + 153 + 352 + 251 = 2710поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1, тогда…Ответ: 2711.