Привет, ты находишься на канале TeachYou. Меня зовут Елена и здесь мы разбираем задачи для ЕГЭ-2023 по информатике. Обязательно подпишись на канал, чтобы не пропустить новые разборы!
Что будет в этой статье
Задание 8 ЕГЭ по информатике можно разбить на два типа. Задачи первого типа (на комбинаторику) мы разобрали здесь. В этой статье разберем задачи со списками слов.
- Тут не будет теории. И почти не будет картинок (вам же нравятся мои картинки? Можете написать в комментариях похвалу или конструктивную критику ☺).
- Разберем три задачи и убедимся, что они практически одинаковые. Тут даже запоминать ничего не надо, для решения этих задач нужна лишь капелька понимания, что в них происходит. И фиксирование основных моментов!)
- Дам подборку задач для самостоятельного разбора.
Почти все задачи я беру с сайта К. Полякова. Мне нравится, что он постоянно обновляется и там вовремя появляются актуальные задачи. Номера задач и ссылки на странички с ними я указываю.
Задача 1
Условие:
(№ 5086) (Досрочный ЕГЭ-2022) Все 5-буквенные слова, составленные из букв слова ПАРУС записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ААААА
2. ААААП
3. ААААР
4. ААААС
5. ААААУ
6. АААПА
...
Укажите номер первого слова в списке, начинающегося на У, в котором две буквы А не стоят рядом?
Решение:
Что происходит в задаче?
Приведенные списки слов похожи на упорядоченные списки чисел, дополненные незначащими нулями до пяти разрядов. Смотрите:
1. 00000
2. 00001
3. 00002
4. 00003
5. 00004
6. 00005
...
Похоже?
Самые внимательные могут провести соответствие между списками и увидеть, что A - 0, П - 1, Р - 2, С - 3, У - 4. Но в шестом элементе списка соответствие пропадает: слову АААПА в приведенном списке чисел соответствует 00005, хотя по установленному выше правилу должно быть 00010. Значит, число 00005 было написано неверно, а правильный список цифр такой:
1. 00000
2. 00001
3. 00002
4. 00003
5. 00004
6. 00010
...
Что это за список? Это упорядоченные по возрастанию числа, записанные в пятеричной системе счисления (пятеричной - потому что для их записи используется пять цифр: 0, 1, 2, 3, 4).
Внезапный вопрос: почему человечество в подавляющем большинстве своём использует десятеричную систему счисления? Пишите догадки в комментариях 😉
После того, как мы разобрались с глубингым смыслом списка слов из условия, можно перефразировать вопрос. "Укажите номер первого слова в списке, начинающегося на У, в котором две буквы А не стоят рядом?" = "Назовите номер первого слова, соответствующего пятизначному пятеричному числу, начинающегося с цифры 4, в котором два нуля не стоят рядом". Понятно, что первое слово будет соответствовать минимальному числу, для которого будет выполняться озвученные условия.
Подбираем такое число. Оно имеет вид 4****. Минимальное число, начинающееся с 4, это 40000. Но в нем стоят рядом аж четыре нуля. Нужно их разбавить какой-то другой цифрой, которая позволит получить наименьшее число - единицей. Точнее, двумя единицами. Имеем варианты 41010 и 40101. Выбираем то, которое меньше - 40101.
Номер в списке - это десятичное число, а 40101 - пятеричное. Переведем его в десятичную систему:
43210 - это степени
40101_5 = 4*5^4 + 1*5^2 + 1*5^0 = 4*625 + 1*25 + 1 = 2526_10
Ищем его номер в списке.
Давайте я еще раз приведу список и мы допишем, какому десятичному числу соответствует каждое число из него:
1. 00000 - 0
2. 00001 - 1
3. 00002 - 2
4. 00003 - 3
5. 00004 - 4
6. 00010 - 5
Видим, что номер числа (слова) - это его значение плюс единица. Значит, номер слова, соответствующего числу 2526, будет равен 2526 + 1 = 2527.
Ответ: 2527.
Задача 2
Условие:
(№ 3537) (Е. Джобс) Стасик выписывает все шестисимвольные комбинации, составленные из букв А, Б, Г, О, Щ. При этом упорядочивая их в обратном алфавитном порядке. Вот начало списка:
1. ЩЩЩЩЩЩ
2. ЩЩЩЩЩО
3. ЩЩЩЩЩГ
4. ЩЩЩЩЩБ
5. ЩЩЩЩЩА
6. ЩЩЩЩОЩ
...
Определите номер слова ОБЩАГА в этом списке.
Решение:
Опираясь на опыт решения предыдущей задачи, зафиксируем некоторые моменты:
- Рассматриваются шестизначные числа,
- записанные в пятеричной системе счисления.
- Нужно выяснить, какое число соответствует слову ОБЩАГА
- и найти его номер.
Сначала записываем соответствие между буквами и цифрами (на бумаге это удобно делать табличкой):
- Щ - 0, О - 1, Г - 2, Б - 3, А - 4.
- Теперь записываем слово ОБЩАГА цифрами: ОБЩАГА = 130424. Это пятеричное число, не забываем!
Переводим в десятичную систему:
543210 - это я так степени возле разрядов выставляю
130424_5 = 1*5^5 + 3*5^4 + 4*5^2 + 2*5^1 + 4*5^0 = 3125 + 1875 + 100 + 10 + 4 = 5114_10.
3. Как и раньше, номер слова в списке на единицу больше, чем значение числа, соответствующего слову: 5114 + 1 = 5115.
Ответ: 5115
Несложно же? Самое главное - фиксировать важные моменты после прочтения условия.
Задача 3
Условие:
(№ 2789) (А.Н. Носкин) Петя составляет список из 5-буквенных слов, в состав которых входят только буквы А, О, У. Петя расположил слова в обратном алфавитном порядке. Вот начало списка:
1. УУУУУ
2. УУУУО
3. УУУУА
4. УУУОУ
...
Запишите слово, которое стоит в этом списке под номером 100.
Решение:
Фиксируем моменты:)))
- Рассматриваются пятизначные числа
- в троичной системе счисления.
- Нужно узнать, какое число соответствует слову под номером 100,
- перевести его в троичную систему счисления
- и записать буквами.
Если номеру 1 соответствует число 0, то номеру 100 будет соответствовать число 99.
Переводим 99 в троичную систему делением столбиком на 3. Так же, как переводим в двоичную, но делим на тройку.
Получаем 10200. Число пятизначное, как и требуется в условии (это важно! Если число получится, к примеру, четырехзначное, нужно будет поставить незначащий ноль).
Остается только записать это число буквами. У - 0, О - 1, А - 2. Получаем ОУАУУ.
Ответ: ОУАУУ
Домашка!
Сайт К. Полякова, номера 5427, 5087, 3538, 2783, 223, 217, 215.
Напоминалка
Если у вас возникают небольшие сложности с решением задач - пишите в комментариях, помогу. Со сложностями побольше можете обращаться в личку, договоримся об онлайн-занятии.
И если вам нравится моя подача материала, подпишитесь, пожалуйста, чтобы не потерять такой ценный источник информации 😄