Задание 10 (презентация по типам задач к ЕГЭ)

В данной перзентации рассматриваются основные типы задач на использование методов измерения количества информации. В презентации использованы типовые задачи с решениями из материалов К.Ю.Полякова с сайта http://kpolyakov.spb.ru . .

Просмотр содержимого документа «Задание 10 (презентация по типам задач к ЕГЭ)»

ege-10 (базовый уровень, время – 4 мин )

Кодирование данных, комбинаторика,

Что нужно знать :

русский алфавит
принципы работы с числами, записанными в позиционных системах счисления
если слово состоит из L букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение

N = n 1 · n 2 · … · n L

если слово состоит из L букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как N =nL

Вася составляет 5-буквенные слова , в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз . Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

буква С может стоять на одном из пяти мест:

С ****, * С ***, ** С **, *** С * и **** С , где * обозначает любой из оставшихся трёх символов ( Л, О, Н )

в каждом случае в остальных четырёх позициях может быть любая из трёх букв Л, О, Н , поэтому при заданном расположении буквы С имеем 34= 81 вариант

всего вариантов 5 · 81 = 405 .

Ответ: 405 .

Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите < A, C, G, T >, которые содержат ровно две буквы A ?

Решение ( 1 вариант , перебор):

рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:

в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 33= 27

всего 4 шаблона, они дают 4· 27 = 108 комбинаций

далее рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три:

они дают 3 · 27 = 81 комбинацию

два шаблона, где первая по счёту буква А стоит на третьей позиции:

они дают 2 · 27 = 54 комбинации

и один шаблон, где сочетание АА стоит в конце:

они дают 27 комбинаций

Ответ : 270

всего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций

Решение ( 2 вариант , использование формул комбинаторики):

в последовательности из 5 символов нужно использовать ровно две буквы А и три символа, не совпадающих с А, которые обозначим «*»

найдём количество перестановок из двух букв А и трёх «*»

используем формулу для вычисления числа перестановок с повторениями ; для двух разных символов она выглядит так:

– количество букв А,

вместо каждой из «*» может стоять любой из трёх символов (кроме А), т.е. на каждую из 10 перестановок мы имеем 3 3 = 27 вариантов распределения остальных символов на месте «*»

таким образом, получаем всего 10 · 27 = 270 вариантов.

Ответ : 270

Сколько слов длины 5 , начинающихся с гласной буквы , можно составить из букв Е, Г, Э ? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Решение (1 вариант):

первая буква слова может быть выбрана двумя способами ( Е или Э ), остальные – тремя ( Е, Г и Э )

общее число различных слов равно 2*3*3*3*3 = 162

Ответ: 162

Решение (2 вариант):

Дано слово длиной 5 символов типа * ****, где красная звездочка – гласная буква ( Е или Э ), а черная - любая буква из трёх заданных.

Общая формула для определения количества вариантов:

N = M L , где М – мощность алфавита, а L – длина кода.

Так как положение одной из букв строго регламентировано (знак умножения в зависимых событиях), то формула всех вариантов примет вид: N = M1L1∙ M2L2

Тогда M1= 2 (алфавит гласных букв), а L1= 1 (только 1 позиция в слове). M2= 3 (алфавит всех букв), а L2= 4 (оставшиеся 4 позиции в слове).

В итоге получаем: N = 2 1 ∙ 3 4 = 2 ∙ 81 = 162 .

Ответ: 162

Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

Запишите слово, которое стоит на 67-м месте от начала списка.

выполним замену К0, Л1, Р2, Т3; поскольку нумерация слов начинается с единицы, а первое число КККК0000 равно 0 , под номером 67 будет стоять число 66 , которое нужно перевести в четверичную систему: 66 = 10024

Выполнив обратную замену (цифр на буквы), получаем слово ЛККР.

Ответ: ЛККР

Все 5-буквенные слова, составленные из букв А, О, У , записаны в алфавитном порядке.

Вот начало списка:

Запишите слово, которое стоит на 240-м месте от начала списка.

заменяем обратно цифры на буквы:

22212  УУУОУ

выпишем начало списка, заменив буквы на цифры:

это напоминает числа, записанные в троичной СС в порядке возрастания: на первом месте стоит число 0 , на втором – 1 и т.д.

тогда легко понять, что 240 -м месте стоит число 239, записанное в троичной СС

Переведем в троичную СС: 239 = 22212 3

Ответ: УУУОУ

Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке.

Вот начало списка:

На каком месте от начала списка стоит слово ШКОЛА ?

будем использовать пятеричную СС с заменой А0, К1, Л2, О3 и Ш4

слово ШКОЛА запишется в новом коде так: 41320 5

переводим это число в десятичную систему:

41320 5 = 4  5 4 + 1  5 3 + 3  5 2 + 2  5 1 = 2710

Т.к. нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, то к полученному результату нужно прибавить 1, тогда…

Ответ: 2711

Все 5 - буквенные слова, составленные из букв А, О, У, записаны в обратном алфавитном порядке. Вот начало списка:

Запишите слово, которое стоит на 240 -м месте от начала списка.

заменяем обратно цифры на буквы, учитывая обратный алфавитный порядок ( 0 → У, 1 → О, 2 → А ): 22212  АААОА

Выпишем начало списка, заменив буквы на цифры так, чтобы порядок символов был обратный алфавитный ( У → 0, О → 1, А → 2 ):

Это числа, записанные в троичной СС в порядке возрастания: на 1-м месте стоит число 0 , на 2-м – 1 и т.д.

легко понять, что 240 -м месте стоит число 239 , записанное в троичной СС

переведем 239 в троичную систему: 239 = 222123

Ответ: АААОА

Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует 5 -буквенные слова, в которых есть только буквы П, И, Р , причём буква П появляется ровно 1 раз . Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

буква П может стоять на одном из пяти мест:

П ****, * П ***, ** П **, *** П * и **** П , где * обозначает любой из оставшихся двух символов ( И и Р )

в каждом случае в остальных четырёх позициях может быть любая из 2 - х букв И , Р поэтому при заданном расположении буквы П имеем 24= 16 вариант

всего вариантов 5 · 16 = 80 .

Ответ: 80

Все 3 -буквенные слова, составленные из букв Г, Е, П, А, Р, Д записаны в алфавитном порядке и пронумерованы, начиная с 1.. Ниже приведено начало списка:

Под каким номером в списке идет первое слово , которое начинается с буквы Г ?

выпишем начало списка, заменив буквы на цифры:

7 . 010 6 =0*6 2 +1*6 1 +0*6 0 = 6 10

будем использовать шестеричную СС с заменой А0, Г1, Д2, Е3, П4, Р5

первое слово , которое начинается с буквы Г в шестеричной СС будет иметь вид: 1006

переведем число 100 6 =1*6 2 =36 10

Ответ: 37

добавим 1 и получим: 37 – номер искомой строки

Для тренировки

Сколько «слов» длины 7 символов, начинающихся с английской буквы, можно составить из букв S , И , R , П , Q ?

Каждая буква может входить в «слово» несколько раз, а сами получаемые «слова» не обязательно должны быть осмысленными.

Решение:

1) Определяем количество «слов», которые можно составить из указанных букв без учета первой буквы, на которую накладывается особое условие («только английская»), т.е. количество «слов» длиной 6 символов.

Сопоставляем каждой букве цифру, например: S = 0 , И = 1 , R = 2 , П = 3 , Q = 4 . Тем самым задача сводится к следующей: «сколько различных 6-разрядных чисел можно получить в пятеричной СС».

Количество таких чисел равно nm , где n – основание системы счисления, а m – количество разрядов.

В нашем случае получается 5 6 = 15625 чисел («слов»).

Первая буква должна быть только английской. Английских букв у нас три . Для каждой из них возможно 15625 слов.

Тогда общее количество слов равно 3  15625 = 46875 .

📎📎📎📎📎📎📎📎📎📎