Публикации Комбинаторные задачи из ЕГЭ по информатике

Всероссийский сборник статей и публикаций института развития образования, повышения квалификации и переподготовки.

Язык издания: русский
Периодичность: ежедневно
Вид издания: сборник
Версия издания: электронное сетевое
Публикация: Комбинаторные задачи из ЕГЭ по информатике
Автор: Беспалова Виктория Юрьевна

Беспалова Виктория Юрьевна, МАО «Лицей №10»г.Каменска-Уральского Свердловской области«Комбинаторные задачи из ЕГЭ по информатике»Задание номер 8 в ЕГЭ по информатике традиционного предусматривает решение комбинаторных задач. В данной статье предлагается единый подход к решению задач данного типа путем переборов вариантов и проверки заданных условий. Программы написаны на языке программирования Python.ПРИМЕР №1 Петя составляет слова из слова ПАРУС и записывает их в алфавитном порядке в список. Вот начало списка1. ААААА2. ААААП3. ААААР4. ААААС5. ААААУ6. АААПАПод каким номером идет первое слово в списке, начинающегося на У, в котором две буквы А не стоят рядом?Ответ: 2527Идея решения. Буквы из слова ПАРУС расположим в алфавитном порядке. Получим такой порядок: А, П, Р С, У. Заменим цифрами: А-0, П-1, Р-2, С-3, У-4. Получим пятеричную систему. Следовательно, имеем список, моделирующий счет в пятеричной системе счисления:1. 000002. 000013. 000024. 000035. 000046. 00010….Обозначим разряды слов (позиции) слева направо как a,b,c,d,e. В процессе перебора в каждом разряде может быть одна из букв А, П, Р С, У с повторением, то есть любая цифра от 0 до 4. В range(0,5) будут генерироваться именно значения от 0 до 4.Введем переменную num – это номер текущего варианта, который обнулим вначале программы. Так как следует найти первое слово, будем находить минимальное значение num. Для этого введем переменную mini и зададим ей первоначально заведомо большое число 1000000000.При получении очередной комбинации значения a,b,c,d,e будут переводиться в строкой тип и формировать строку s. Это удобно, так как при применении функции count можно легко найти количество вхождений необходимой подстроки в строку s.В строке сравнений проверяем, что значение а равно 4, то есть слово начинается на У, далее проверяется нахождение подряд двух цифр 00, которые соответствуют сочетанию АА в слове, а также вычисляется минимальный номер строки путем сравнения номера строки num c минимумом mini и перезапоминания нового значения минимума. Полный текст программы:num=0 mini=1000000000for a in range(0,5): for b in range(0,5): for c in range(0,5): for d in range(0,5): for e in range(0,5): num=num+1 s=str(a)+str(b)+str(c)+str(d)+str(e) if a==4 and s.count('00')==0 and \ num<mini: mini=numprint(mini)ПРИМЕР 2. Все пятибуквенные слове, в составе которых могут быть только русские буквы Я, Н, В, А, Р, Ь, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка.1. ААААА2. ААААВ3. ААААН4. ААААР5. ААААЬ6. ААААЯ7. АААВА…Под каким номером в списке идёт последнее слово, которое не начинается с буквы Я, содержит не более одной буквы Ь и не содержит букв Я, стоящих рядом?Ответ 6406Идея решения та же самая, что и в первом примере. Система счисления 6-разрядная, так как имеем шесть букв Я, Н, В, А, Р, Ь. Так как буквы расположены в алфавитном порядке, имеем: А=0, В=1, Н=2, Р=3, Ь=4, Я=5. Количество позиций равно пяти (слева направо a,b,c,d,e).Если требуется последнее слово, то номер должен быть максимальным. Следовательно, объявляем переменную ma c заведомо малым числовым значением -1000000000, а при появлении строки, соответствующей условиям, но имеющий бОльший порядковый номер num, происходит перезапоминание номера строки в переменной ma.В строке сравнения проверяется, что строка не начинается на 5, то есть не на Я, количество букв Ь содержится не более одной (то есть количество 4 меньше или равно 1), а количество сочетаний ЯЯ (55) равно нулю.Полный текст программы:num=0ma=-1000000000for a in range(0,6): for b in range(0,6): for c in range(0,6): for d in range(0,6): for e in range(0,6): x=str(a)+str(b)+str(c)+str(d)+str(e) num=num+1 if a!=5 and x.count('4')<=1 and x.count('55')==0 \ and num>ma: ma=numprint(ma)ПРИМЕР 3. Определите количество пятизначных чисел, записанных в восьмеричной системе счисления, в записи которых ровно одна цифра 6, при этом никакая нечетная цифра не стоит рядом с цифрой 6.Ответ: 2961Идея решения такая же, но число не может начинаться с нуля, потому первый range имеет параметры 1,8. 8, потому что система восьмеричная, а раз числа пятизначные, то идет перебор пятью циклами по разрядам a,b,c,d,e. Проверяется, что количество цифр 6 равно единице, а также нет сочетаний, когда рядом с цифрой 6 стоят нечетные цифры, причем рассматриваются вариации, когда нечетная цифра может стоять и слева, и справа от цифры 6.Полный текст программы:k=0for a in range(1,8): for b in range(0,8): for c in range(0,8): for d in range(0,8): for e in range(0,8): s=str(a)+str(b)+str(c)+str(d)+str(e) if s.count('6')==1 and s.count('16')==0 and \ s.count('61')==0 and s.count('36')==0 and \ s.count('63')==0 and s.count('56')==0 and\ s.count('65')==0 and s.count('76')==0 and\ s.count('67')==0 and\ s.count('69')==0 and s.count('96')==0: k=k+1print(k)ПРИМЕР 4. Ученица составляет 5-буквенные слова из букв ГЕПАРД. При этом в каждом слове ровно одна буква Г, слово не может начинаться на букву А и заканчиваться буквой Е. Какое количество слов может составить ученица? Ответ 2200Идея решение такая же, но в данном случае нет требований, что буквы расположены в алфавитном порядке, поэтому пусть они соответствуют цифрам: Г – 0, Е- 1, П- 2, А- 3, Р-4, Д -5Так как стоит вопрос о количестве, обнуляем переменную k, а далее при выполнения условия будем добавлять в нее 1. Проверяем, если количество букв Г (цифр 0) равно 0, а также то, что слово не начинается на букву А (цифра 3) и не заканчивается на Е (цифру 1).Полный текст программы: k=0for a in range(0,6): for b in range(0,6): for c in range(0,6): for d in range(0,6): for e in range(0,6): s=str(a)+str(b)+str(c)+str(d)+str(e) if s.count('0')==1 and a!=3 and e!=1: k=k+1print(k)ПРИМЕР 5.Вася составляет 6-буквенные слова, в которых могут быть использованы только буквы В, И, Ш, Н, Я, причём буква В используется не более одного раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Слово не должно начинаться с буквы Ш и оканчиваться гласными буквами. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?Ответ: 4352Как и в предыдущем примере, нет необходимости располагать буквы в алфавитном порядке, потому положим соответствие букв следующим цифрам:В-0, И-1, Ш-2, Н-3, Я-4 Система пятеричная, количество букв 6. В сроке сравнения проверяем, что количество букв В не более одной (то есть цифра 0 встречается меньше или равно 1 раз), а чтобы слово заканчивалось на гласные буквы, проверяем, что это не согласная буква, то есть невозможно окончание на цифры 1,4. Также проверяется, что слово не начинается на букву Ш (на цифру 2).k=0for a in range(0,5): for b in range(0,5): for c in range(0,5): for d in range(0,5): for e in range(0,5): for f in range(0,5): s=str(a)+str(b)+str(c)+str(d)+str(e)+str(f) if s.count('0')<=1 and a!=2 and f!=1 and f!=4: k=k+1print(k)