Палиндром егэ информатика

Назовем натуральное число палиндромом, если в его десятичной записи все цифры расположены симметрично (совпадает первая и последняя цифры, вторая и предпоследняя, и т. д. Например, числа 121 и 123321 являются палиндромами.

а)  Приведите пример числа‐палиндрома, которое делится на 15

б)  Сколько существует пятизначных чисел‐палиндромов, делящихся на 15?

в)  Найдите 37‐е по величине число‐палиндром, которое делится 15.

Решение.

Чтобы число делилось на 15, оно должно делиться на 5 и на 3. Для делимости на 5 оно должно кончаться на 5 (или на 0, но для палиндромов это невозможно). Дляделимости на 3 его сумма цифр должна быть кратна

а)  Например, 525.

б)  Пусть это число Тогда кратно 3. Изучим остатки цифр a и b от деления на 3.

Если то причем можно сочетать любые варианты.

Если то причем можно сочетать любые варианты.

Если то причем можно сочетать любые варианты.

Значит, всего этих чисел

в)  Трехзначные числа бывают только такие  — Четырехзначные  — только такие  — Значит, всего Среди не более чем пяизначных чисел есть палиндромов. Осталось отсчитать третий с конца. Очевидно это число вида поэтому

Ответ: а) 525; б) 33; в) 59295.

Сумма-палиндром

Хотите готовиться со мной к ЕГЭ?
Пишите:  ydkras@mail.ru
Немного обо мне.

Рассмотрим следующую задачу для подготовки к ЕГЭ с сайта К.Полякова (задача 25, вариант 1):

(№ 4410) (Л. Шастин) Среди чисел, больших 520000, найти такие, сумма
всех делителей которых, не считая единицы и самого числа, образует
число-палиндром (например, число 1221: если его «перевернуть»,
получается то же самое число). Вывести первые пять чисел,
удовлетворяющих вышеописанному условию, справа от каждого числа вывести
его максимальный делитель.  

Получить список делителей числа можно с помощью функции divisors, описанной в статье «Разложение на множители и простые числа».

Как определить, является ли число палиндромом? Наверно, самый короткий способ — преобразовать число в символьную строку и проверить строку «на палиндромность». Самое простое — сравнить исходную строку с «перевернутой задом наперед». В Питоне получить из некой строки s перевернутую строку очень просто: s[::-1]. (Если в операции получения подстроки записаны три параметра, то третий параметр — это шаг. С его помощью можно получить, например, каждый второй или каждый третий символ, а можно и перевернуть строку.)

Для пишущих на других языках приведу функцию, которая проверяет, является ли строка палиндромом (эта функция легоко реализуется на паскале или С++). Создадим пустую строку и будем присоединять к её началу поочередно символы исходной строки. Мы получим строку «задом наперед». Если она равна исходной строке, то наша строка — палиндром.

Вот текст функции

def palindrom(s):
    t=»
    for i in range(len(s)): t=s[i]+t  
    return s==t 

Основная программа очень проста. По очереди раскладываем числа 520001, 520002 и т.д. на множители, вычисляем их сумму. Если сумма — палиндром, то печатаем число и его наибольший множитель. В переменной k мы подсчитываем количество найденных чисел. Когда будет найдено пять чисел, цикл завершается.

Для преобразования числа в символьную строку используем функцию Питона str, для суммирования элементов массива — функцию sum и для поиска максимального элемента массива — функцию max.

Приведем полный текст программы:

Условие len(d) > 0 нужно для того, чтобы убедиться, что массив
делителей не пустой. (Если массив пустой, то функция sum выдаст 0, он
будет преобразован в строку «0», которая, очевидно, является
палиндромом, а при попытке найти в пустом массиве наибольший элемент
возникнет ошибка выполнения. Проверка len(d)> 0 исключает подобные неприятности.)

Результат выполнения программы следующий:

520211 16781
520993 47363
521653 47423
521947 16837
522077 22699

Он совпадает с приведенным на сайте ответом.

Программа выполняется очень быстро (десятые доли секунды).

(c) Ю.Д.Красильников, 2021-2022 г.

ЕГЭ – 2021, задание 8. Кодирование данных, комбинаторика

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

• Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки.

• В русском языке 33 буквы: 10 гласных букв (а, у, о, ы, и, э, я, ю, ё, е), 21 согласная буква (б, в, г, д, ж, з, й, к, л, м, н, п, р, с, т, ф, х, ц, ч, ш, щ) и два знака (ь, ъ).

• Алфавит – набор символов, используемых при кодировании.

• Мощность алфавита – количество символов в алфавите.

• Число возможных слов Q длиной в L букв, когда есть m₁ вариантов выбора первой буквы, m₂ вариантов выбора второй буквы и т.д., вычисляется как произведение

Q = m₁ * m₂ * … * m_L

• Тогда количество сообщений Q длиной в L букв, которое можно получить из алфавита мощностью М, при равном количестве вариантов выбора для всех букв равно

Q=М^L

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

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1 (демо-2021). Демоверсия 2020

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

Решение:

Для составления трехбуквенных слов (то есть слов длиной 3 буквы) используется алфавит мощностью пять букв. Здесь отдельное условие выбора указано только для буквы К, для остальных четырех букв алфавита (обозначим их символами х) – выбор одинаковый и равен 4² = 16.

При этом буква К может стоять на любом из трех мест в слове, тогда возможны три варианта слов: Кхх, хKх, ххК. Тогда общее количество вариантов слов будет

Q = 3 * 16 = 48

Ответ: 48

Задача 2.

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

Решение.

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

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

Ответ: 128

Задача 3.

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

Решение.

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

3⁵ = 243 варианта.

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

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

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

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

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

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

Ответ: 80

Задача 4.

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

Решение.

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

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

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

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

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

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

4 * 4 * 4 * 4 * 4 = 1024

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

Ответ: 2101

Задача 5.

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

Решение.

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

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

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

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

Ответ: 1008

Задача 6. Илья составляет 3-буквенные слова из букв К, Л, М, Н, О, Я. Буква Я в слове может быть только одна (или ни одной) и только на первой или последней позициях. Сколько различных кодовых слов может составить Илья?

Решение.

Максимальное число различных слов, которое можно получить в этой задаче, равно 6³ = 216 вариантов.

При этом возможны только следующие шаблоны:

* * *, Я * * и * * Я — всего 3 шаблона,

где на месте звезд могут быть в первом случае — 5 букв (без Я), то есть 5³ = 125 вариантов,

во втором и третьем случае – 5² = 25 * 2 = 50 вариантов. Итого возможно получить

125+50 = 175 вариантов различных слов.

Ответ: 175

Задача 7. Палиндром – это символьная строка, которая читается одинаково в обоих направлениях. Сколько различных 4-символьных палиндромов можно составить из строчных латинских букв? (В латинском алфавите 26 букв).

Решение.

4-символьный палиндром состоит из пары двух одинаковых букв, тогда общее количество таких возможных палиндромов будет 26² = 676 вариантов.

Ответ: 676

Задача 8. Все 6-буквенные слова, составленные из букв М, А, К записаны в алфавитном порядке. Вот начало списка:

1. АААААА

2. АААААК

3. АААААМ

4. ААААКА

5. ААААКК

……

Запишите номер первого слова, которое начинается на букву М.

Решение.

Данный список будет состоять из трех равных частей, каждая из которых будет содержать 3⁶ / 3 = 243. Тогда третья часть начнется со строки под номером 243 * 2 + 1 = 487.

Ответ: 487

Задача 9.

Иннокентий составляет семибуквенные слова из букв Е, И, Й, К, Н, О,

Т. Сколько слов может составить Иннокентий, если известно, что в каждом из них есть комбинация КОТ?

Решение:

Подвох в условии этой задачи в том, что не сказано, что комбинация КОТ встречается только один раз!

Тогда сначала посчитаем общее число возможных комбинаций, в которых слово кот встречается только один раз, и вычтем из этого количества те, где комбинация повторяется дважды.

Всего возможны варианты:

КОТхххх, хКОТххх, ххКОТхх, хххКОТх, ххххКОТ, где х – одна из четырех оставшихся букв, то есть 5 * 7⁴ = 12005

Второй раз комбинация КОТ может встретиться в четвертом и пятом варианте, причем в пятом варианте – дважды:

КОТКОТх , КОТхКОТ и хКОТКОТ.

В каждом случае остается свободной одна позиция из семи различных букв, то есть три раза по 7 вариантов букв – итого 21.

Итого получаем: 12005 – 21 = 11984.

Ответ: 11984

Задача 10

Василий составляет 4-буквенные коды из букв Г, А, Ф, Н, И, Й. Каждую букву можно использовать любое количество раз, при этом код не может начинаться с буквы Й и должен содержать хотя бы одну гласную. Сколько различных кодов может составить Василий?

Решение:

Решим задачу с конца, так как решение с начала – на много длиннее. Для этого мы сосчитаем, сколько вариантов кодов может быть всего (без учета заданных ограничений) и вычтем количество кодов, которых быть не может.

В данном задании мощность алфавита М = 6, длина получаемых кодов L = 4 то есть общее возможное количество вариантов слов (без учета ограничений на использование букв) равно Q = 64 = 1296. Напомним, что буква Й – согласная, т.е. в используемом в задаче алфавите четыре согласных и две гласных буквы.

Не может быть кодов, которые начинаются на Й, их количество

Q = 1(Й) *6 *6 *6 =216

Также не может быть кодов, в которых нет ни одной гласной буквы, их количество Q = 3 *4 *4 *4 =192.

Тогда остается возможных кодов 1296-216-192 = 888.

Ответ: 888

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

1. ЛЛЛЛ

2. ЛЛЛН

3. ЛЛЛО

4. ЛЛЛС

……

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

Решение.

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

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

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

1. 0000

2. 0001

3. 0002

4. 0003

……

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

249 = 3321₄

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

Проверка решения.

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

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

Ответ: ССОН

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

1. ААААА

2. ААААЛ

3. ААААС

4. ААААУ

5. АААЛА

……

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

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

31020₄ = 840.

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

Ответ: 841

Продолжаем разбирать задачки с сайта Leetcode. В прошлый раз было про массив и сумму чисел, теперь тоже необычное. 

Условия

В переменной X лежит какое-то целое число

Задача — проверить, является ли это число палиндромом.

Задача со звёздочкой — проверить на наличие палиндрома, не используя строки.

Палиндром — это когда строка или число одинаково читается в прямом и обратном направлении:

121 — это палиндром.

А роза упала на лапу Азора — тоже палиндром (если не считать заглавных букв).

12321 — и это палиндром.

Решение, где используем строки

Самый простой способ проверить, число в переменной палиндром или нет, — преобразовать его в строку, выставить знаки задом наперёд и сравнить с оригиналом. Этим мы сразу решаем проблему отрицательных чисел, когда «−121»превращается в «121−» и сразу становится ясно, что это не палиндром.

Сначала решим это на Python. Тут вообще суть в одной строке:

X = 121
if str(X) == str(X)[::-1]:
    print("Это палиндром")
else:
    print("Это не палиндром")

Здесь мы использовали трюк с переворачиванием строки без её изменения — применили конструкцию [::-1]. Работает это так:

Мы уже делали похожие штуки, когда писали свой генератор новых слов, но там было одно двоеточие, а здесь два.

Теперь решим это же, но на JavaScript:

var X = 121;
if (X.toString().split("").reverse().join("") == X.toString()) {
    console.log("Это палиндром")
} else {
    console.log("Это не палиндром")
}

Здесь мы использовали другой метод пересборки:

Решение без строк

Тем, кто справился с первой частью, предлагают задачу со звёздочкой — сделать то же самое, но не используя строки, а работая только с числами. Попробуем и мы.

Сделаем в JavaScript функцию, которая будет возвращать true, если в переменной лежит палиндром, и false — если нет. Всё остальное будем писать внутри этой функции:

function palindrome(x) {
}

Теперь обработаем три стандартные ситуации:

Запишем это на JavaScript:

function palindrome(x) {
    // если перед нами ноль — это палиндром
    if(x == 0) {
        return true;
    }
    // если число меньше нуля или делится на 10 без остатка — это не палиндром
    if(x < 0 || x%10 == 0){
        return false;
    }
}

Чтобы проверить, является ли число палиндромом или нет, можно сделать так: отрезаем от числа цифры справа по одной, добавляем их в начало нового числа и постоянно сравниваем новое и старое значение. Если они станут равны — перед нами палиндром. Читайте комментарии, чтобы вникнуть в то, что происходит в коде:

function palindrome(x) {
    // если перед нами ноль — это палиндром
    if(x == 0) {
        return true;
    }
    // если число меньше нуля или делится на 10 без остатка — это не палиндром
    if(x < 0 || x%10 == 0){
        return false;
    }
    // сюда будем собирать число в обратном порядке
    temp = 0;
    // а тут будем хранить промежуточные значения икса
    preX = x;
    // пока не дойдём до середины числа — повторяем цикл
    while (x > temp) {
        // берём самую правую цифру в числе — это остаток от деления на 10
        pop = x%10;
        // запоминаем старое значение переменной X
        preX = x;
        // и отрезаем от переменной последнюю цифру — делаем это через целую часть деления на 10
        x /= 10;
        // добавляем отрезанную цифру к обратной переменной
        temp = temp*10 + pop;
    }
    // если обратная переменная совпала с оставшейся половиной исходной переменной — это палиндром
    // мы добавляем сравнение с предыдущей версией исходной половины (которая на 1 цифру больше) на тот случай, если исходное число состояло из нечётного количества символов и его нельзя было бы разбить строго пополам
    if(x == temp || preX == temp)
        return true;
    // 
    else
        return false;
};

Для запуска кода просто вызываем функцию и передаём её нашу переменную:

// запускаем код
var X = 121;
console.log(palindrome(X));

Чтобы попрактиковаться, попробуйте сделать такое же, но на Python и не подглядывая в наш код.

За это задание ты можешь получить 1 балл. На решение дается около 30 минут. Уровень сложности: повышенный.
Средний процент выполнения: 52.2%
Ответом к заданию 24 по информатике может быть развернутый ответ (полная запись решения с обоснованием выполненных действий).

Задачи для практики

f = open('24_ABD.txt', 'r')
s = f.readline().strip()
s1 = s.replace('BD', 'B D')
s2 = s.replace('BA', 'B A')
x = s1.split()
y = s1.split()
max_not_bd = len(max(x, key=len))
max_not_ba = len(max(y, key=len))
print(max(max_not_ba, max_not_bd))

f = open('24_ABD.txt', 'r')
s = f.readline().strip()
max_len = 0
cur_len_notBA = 1
cur_len_notBD = 1
for i in range(len(s) - 1):
    if s[i] == 'B' and s[i + 1] == 'A':
        cur_len_notBA = 1
        cur_len_notBD += 1
    elif s[i] == 'B' and s[i + 1] == 'D':
        cur_len_notBA += 1
        cur_len_notBD = 1
    else:
        cur_len_notBA += 1
        cur_len_notBD += 1
    max_len = max(max_len, cur_len_notBA, cur_len_notBD)
print(max_len)

f = open('24_ABD.txt', 'r')
s = f.readline().strip()
max_s = 0
k = 0
for i in range(len(s)):
    if s[i] != 'B':
        k += 1
        max_s = max(k, max_s)
    else:
        k = 0
print(max_s)

f = open('24_ABD.txt', 'r')
s = f.readline().strip()
s = s.replace('B', ' ')
x = s.split()
print(len(max(x, key=len)))

f = open('24_4.txt', 'r')
s = f.readline().strip()
bd = s.count('BD')
ba = s.count('BA')
if bd > ba:
    print(f'{bd}BD')
else:
    print(f'{ba}BA')

f = open('24.txt', 'r')
s = f.readline().strip()
s = s.replace('BD', '1')
s = s.replace('BA', '2')
x1 = s.replace('A', '2')
x1 = x1.replace('B', '2')
x1 = x1.replace('D', '2')
x2 = s.replace('A', '1')
x2 = x2.replace('B', '1')
x2 = x2.replace('D', '1')
x = x1.split('2')
max_s = len(max(x, key=len))
x = x2.split('1')
max_s = max(max_s, len(max(x, key=len)))
print(max_s)

f = open('24.txt', 'r')
s = f.readline().strip()
s = s.replace('BD', '1')
s = s.replace('BA', '2')
s = s.replace('A', ' ')
s = s.replace('B', ' ')
s = s.replace('D', ' ')
x = s.split()
print(len(max(x, key=len)))

f = open('24.txt', 'r')
s = f.readline().strip()
s = s.replace('BD', '1')
s = s.replace('BA', '2')
s = s.replace('A', ' ')
s = s.replace('B', ' ')
s = s.replace('D', ' ')
x = s.split()
print(len(max(x, key=len)))

#include <iostream>
#include <fstream>
using namespace std;
int main() {
    ifstream file("Задание 24 (ABCD3).txt");
    if (file.is_open()){
        string text;
        file >> text;
        int maxCount = 0, currentCount = 1;
        for (int i = 1; i < text.length(); ++i) {
            if (text[i - 1] == text[i]) {
                currentCount += 1;
                if (currentCount > maxCount)
                    maxCount = currentCount;
            } else
                currentCount = 1;
        }
        cout << maxCount;
    } else {
        cout << "File isn not opened.";
    }
    return 0;
}

#include <iostream>
#include <fstream>
using namespace std;
int main() {
    ifstream file("D:\DOWNLOADS\num3.txt");
    int count = 0;
    if (file.is_open()){
        string text;
        file >> text;
        for (int i = 3; i < text.length(); ++i)
            if ((text[i - 3] != text[i - 2])
                && (text[i - 2] != text[i - 1])
                && (text[i - 1] != text[i]))
                count++;
        cout << count;
    } else cout << "File is not opened.";
    return 0;
}

f = open("file.txt")
st = f.read()
f.close()
count = 0
prev1 = "Z"
prev2 = "Z"
for x in st:
    if prev2 == "C" and prev1 == "A" and x == "B":
        count += 1
    prev2 = prev1
    prev1 = x
print(count)

#include <iostream>
#include <fstream>
using namespace std;

int main() {
    ifstream file("D:\YandexDisk\YandexDisk\ДОКУМЕНТЫ\РЕПЕТИТОР\ТУРБОПОДГОТОВКА\Файлы для задач\№24\Задание 24 (ABC1).txt");
    if (file.is_open()){
        string text;
        file >> text;
        int count = 0;
        for (int i = 2; i < text.length(); ++i){
            if (text[i - 2] == 'C' && text[i - 1] == 'A' && text[i] == 'B')
                count++;
        }
        cout << count;
    } else cout << "File is not opened.";
    return 0;
}

#include <iostream>
#include <fstream>
using namespace std;
bool check(string text){
    for (int i = 0; i < text.length() - 1; i++)
        for (int j = i + 1; j < text.length(); j++)
            if (text[i] == text[j])
                return false;
    return true;
}
int main() {
    ifstream file("D:\DOWNLOADS\num4.txt");
    int count = 0;
    if (file.is_open()){
        string text;
        file >> text;
        for (int i = 3; i < text.length(); ++i)
            if ((text[i - 3] != text[i - 2])
                && (text[i - 3] != text[i - 1])
                && (text[i - 3] != text[i])
                && (text[i - 2] != text[i - 1])
                && (text[i - 2] != text[i])
                   && (text[i - 1] != text[i]))
//            if(check(text.substr(i - 4, 4)))
                count++;
        cout << count;
    } else cout << "File is not opened.";
    return 0;
}

#include <iostream>
#include <fstream>
using namespace std;
int main() {
    ifstream file("D:\DOWNLOADS\num5.txt");
    int count = 0;
    if (file.is_open()){
        string text;
        file >> text;
        for (int i = 3; i < text.length(); ++i){
            if ((text[i - 3] == text[i])
                && (text[i - 2] == text[i - 1]))
                count++;
            if (text[i - 2] == text[i])
                count++;
        }
        cout << count;
    } else cout << "File is not opened.";
    return 0;
}

f = open("file.txt")
max_len = 0
cur_len = 0
st = f.read()
pred_x = "X"
for x in st:
    if ((x == pred_x and cur_len > 0) or
            (x == "B" and pred_x == "A")
            or (x == "C" and pred_x == "B" and cur_len > 0)):
        cur_len += 1
    else:
        if x == "A":
            cur_len = 1
        else:
            cur_len = 0
    if x == "C" and cur_len > max_len:
        max_len = cur_len
    pred_x = x
print(max_len)
f.close()

#include <iostream>
#include <fstream>
using namespace std;
int main(){
    ifstream file ("file.txt");
    string text;
    file >> text;
    int maxLength = 0, curLength = 1;
    for (int i = 1; i < text.length(); ++i) {
        if (text[i-1] <= text[i]) {
            curLength++;
            if (curLength > maxLength)
                maxLength = curLength;
        } else
            curLength = 1;
    }
    cout << maxLength;
    return 0;
}

Сегодня на повестке дня 8 задание из ЕГЭ по информатике 2021. Данный тип заданий включает в себя нахождение количества вариантов, элементы комбинаторики и другие математические понятия.

Перейдём к практике решения задач задания 8 ЕГЭ по информатике 2021.

Задача (Классика)

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

1. АААА
2. АААЕ
3. АААИ
4. АААО
5. ААЕА
…

Запишите слово, стоящее на 248-м месте от начала списка.

Решение:

Обозначим условно А — 0, Е — 1, И — 2, О — 3.

Важно: Нужно буквам присваивать цифры именно в том порядке, в котором они идут в самом правом столбце, потому что буквы могут дать в «перепутанном порядке» (например Е, А, И, О), и тогда ничего не получится.

Теперь запишем список с помощью цифр.

1. 0000
2. 0001
3. 0002
4. 0003
5. 0010
…

Получился обычный счёт в четверичной системе!! (всего используются 4 цифры: 0, 1, 2, 3). А слева нумерация показывает соответствие нашей десятичной системе. Но все числа десятичной системы в этой таблице соответствия сдвинуты на 1, ведь мы должны были начать с нуля.

Нас просят записать слово стоящее на 248, т.е. если была обычная таблица соответствия чисел десятичной системы и четверичной системы, слово стоящее на 248 месте, находилось бы на 247 (248 — 1) месте. Значит, наше искомое четверичное число соответствует 247 в десятичной системе.

Переведём число 247 в четверичную систему!

Получилось число 3313₄ в четверичной системе. Сделаем обратное декодирование в буквы. Таким образом, ответ будет ООЕО.

Ответы: ООЕО

Ещё одна похожая задача 8 задания из примерных вариантов ЕГЭ по информатике, но другой вариации.

Задача (Классика, Другая вариация)

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

1. ААААА
2. ААААК
3. ААААР
4. ААААУ
5. АААКА
……
Укажите номер слова УКАРА

Решение:

Закодируем буквы цифрами: А — 0, К — 1, Р — 2, У — 3. Здесь как раз буквы даны не в том порядке, как они идут в самом правом столбце. Но мы должны кодировать именно в том порядке, как буквы идут в самом правом столбце.

У нас получилось четыре цифры! Значит снова можно слова превратить в таблицу соответствия между десятичной системой и четверичной системой. Но десятичная система смещена на 1 позицию.

1. 00000
2. 00001
3. 00002
4. 00003
5. 00010
……

Выписываем данное нам слово и посмотрим, какое число в четверичной системе было бы, если бы у нас были в место слов числа в четверичной системе!

Получили число в четверичной системе 31020₄. Узнаем, какое число в десятичной системе соответствовало этому числу, если бы была обычная таблица соответствия. Для этого переведём число 31020₄ из четверичной системы в десятичную. Перевод делаем по аналогии перевода из двоичной системы в десятичную.

Но помним, что у нас нумерация идёт на 1 быстрее, нежели мы бы поставили десятичные числа, как в таблице соответствия, потому что нумерация начинается не с нуля, а с 1. Поэтому к числу 840 нужно прибавить 1, и в ответе будет 841

Ответ: 841

Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)

Все 4-буквенные слова, в составе которых могут быть буквы Н, О, Т, К, И,
записаны в алфавитном порядке и пронумерованы, начиная с 1.
Ниже приведено начало списка.

1. ИИИИ
2. ИИИК
3. ИИИН
4. ИИИО
5. ИИИТ
6. ИИКИ
…

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

Решение:

Закодируем буквы цифрами.

Получилось 5 цифр ( 0, 1, 2, 3, 4 ), значит, будем работать в пятеричной системе.

Нужно найти номер первого слова, которое начинается с буквы О. Если говорить на языке пятеричных чисел, то нужно найти номер числа 3000₅. Мы «забиваем нулями», чтобы число было четырёхразрядное, т.к. слова 4-х буквенные. Именно нулями, потому что нужно именно первое слово найти.

Теперь, как в предыдущей задаче, переведём число 3000₅ из пятеричной системы в десятичную.

0 * 5 ⁰ + 0 * 5 ¹ + 0 * 5 ² +
3 * 5 ³ = 375 (в десят. системе)

Но опять же должны прибавить 1 к числу 375, т.к. нумерация отличается от десятичных чисел на 1 в большую сторону.

Ответ: 376

Задача (Досрочная волна 2020 ЕГЭ по информатике, вариант 1)

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

Решение:

Для начала решим вводную подзадачу.

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

Т.е буквы могут повторяться!

Например

Такая конструкция сильно напоминает перебор чисел, где вместо цифр используются буквы.

Рассмотрим перебор трёхразрядных чисел. Вместо 5 букв теперь можно использовать 10 цифр ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ). Цифры так же могут повторяться. Сколько получится вариантов ?

Выведем общую формулу для количества вариантов, когда символы могут повторяться!

Для трёхразрядных чисел от 000 до 999:

N = 10³ = 1000 вариантов.

Вернёмся к пятибуквенным словам и нашей подзадаче. Здесь количество букв (разрядов) в слове равно 5, количество допустимых символов равно 4 ( В, О, Л, К ).

N = 4⁵ = 1024 вариантов.

Вернёмся к изначальной задаче. Сначала найдём количество вариантов, когда буква В находится в самой левой ячейке!

Применим формулу! Здесь слово сократилось до четырёхразрядного. А количество букв для использования 3 (О, Л, К).

N = 3⁴ = 81 комбинация.

Но буква В так же может стоять во второй ячейке слева. Этот случай тоже даст 81 других комбинаций. Буква В может стоять в каждой из 5-ти ячеек, и везде будет получатся 81 комбинация.

Таким образом, окончательный ответ будет:

N = 81 * 5 = 405 различных вариантов.

Ответ: 405

Разобравшись с этой задачей, больше половины тренировочных задач десятого задания из различных книг и сайтов по подготовке к ЕГЭ по информатике будут решаться, как по маслу!

Задача(Закрепление формулы)

Рассматриваются символьные последовательности длины 5 в шестибуквенном алфавите {У, Ч, Е, Н, И, К}. Сколько существует таких последовательностей, которые начинаются с буквы У и заканчиваются буквой К?

Решение:

Применим главную формулу 8 задания из ЕГЭ по информатике

N = mⁱ = 6³ = 216

Здесь буквы могут изменяться на 3 ячейках! Значит, в формуле i=3. Количество допустимых символов, которые можно поставить в каждую ячейку равно 6. Значит, в формуле m=6.

В ответе будет 216.

Примечание: Здесь можно использовать все буквы в каждой ячейке, включая У и К. В некоторых задачах их уже использовать нельзя, т.е. сказано, что буквы У и К используются один раз в слове. Тогда в формуле m, будет на 2 единицы меньше. Нужно внимательно читать задачу!

Ответ: 216

Задача (Демонстрационный вариант ЕГЭ по информатике, 2019)

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

Решение:

Рассмотрим количество вариантов, когда гласная И стоит в первом месте!

Подсчитаем количество слов с помощью супер-формулы

N = mⁱ = 2⁴ = 16

Длина изменяющихся ячеек равна 4, а количество допустимых букв равно 2.

Но буква И может стоять не только на первом месте. Она так же может стоять и на 2, и на 3, и на 4, и на 5 месте. Каждый такое случай добавляет столько же новых слов.

Значит, при использовании только буквы И будет количество слов 16 * 5 = 80. Ещё столько же слов добавится, если в словах вместо буквы И будет использоваться буква А. Поэтому окончательный ответ будет 80 * 2 = 160

Ответ: 160

Отработаем главную формулу 8 задания из ЕГЭ по информатике.

Задача (Развиваем понимание формулы!)

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

Решение:

Рассмотрим, какие варианты могут быть, если у нас на первом месте стоит согласная, а на последнем месте гласная

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

N = mⁱ = 4³ = 64

Длина изменяющихся ячеек равна 3, а количество возможных букв 4.

Но т.к. таких случая у нас четыре, то ответ будет 4 * 64 = 256

Ответ: 256

Рассмотрим важнейший «метод умножения» при решении 8 задания из ЕГЭ по информатике.

Задача (Другой метод решения!!)

Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз , при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?

Решение:

Эта задача отличается от уже разобранных тем, что каждую букву можно использовать один раз. В этой задаче удобнее воспользоваться немного другим методом решения! «Методом умножения»!

Решим вводную подзадачу (без дополнительных ограничений).

Сколькими способами можно составить 6-x буквенное слово из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз .

Чтобы найти возможные варианты, перемножаем для каждой ячейки количество букв из которых у нас есть выбор!

N = 6 * 5 * 4 * 3 * 2 * 1 = 720

Вернёмся к изначальной задаче!

В начале подсчитаем «методом умножения» количество слов, не обращая внимание, на условие, в котором сказано, что слово не может содержать сочетание АЕ.

N = 5 * 5 * 4 * 3 * 2 * 1 = 600

В формуле стоят почти все те же самые числа, как и в вводном примере, только первый множитель не 6, а 5. Это произошло из-за того, что у нас в задаче слово не может начинаться на букву Й. Значит, выбор на первую позицию будет не из 6 букв, а из 5.

Но в 600 комбинаций входят и те случаи, когда в слове присутствует сочетание АЕ. Теперь найдём сколько таких слов, где присутствует сочетание АЕ

Узнаем количество вариантов в каждом таком случае.

N1 = 4 * 3 * 2 * 1 = 24

На первом месте мы не можем использовать букву Й, поэтому мы на первом месте выбираем из 3 букв.

N2 = 3 * 3 * 2 * 1 = 18

Аналогично предыдущему случаю.

N5 = 3 * 3 * 2 * 1 = 18

24 + 18 + 18 + 18 + 18 = 96

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

N = 600 — 96 = 504

Примечание: Метод умножения можно было использовать и в задачах, которые мы рассмотрели ранее. Например, в задаче «Закрепление формулы» в первой свободной ячейке выбираем из 6 букв, во второй свободной ячейке тоже из 6 букв, и в третий свободной ячейке тоже можно использовать 6 букв. Значит, по методу умножения получается N = 6 * 6 * 6 = 6³ = 216

Ответ: 504

Задача (Закрепления «метода умножения»)

Полина составляет 6-буквенные коды из букв П, О, Л, И, Н, А. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Полина?

Решение:

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

На первое место можно выбрать из 6 букв, предположим, мы выберем согласную. Тогда на второе место нужно выбирать из 3 гласных. Потом опять должна идти согласная, но их у нас осталось только 2. Далее, на следующее место выбираем из 2 гласных букв. И на предпоследнее место выбирается 1 согласная, а на последнее место остаётся 1 гласная.

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

N = 6 * 3 * 2 * 2 * 1 * 1 = 72

Ответ: 72

Задача (Азбука Морзе)

Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код Морзе длиной не менее трёх и не более четырёх сигналов (точек и тире) ?

Решение:

Зная формулу, без проблем решим данную примерную задачу из ЕГЭ по информатике.

У нас есть 2 символа, которые можно использовать: точка и тире. Фраза, что сообщение может иметь «не менее трёх и не более четырёх сигналов», означает, что сообщения могут быть длиною 3 символа и длиною 4 символа.

Подсчитаем общее количество вариантов.

N = 2³ + 2⁴ = 8 + 16 = 24 комбинаций.

Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?

Решение:

Нам нужно закодировать 300 различных вариантов! Имеются 4 различных лампочки! (Они имеют смысл, как количество допустимых символов!) На этот раз нужно узнать количество лампочек (количество разрядов, «длину слова»). Применяем формулу.

N = 4^x = 300

Не найдётся такое целое x, чтобы равенство стало верным. Поэтому берём целое минимальное x такое, чтобы 4^x больше 300.

4⁵ = 1024

Пять лампочек на табло хватит, чтобы закодировать 300 сигналов, но, к сожалению, много комбинаций просто не пригодится!

Ответ: 5

Задача (Важная!)

Нужно выбрать в подарок 3 книги из 5. Сколькими способами можно выбрать ?

Решение:

На рисунке показано две комбинации, как можно выбрать в подарок 3 книги из 5.

Данную задачку нужно решать используя формулу сочетаний из раздела комбинаторика.

n — количество книг, из которых мы выбираем подарок, m — количество книг, которое мы хотим выбрать, C — количество вариантов (способов).

Восклицательный знак — это факториал!

Факториалом числа «n» (условное обозначение n!- читается как «эн» — факториал) называется произведение чисел от 1 до «n»

Примечание: При использовании формулы сочетаний, не важен порядок, в котором мы выбираем одни и те же книги. Это будет один и тот же вариант.

Ответ: 10

Следующая задача часто встречается в книгах по подготовке к ЕГЭ по информатике.

Задача (Главная формула + сочетания)

Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 5. Сколько различных вариантов шифра можно задать, если известно, что цифра 1 встречается ровно три раза, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?

Решение:

В начале нужно посчитать, сколькими способами на 5-ти ячейках можно расположить 3 единицы!

Обратите внимание, как будто мы выбираем 3 книги в подарок из 5 возможных! Значит, опять применяем формулу сочетаний из комбинаторики. Мы вычисляли уже её точно с такими же числами в прошлой задаче, количество вариантов равно 10.

Подсчитаем, сколько вариантов кодового замка можно составить при одном определённом расположении трёх единиц.

Применим формулу, есть две ячейки, в которых изменяются цифры, а в каждой ячейке может быть одна из 4 цифр.

N = mⁱ = 4² = 16

Т.к. различных вариантов, как расположить единицы на 5 ячейках равно 10, то ответ будет 16 * 10 = 160

Ответ: 160

Ещё одна задача из примерных вариантов по подготовке к ЕГЭ по информатике.

Задача (Таблица соревнований)

Для записи результатов соревнований используется таблица, в которой для каждой из 20-ти команд по каждому из 10-ти видов состязаний записано 1, 2 или 3 (если команда заняла соответствующее место в этом состязании) или прочерк (если не заняла призовое место или не участвовала). Какое количество информации (бит) содержит таблица ?

Решение:

Есть таблица с 20 командами и для каждой команды есть результат по 10-ти видам состязаний.

В каждой ячейке может быть 4 различных значения ( 1, 2, 3, — ). Нужно узнать, сколько бит занимает одна ячейка таблицы. Один бит может быть либо единицей, либо нулём.

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

Как будто мы решаем задачу с перебором слов. Но здесь длина слова неизвестна, а количество вариантов, которое должно получится уже дано и равно 4 (четырём). Применим главную формулу из 10 задания из ЕГЭ по информатике.

Одна ячейка таблицы весит 2 бита. Найдём количество ячеек во всей таблице соревнований.

Всего ячеек = 20 * 10 = 200

Тогда вся таблица будет весит:

V = 2 бита * 200 = 400 бит.

Ответ: 400

Формула Шеннона

Задача (Формула Шеннона)

В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?

Решение:

Данную задачу нужно решать по формуле Шеннона

Найдём вероятность p того, что вытащили чёрный шарик.

Применим формулу Шеннона.

Ответ: 2

ЕГЭ – 2021, задание 8. Кодирование данных, комбинаторика

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

• Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки.

• В русском языке 33 буквы: 10 гласных букв (а, у, о, ы, и, э, я, ю, ё, е), 21 согласная буква (б, в, г, д, ж, з, й, к, л, м, н, п, р, с, т, ф, х, ц, ч, ш, щ) и два знака (ь, ъ).

• Алфавит – набор символов, используемых при кодировании.

• Мощность алфавита – количество символов в алфавите.

• Число возможных слов Q длиной в L букв, когда есть m₁ вариантов выбора первой буквы, m₂ вариантов выбора второй буквы и т.д., вычисляется как произведение

Q = m₁ * m₂ * … * m_L

• Тогда количество сообщений Q длиной в L букв, которое можно получить из алфавита мощностью М, при равном количестве вариантов выбора для всех букв равно

Q=М^L

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

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1 (демо-2021). Демоверсия 2020

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

Решение:

Для составления трехбуквенных слов (то есть слов длиной 3 буквы) используется алфавит мощностью пять букв. Здесь отдельное условие выбора указано только для буквы К, для остальных четырех букв алфавита (обозначим их символами х) – выбор одинаковый и равен 4² = 16.

При этом буква К может стоять на любом из трех мест в слове, тогда возможны три варианта слов: Кхх, хKх, ххК. Тогда общее количество вариантов слов будет

Q = 3 * 16 = 48

Ответ: 48

Задача 2.

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

Решение.

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

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

Ответ: 128

Задача 3.

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

Решение.

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

3⁵ = 243 варианта.

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

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

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

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

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

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

Ответ: 80

Задача 4.

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

Решение.

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

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

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

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

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

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

4 * 4 * 4 * 4 * 4 = 1024

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

Ответ: 2101

Задача 5.

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

Решение.

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

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

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

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

Ответ: 1008

Задача 6. Илья составляет 3-буквенные слова из букв К, Л, М, Н, О, Я. Буква Я в слове может быть только одна (или ни одной) и только на первой или последней позициях. Сколько различных кодовых слов может составить Илья?

Решение.

Максимальное число различных слов, которое можно получить в этой задаче, равно 6³ = 216 вариантов.

При этом возможны только следующие шаблоны:

* * *, Я * * и * * Я — всего 3 шаблона,

где на месте звезд могут быть в первом случае — 5 букв (без Я), то есть 5³ = 125 вариантов,

во втором и третьем случае – 5² = 25 * 2 = 50 вариантов. Итого возможно получить

125+50 = 175 вариантов различных слов.

Ответ: 175

Задача 7. Палиндром – это символьная строка, которая читается одинаково в обоих направлениях. Сколько различных 4-символьных палиндромов можно составить из строчных латинских букв? (В латинском алфавите 26 букв).

Решение.

4-символьный палиндром состоит из пары двух одинаковых букв, тогда общее количество таких возможных палиндромов будет 26² = 676 вариантов.

Ответ: 676

Задача 8. Все 6-буквенные слова, составленные из букв М, А, К записаны в алфавитном порядке. Вот начало списка:

1. АААААА

2. АААААК

3. АААААМ

4. ААААКА

5. ААААКК

……

Запишите номер первого слова, которое начинается на букву М.

Решение.

Данный список будет состоять из трех равных частей, каждая из которых будет содержать 3⁶ / 3 = 243. Тогда третья часть начнется со строки под номером 243 * 2 + 1 = 487.

Ответ: 487

Задача 9.

Иннокентий составляет семибуквенные слова из букв Е, И, Й, К, Н, О,

Т. Сколько слов может составить Иннокентий, если известно, что в каждом из них есть комбинация КОТ?

Решение:

Подвох в условии этой задачи в том, что не сказано, что комбинация КОТ встречается только один раз!

Тогда сначала посчитаем общее число возможных комбинаций, в которых слово кот встречается только один раз, и вычтем из этого количества те, где комбинация повторяется дважды.

Всего возможны варианты:

КОТхххх, хКОТххх, ххКОТхх, хххКОТх, ххххКОТ, где х – одна из четырех оставшихся букв, то есть 5 * 7⁴ = 12005

Второй раз комбинация КОТ может встретиться в четвертом и пятом варианте, причем в пятом варианте – дважды:

КОТКОТх , КОТхКОТ и хКОТКОТ.

В каждом случае остается свободной одна позиция из семи различных букв, то есть три раза по 7 вариантов букв – итого 21.

Итого получаем: 12005 – 21 = 11984.

Ответ: 11984

Задача 10

Василий составляет 4-буквенные коды из букв Г, А, Ф, Н, И, Й. Каждую букву можно использовать любое количество раз, при этом код не может начинаться с буквы Й и должен содержать хотя бы одну гласную. Сколько различных кодов может составить Василий?

Решение:

Решим задачу с конца, так как решение с начала – на много длиннее. Для этого мы сосчитаем, сколько вариантов кодов может быть всего (без учета заданных ограничений) и вычтем количество кодов, которых быть не может.

В данном задании мощность алфавита М = 6, длина получаемых кодов L = 4 то есть общее возможное количество вариантов слов (без учета ограничений на использование букв) равно Q = 64 = 1296. Напомним, что буква Й – согласная, т.е. в используемом в задаче алфавите четыре согласных и две гласных буквы.

Не может быть кодов, которые начинаются на Й, их количество

Q = 1(Й) *6 *6 *6 =216

Также не может быть кодов, в которых нет ни одной гласной буквы, их количество Q = 3 *4 *4 *4 =192.

Тогда остается возможных кодов 1296-216-192 = 888.

Ответ: 888

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

1. ЛЛЛЛ

2. ЛЛЛН

3. ЛЛЛО

4. ЛЛЛС

……

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

Решение.

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

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

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

1. 0000

2. 0001

3. 0002

4. 0003

……

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

249 = 3321₄

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

Проверка решения.

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

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

Ответ: ССОН

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

1. ААААА

2. ААААЛ

3. ААААС

4. ААААУ

5. АААЛА

……

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

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

31020₄ = 840.

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

Ответ: 841