Продолжаем наш непотопляемый цикл про задачки с собеседований. Эти задачи мы берём с сайта Leetcode — главного сборника таких задач с комментариями разработчиков. Но там всё по-английски, а мы разберём по-русски и насколько возможно просто.
Сегодняшнюю задачу любят давать тем, кому придётся работать с текстом, например в разработке поисковых систем. Условие:
Есть массив со словами, в котором есть хотя бы одно слово. Надо найти максимально длинное общее начало каждого слова. Если такого нет — вывести пустую строку.
Пример: у нас есть массив [‘дом’, ‘домен’, ‘домра’, ‘доширак’]. Общее начало каждого слова — ‘до’.
Ещё пример: массив [‘документ’, ‘дока’, ‘кум’, ‘ум’]. Ответом будет пустая строка, потому что у всех этих слов нет единой общей части в начале слова.
Попробуйте решить это самостоятельно, а потом возвращайтесь к ответам.
Простое решение
Раз одинаковое начало должно быть у всех слов, то за основу можно взять первое слово, а все остальные начала сравнивать с ним. Причём сравнивать нужно посимвольно:
МКН Александр Куликов. Выполнимость: задача на миллион. 3. Перебором с возвратом и локальный поиск
- Берём первое слово как основное.
- Берём оттуда первую букву.
- Смотрим, совпадает ли она с первыми буквами во всех других словах.
- Если совпадает — добавляем эту букву к ответу с общей частью.
- Если не совпадает — прекращаем работу и выводим то, что нашли к этому моменту.
- Если ничего не нашли, то выводим пустую строку.
Чтобы такое сделать в Python, нам понадобится функция enumerate() — если ей на вход дать слово, то она сможет в цикле по очереди возвращать очередной символ и его порядковый номер. Это именно то, что нам нужно, — перебрать все символы в первом слове по порядку.
Ещё из нового — команда else в конце цикла. Мы привыкли, что else используют в условиях, но иногда эту команду добавляют и к циклу. Смысл в том, что если цикл отработал штатно и ни разу не прервался, то после его работы выполняется то, что написано после else . Это нам пригодится, чтобы понять, нужно нам добавлять очередной символ к общему началу или с циклом были проблемы и добавлять его не нужно.
Вот как выглядит реализация такого алгоритма на Python:
# исходный массив со строками strs = [‘дом’, ‘домен’, ‘домра’, ‘доширак’] # функция, которая найдёт общее начало def simplelongestCommonPrefix (strs): # на старте общее начало пустое res = «» # получаем пары «номер символа» — «символ» из первого слова for i, c in enumerate(strs[0]): # перебираем следующие слова в списке for s in strs[1:]: # если это слово короче, чем наш текущий порядковый номер символа # или если символ на этом месте не совпадаем с символом на этом же месте из первого слова if len(s)
Хитрое решение
Для хитрого решения нам понадобятся две функции — zip(*) и set() .
Функция zip(*) берёт список и формирует из него много других списков, складывая их так: первый элемент к первому, второй ко второму и так далее. Покажем работу на примере нашего списка:
Решение 6 задачи ЕГЭ по информатике. Алгоритм полного перебора чисел
- Функция возьмёт из него все слова по отдельности: ‘дом’, ‘домен’, ‘домра’, ‘доширак’.
- Возьмёт первую букву каждого слова и составит из них отдельный список: .
- Потом возьмёт вторую букву каждого слова и составит список уже из них: .
- Так она будет делать до тех пор, пока не закончатся буквы в самом коротком слове. Как только хоть одно слово закончилось — функция заканчивает работу.
Получается, что так мы можем получить сразу все сгруппированные буквы по порядку каждого слова. Теперь нам нужно проверить, разные там буквы в этих списках или нет. Если все буквы одинаковые, значит, они подходят к каждому слову, и значит, что их можно добавить к ответу. Если есть хоть одна отличающаяся буква — всё, общее начало на этом закончилось.
Чтобы такое проверить, используем функцию set() — она составит из переданных ей аргументов список с уникальными значениями. Если длина такого списка будет равна 1, значит, все переданные символы были одинаковые — и их можно добавлять к ответу.
Читайте комментарии, чтобы разобраться в этом хитром коде:
# исходный массив со строками strs = [‘дом’, ‘домен’, ‘домра’, ‘доширак’] # функция, которая найдёт общее начало def longestCommonPrefix(strs): # на старте общее начало пустое prefix=[] # разбираем слова побуквенно в отдельные списки и перебираем их по очереди for x in zip(*strs): # смотрим, сколько уникальных элементов у нас получилось в наборе на этом этапе if len(set(x)) == 1: # если уникальный элемент один — добавляем его к общему началу prefix.append(x[0]) # если уникальных элементов было больше одного else: # прерываем цикл и выходим из него break # возращаем результат работы функции # если общее начало пустое, то на выходе получим тоже пустую строку return «».join(prefix) # выводим результат работы функции print(longestCommonPrefix(strs))
Источник: thecode.media
6. Задачи на перебор вариантов
Имеется целый класс задач, решение которых сводится к перебору различных вариантов, среди которых выбирается такой, который удовлетворяет условию задачи. Пример 1: Поиск делителей целого числа N. Целое число K является делителем N, если остаток от деления N на K равен 0. Чтобы найти все делители достаточно перебрать все числа от 1 до N и проверить, являются ли они делителями. Данный алгоритм можно реализовать с помощью программы:
readln(n); for i:=1 to n do if n mod i = 0 then write(i, ‘ ‘);
На этом простейшем примере ясна общая структура решения задач на перебор вариантов. Для организации перебора используется цикл, каждый шаг выполнения которого соответствует рассмотрению одного из вариантов. Внутри цикла стоит проверка, подходит ли данный вариант под условие задачи.
Решая задачи методом перебора, всегда следует подумать, а нельзя ли каким-то образом сократить количество перебираемых вариантов. В данном случае заметим, что любое число делится само на себя и на 1. Поэтому эти варианты можно исключить из перебора. Более того, наибольшим делителем, отличным от самого числа N может быть только N/2, а все числа, большие N/2 заведомо делителями не являются. Учет этих особенностей приводит к более эффективной программе:
readln(n); write(1, ‘ ‘); for i:=2 to n div 2 do if n mod i = 0 then write(i, ‘ ‘); write(n);
Продолжая размышления о сокращении перебора (спасибо комментарию Владимира), заметим, что если i является делителем, то частное от деления на i — тоже делитель. Таким образом, выводя делители парами, можно ограничится перебором до корня из n:
readln(n); writeln(1, ‘ ‘, n); m:=trunc(sqrt(n)); for i:=2 to m do if n mod i = 0 then writeln(i, ‘ ‘, n div i);
Конец примера 1. В приведенном примере вариантом решения являлась переменная i, используемая как счетчик цикла. Не трудно представить себе, задачу, где такое невозможно. Например, вариант может не быть целым числом.
В этом случае переменная счетчик цикла выступает как номер варианта, а в цикле требуется совершить еще одно действие: по номеру определить этот самый вариант. То есть вместо схемы: Перебираем варианты и проверяем, удовлетворяют ли они условию будем иметь схему Перебираем номера вариантов, по номеру вычисляем вариант решения, проверяем Пример 2. Найти минимумы функции с точностью до 0.001 на отрезке от –5 до 5. Для поиска минимума будем перебирать все числа от –5 до 5 с шагом 0.001. Условием нахождения минимума будем считать то, что значение функции меньше, чем в соседних точках. А именно: . Данный алгоритм можно реализовать с помощью программы:
Step:=0.001; MinX:=-5; MaxX:=5; VarNumber:=trunc((MaxX – MinX)/Step)+1; for i:=1 to VarNumber do begin x:=MinX + (i-1)*step; if (sqr(sqr(x))–sqr(x) < sqr(sqr(x-step))–sqr(x-step)) and (sqr(sqr(x))–sqr(x) < sqr(sqr(x+step)) then writeln(x); end;
Кроме перебора вариантов здесь в начале программы использован еще один важный прием, называемый параметризацией. Такие характеристики как точность и диапазон поиска были записаны в отдельные переменные, а затем вместо чисел использовались имена этих переменных. Такой подход позволяет легче модифицировать программу, если параметры задачи изменятся, программа становится более универсальной. Кроме того, программа становится более понятной, особенно если имена переменных выбраны так, чтобы соответствовать смыслу, хранимого в них параметра (MinX – минимальное значение переменной x и т.п.) Каждый следующий проверяемый вариант можно также вычислять не по номеру
x:=MinX + (i-1)*step;
а по предыдущему значению
x:=x + step;
Очевидно, это ничем не хуже. Пример 3. Пусть двумя числами (H и V) задано положение коня на шахматной доске.
Найдите координаты всех клеток, куда конь может пойти следующим ходом (других фигур на доске нет). В данном примере, вариантами решения являются координаты клеток, то есть каждый вариант это не одно число, а два. Необходимо придумать способ вычисления варианта (в данном случае номеров горизонтали и вертикали) по его номеру. Всего клеток 64.
Пронумеруем клетки, как показано на рисунке. Теперь, если мы будем перебирать в цикле номера клеток N, необходимо уметь по этим номерам определять номер горизонтали X и вертикали Y. Нетрудно видеть, что номер горизонтали определяется тем сколько раз по 8 клеток надо взять, пока мы не доберемся до числа N:
X := (N — 1) div 8 + 1;
(N — 1) потому что важно сколько горизонталей заполняют клетки лежащие до N-й, а их как раз N — 1. Остаток после удаления целого числа раз по 8 клеток позволит вычислить номер вертикали:
Y := (N — 1) mod 8 + 1;
Теперь, когда мы умеем перебирать варианты, необходимо записать условие того, что данный вариант является решением задачи. Известно, что конь ходит буквой Г, смещаясь на две клетки в одном направлении и на одну в другом. Например, на рисунке показан ход, когда перемещение коня состоит из сдвига на две клетки по вертикали и на одну по горизонтали. Пусть проверяется клетка с координатами (x, y). Тогда условие сдвига по горизонтали на 2 будет выглядеть так:
abs(X-H) = 2
Взятие модуля необходимо, чтобы учесть возможность сдвига как вправо, так и влево. Аналогично условие сдвига на одну клетку, например, по вертикали:
abs(Y-V) = 1
Полное условие возможности пойти на клетку конем будет выглядеть как:
((abs(X-H) = 2)and(abs(Y-V) = 1)) or ((abs(Y-V) = 2)and(abs(X-H) = 1))
То есть либо сначала по горизонтали на две клетки, а потом на одну по вертикали либо на две по вертикали, потом на одну по горизонтали. Теперь, когда ясно как перебирать клетки и как проверять возможность хода, можно написать требуемую программу:
readln(H, V); for n:=1 to 64 do begin X := n div 8 + 1; Y := n mod 8; if ((abs(X-H) = 2)and(abs(Y-V) = 1)) or ((abs(Y-V) = 2)and(abs(X-H) = 1)) then writeln(X, Y); end;
В случае, когда как в приведенном примере, каждый вариант задается не одним числом, а несколькими, удобно для перебора использовать вложенные циклы. В данном случае номера вертикали и горизонтали являются целым числами от 1 до 8, поэтому для перебора их значений можно использовать счетчики циклов:
readln(H, V); for X:=1 to 8 do for Y:=1 to 8 do if ((abs(X-H) = 2)and(abs(Y-V) = 1)) or ((abs(Y-V) = 2)and(abs(X-H) = 1)) then writeln(X, Y);
Рассмотрим еще один пример, где вариант задается несколькими числами. Пример 4. Составить программу-генератор пифагоровых троек.
Пифагоровой тройкой называют такие целые числа a, b и c, которые удовлетворяют условию a 2 +b 2 =c 2 . Известно, что существует прямоугольный треугольник с такими длинами сторон. Найдем все пифагоровы тройки для c < 5.Тройное вложение циклов позволит перебрать все возможные комбинации значений трех чисел a, b и c и вывести те из них, которые удовлетворяют заданному равенству.
MaxC:=25; MaxAB:=trunc(sqrt(MaxC)); for a:=1 to MaxAB do for b:=1 to MaxAB do for c:=1 to MaxC do if a*a+b*b = c*c then begin write(a, ‘ ‘, b, ‘ ‘, c); writeln; end;
Как всегда при решении задачи методом перебора, следует задуматься, можем ли мы сократить число перебираемых вариантов. Оказывается, можно ограничиться только перебором a и b, а c вычислять по теореме Пифагора . Вычисленное таким образом c может оказаться нецелым, поэтому условие задачи для него проверять все равно необходимо.
MaxC:=25; MaxAB:=trunc(sqrt(MaxC)); for a:=1 to MaxAB do begin for b:=1 to MaxAB do begin c:=round(sqrt(a*a+b*b)); if a*a+b*b = c*c then begin write(a, ‘ ‘, b, ‘ ‘, c); writeln; end; end; end;
Источник: www.tvd-home.ru
5 самых сложных задач из ЕГЭ по информатике в 2023 году — и как их решать
В ЕГЭ по информатике 27 заданий разного уровня: и ряд из них требует особого подхода. Преподаватель Московской школы программистов (МШП) Кирилл Ситнов рассказывает о самых сложных заданиях 2023 года — и дает подсказки, как с ними справиться.
Последние пару лет ЕГЭ по информатике проходит в компьютерной форме (так называемом КЕГЭ). В первый год использования формата было найдено много лазеек, которые позволяли упростить решение некоторых задач. Это, например, задания № 6 и № 22, где нужно было проанализировать код в бланке задания и написать, что программа выведет в результате (либо какая ошибка допущена в этом коде). Тогда многие переписали эту программу в компилятор, увидели результат и получили за это 2 балла.
После подобных «взломов экзамена» ФИПИ стали ежегодно вносить массу изменений в КЕГЭ, чтобы избавиться от шаблонности решения задач.
Что из себя представляют эти задания сейчас
Вот формулировка ФИПИ:
Теперь в задании 6 (согласно демоверсии экзамена) нужно проанализировать работу исполнителя на примере «черепашки». Кто сдавал ОГЭ, могут это вспомнить. А вот задание 22 требует анализировать информацию, представленную в электронных таблицах.
Также стоит ожидать усложнения еще ряда заданий.
Например, задание № 14. Ранее требовалось только знать, как производится перевод чисел в различные системы счисления либо как проводить операции сложения и вычитания. Теперь же от учащегося требуют найти недостающую цифру числа.
Задание 16 «Рекурсия». Это задание лишилось простого решения, где ответ можно было получить обычным перебором, используя граф. Теперь из-за больших величин аргументов стоит опираться в первую очередь на аналитическое мышление. А также понимать, что именно считает функция.
5 самых сложных задач
Задание № 15 «Преобразование логических выражений»
Первый тип этой категории — «побитовая конъюнкция». Задание не вызовет серьезных проблем, если ребенок разбирается в программировании. Для решения нужно знать, как записывать логические выражения на языке программирования, а также понимать структуру циклов перебора и алгоритма ветвления.
Вторая категория — «числовые отрезки». Основную трудность вызывает применение законов алгебры логики для упрощения выражений. Ученики либо не видят способ применения того или иного закона, либо просто забывают о них. Поэтому в этом задании нужно как можно больше практики. Стоит потренироваться на большом объеме задач, которые можно найти на «Решу ЕГЭ» или сайте Константина Полякова.
Третий тип — «координатная плоскость». Задания логичнее решать программированием, поскольку это экономит время. Здесь всё опирается на понимание циклов и условных операторов.
Задание № 24 «Обработка символьных строк»
Ученику предстоит написать программу для обработки символьных данных, записанных в файле. Ручной перебор здесь исключен из-за большого массива данных. Воспользоваться альтернативными способами решения, не прибегая к программированию, также затруднительно.
Задание № 25 «Обработка целочисленной информации»
Задача проверяет, умеет ли ученик оптимизировать код. Диапазон значений, на которых выпускнику необходимо проверить ряд условий, достаточно большой, и программа будет долго выполнять перебор. Условия в задаче примерно следующие:
— найти количество чисел из диапазона, у которых только два делителя
— проверить числа из диапазона на «простоту» и т. д.
Задание № 26 «Обработка массива данных из файла»
Необходимо перебрать данные из файла и отобрать их по определенному признаку, который заявлен в условии задачи. Задачу необходимо решить оптимально, выполняя сортировку либо по возрастанию, либо по убыванию.
Задание № 27 Самое сложное
По некоторым данным, за последние пару лет с заданием справились всего около 14% выпускников.
Зачастую, если ученик не претендует на 100 баллов, учителя и репетиторы предлагают не тратить время на задание. Поскольку решение в среднем займет около 40 минут.
Вот только часть необходимых знаний и умений, чтобы успешно справиться с заданием:
- уметь решать задачи с разбиением строк на подстроки по разделителям;
- умело использовать функции и процедуры;
- знать, как обрабатывать символьные данные;
- использовать сдвиги элементов массива.
Кроме того, задачи имеют достаточно большую вариативность и с ними не получится вызубрить несколько алгоритмов решений. Поэтому нужен максимум усилий и практики.
Фото на обложке: jannoon028 / Shutterstock / Fotodom
Источник: mel.fm