Методическая разработка по теме "Практикум по теме  "Кодирование данных, комбинаторика, системы счисления. КЕГЭ -2025, задание 10»
методическая разработка по информатике и икт (10 класс)

Методическая разработка по теме "Практикум по теме  "Кодирование данных, комбинаторика, системы счисления. КЕГЭ -2025, задание 10»

Для решения данного задания необходимо помнить, что:

• Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки.
• Алфавит – набор символов, используемых при кодировании.
• Мощность алфавита – количество символов в алфавите.
• Количество сообщений Q длиной в L знаков, которое можно получить из алфавита мощностью N, равно Q=NL
• Число возможных слов  N из L букв, когда есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., вычисляется как произведение

N = n1 · n2 ·  … · nL

Рассмотрим примеры решения различных задач по данной теме.

Задача 1.  Все 4-буквенные слова, составленные из букв С, Л, О, Н, записаны в алфавитном порядке. Вот начало списка:

         1. ЛЛЛЛ

         2. ЛЛЛН

         3. ЛЛЛО

         4. ЛЛЛС

……

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

Решение.  Пронумеруем буквы в порядке их следования в алфавите цифрами от 0 до 3:

                    Л = 0,  Н = 1, О = 2, С = 3

и запишем заданное нам начало списка этими цифрами:

        1. 0000

        2. 0001

        3. 0002

        4. 0003

        ……

Очевидно, что получили числа в четверичной системе счисления, записанные в порядке возрастания. Очень важно, что число ноль стоит на первом месте. Тогда далее на каждом месте будет стоять число, на 1 меньшее номера слова. Значит, на 250-м месте от начала списка будет находиться число 249, но записанное в четверичной системе счисления:

          249 = 33214

Заменив обратно цифры на буквы, получаем:  ССОН

Проверка решения. При желании можно получить ответ, решив задачу с конца списка.

Всего в данной задаче возможно получить 44 = 256 вариантов различных слов. Запишем полученные слова с конца: 255 = СССС, 254 = СССО, 253 = СССН, 252 = СССЛ, 251 =ССОС, 250 =ССОН – что и требовалось доказать. Или же для проверки выполните обратный перевод числа в десятичную систему счисления.

Ответ: ССОН

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

         1. ААААА

         2. ААААЛ

         3. ААААС

         4. ААААУ

         5. АААЛА

……

Укажите номер слова УЛАСА.

Решение.   Нумеруем буквы в порядке их следования в алфавите цифрами от 0 до 3, получаем:   А = 0, Л = 1, С = 2, У = 3, тогда получаем число 31020 в четверичной системе счисления. После перевода его в десятичную систему счисления получаем

                 310204  = 840.

Значит, искомое нами число занимает 840 +1 = 841 место.

Ответ: 841

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

Решение.   Всего из 4 различных букв можно составить 44  = 256 вариантов различных слов длиной четыре.

Но так как слова должны начинаться только с согласной буквы (здесь их 2  из четырех), полученных слов будет

256 / 2 = 128 вариантов.

Ответ: 128

Задача 4.  Сколько существует различных символьных последовательностей длины 5 в трёхбуквенном алфавите {Т, О, К}, которые содержат ровно две буквы О?

Решение.  Общее количество слов, которое можно составить из 3 букв длиной 5, равно

                     35 =  243 варианта.

Рассмотрим варианты пятибуквенных слов, в которых буква О стоит в разных позициях:

ОО***     О*О**      О**О*      О***О  -  4 шаблона, где звездочками обозначены 23  = 8 вариантов слов, которые можно составить из двух оставшихся букв (Т и К). Тогда получаем  здесь  всего  4 * 8 = 32 варианта;

*ОО**      *О*О*      *О**О   -  3 шаблона, которые дают 3 * 8 = 24 варианта слов;

**ОО*      **О*О  - 2 шаблона, которые дают  2 * 8 = 16 вариантов;

***ОО   = 1 шаблон, который дает  8  вариантов слов.

Тогда всего получаем 32 + 24 + 16 + 8 = 80 вариантов слов с двумя буквами О.

Ответ: 80

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

Решение.  Так как по условию буква У встречается в слове хотя бы один раз, то  

рассчитаем количество слов, в которых буква У встречается все пять раз

и вычтем случаи, когда буква У не встречается ни разу.

В первом случае, когда буква У используется на всех 5 позициях, получаем

               5 * 5 * 5 * 5 *5 = 3125 вариантов.

Во втором случае буква У не используется совсем, то есть используются только 4 буквы:

               4 * 4 * 4 * 4 * 4 = 1024

Тогда разница между ними и даст нам требуемый результат:  3125 – 1024 = 2101

Ответ: 2101

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

Решение.   Всего здесь возможно получить 45  = 1024 слова, но есть ограничение – одна из букв не может использоваться более 3 раз. При этом, буква использоваться 5 раз может только в единственном случае.

Когда же буква используется 4 раза, то возможны варианты:

    Е Е Е Е *,    Е Е Е * Е ,     Е Е * Е Е ,  Е * Е Е Е   и   * Е Е Е Е  –  всего  5 шаблонов, где на месте звездочки может быть любая из трех оставшихся букв, то есть всего 15 вариантов.   Значит,  всего не может быть  использовано 15 + 1 = 16 вариантов.

Тогда возможное количество слов при заданном условии будет 1024 – 16 = 1008 слов.

Ответ: 1008