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

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

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

системы счисления

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

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

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

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

Пример I:

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

Решение

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

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

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

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

Ответ: 405 .

Пример II:

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

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

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

АА***

А*А**

А**А*

А***А

• в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 3 3 = 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

Пример III:

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

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

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

Е или Э

2

*

*

3

*

3

*

3

3

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

Ответ: 162

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

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

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

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

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

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

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

Ответ: 162

Пример IV:

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

1. КККК

2. КККЛ

3. КККР

4. КККТ

……

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

Решение

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

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

Ответ: ЛККР

Пример V:

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

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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

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

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

22212  УУУОУ

Решение

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

1. 00000

2. 00001

3. 00002

4. 00010

……

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

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

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

Ответ: УУУОУ

Пример VI:

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

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

1. ААААА

2. ААААК

3. ААААЛ

4. ААААО

5. ААААШ

6. АААКА

……

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

Решение

• будем использовать пятеричную СС с заменой А  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

Пример VII:

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

1. УУУУУ

2. УУУУО

3. УУУУА

4. УУУОУ

……

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

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

Решение

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

1. 00000

2. 00001

3. 00002

4. 00010

……

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

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

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

Ответ: АААОА

ДЕМО - 2016:

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

Решение

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

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

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

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

Ответ: 80

Вариант 2

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

1. ААА

2. ААГ

3. ААД

4. ААЕ

5. ААП

6. ААР

7. АГА

……

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

перев

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

1. 000

2. 001

3. 002

4. 003

5. 004

6. 005

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

=0

=1

=2

=3

=4

=5

=6

Решение

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

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

• переведем число 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-разрядных чисел можно получить в пятеричной СС».

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

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

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

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

Ответ:

46875