Сообщения

Подсчет путей в ориентированном графе (задача 13)

Изображение
Подсчет путей в ориентированном графе (задача 13)   Хотите готовиться со мной к ЕГЭ? Пишите:  ydkras@mail.r u Немного обо мне .   В задаче 13 ЕГЭ по информатике требуется подсчитать число путей из одного узла в другой. Вот типичная задача (заимствована из демонстрационного варианта ФИПИ по информатике 2022 г.):   "На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.Сколько существует различных путей из города А в город М, проходящих через город В?" Как решать подобные задачи программным путем? Прежде всего надо уметь представлять информацию о графе в форме, удобной для компьютерной обработки. В языке Питон есть очень удобный тип данных для нашей цели: словарь или ассоциативный массив. Это совокупность пар "ключ-значение".  Сначала подготовим исходные данные для заполнения словаря. Создадим текстовый файл, строки которого устроены следующим обр...

Количество программ (задача 23)

Количество программ (задача 23)   Хотите готовиться со мной к ЕГЭ? Пишите:  ydkras@mail.ru Немного обо мне .   В задаче 23 ЕГЭ по информатике описывается исполнитель, который может выполнять несколько команд (чаще всего две), например, прибавить 1 или прибавить 3. Требуется найти количество программ, которые преобразуют одно число (исходное) в другое (цель). Например, из числа 2 нужно получить число 15, используя две описанные выше команды. Такая задача решается вручную, но нас здесь интересует программый способ её решения. Получить искомое число программ можно с помощью несложной рекурсивной функции.  Для каждого числа менее цели количество программ, требуемых для её достижения - это сумма числа программ, получаемых с помощью каждой из команд исполнителя.  Заметим, что каждая команда увеличивает число. Поэтому если команда дает результат, превышающий целевое число, то в дальнейшем мы никогда не получим целевого числа. Если текущее число равно целевому, то мы, ...

Подпоследовательность с максимальной суммой, кратной 43

Подпоследовательность с максимальной суммой, кратной 43.   Хотите готовиться со мной к ЕГЭ? Пишите: ydkras@mail.ru Немного обо мне .   Рассмотрим следующую задачу из демонстрационного варианта ФИПИ ЕГЭ по информатике 2022 г. (она также включена в вариант 3 на сайте Полякова): Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них. Входные данные . Даны два входных файла ( файл A и файл B ), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 10 8 ). Каждая из следующих N строк содержит натуральное число, не превышающее 10000. Пример входного файла : 7 21 13 9 19 17 26 95 В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 4...

Теория игр, информатика и питон. Задачи ЕГЭ 19-21

Теория игр, информатика и питон. Задачи ЕГЭ 19-21.   Хотите готовиться со мной к ЕГЭ? Пишите: ydkras@mail.ru Немного обо мне .   Внимание! Данный материал устарел! Новую версию статьи читайте здесь: https://ege-informatika-yk.blogspot.com/2024/02/19-21.html       В задачах 19-21 ЕГЭ по информатике требуется проанализировать некую простую игру. Однако хотя игра и проста, её анализ может оказаться достаточно хитрым делом. Поэтому приходит мысль: а нельзя ли, чтобы этот анализ выполнил компьютер? (Спойлер: Можно!) Немного теории. Основную идею, лежащую в основе теории игр, подобных описанным в задачах ЕГЭ, можно выразить в двух словах: игроки умные. Это означает, что если у кого-то из игроков в текущей позиции есть возможность сделать выигрышный ход, то он этот ход сделает. Таким образом, если в текущей позиции у игрока есть хотя бы один ход, ведущий к выигрышу, то это - выигрышная позиция для данного игрока.  Если же в ответ на любой ход текущего игрока его п...

Задача 16 - рекурсивная функция

Задача 16 - рекурсивная функция Хотите готовиться со мной к ЕГЭ? Пишите: ydkras@mail.ru Немного обо мне .   Задача 16 ЕГЭ по информатике посвящена рекурсивным функциям.  Рекурсивные функции - такие функции, которые обращаются к самим себе. Рассмотрим задачу 16 из демонстрационного варианта ЕГЭ 2022 г. с сайта ФИПИ: Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n чётно, F(n) = 2 × F(n − 2), если n > 1 и при этом n нечётно. Чему равно значение функции F(26)? Вообще говоря, данная задача решается на бумаге. Для этого придется составить таблицу, содержащую значения F(1), F(2) и т.д. - до F(26) включительно. Но составлять таблицу из 26 строк вручную несколько трудоемко, да и вероятность ошибиться ненулевая. Гораздо проще составить эту таблицу в excel.   Но, на мой взгляд, ещё проще решать данную задачу программно. Сначала напишем рекурсивную функцию на Питоне: def F(n)...

Слова по порядку (задача 8)

Слова по порядку (задача 8)   Хотите готовиться со мной к ЕГЭ? Пишите:  ydkras@mail.r u Немного обо мне .   Рассмотрим типичную задачу ЕГЭ по информатике по теме 8 ("Перебор слов и системы счисления"). Все 5-буквенные слова, составленные из букв Л, Н, Р, Т, записаны в алфавитном порядке. Вот начало списка: 1. ЛЛЛЛЛ 2. ЛЛЛЛН 3. ЛЛЛЛР 4. ЛЛЛЛТ 5. ЛЛЛНЛ Запишите слово, которое стоит на 150-м месте от начала списка. (Задача 7755 с сайта "Решу ЕГЭ".) В принципе эта задача решается довольно просто. Данные слова можно рассматривать как числа в системе счисления с основанием 4, причем вместо цифры 0 используется буква Л, вместо 1 - Н, вместо 2 - Р и вместо Т - 3.  Заметим, что под номером 1 стоит число 0, под номером 2 - число 1 и т.д. Таким образом, под номером 150 будет стоять число 149. Надо перевести число 149 в систему счисления с основанием 4, затем заменить в нем цифру 0 на букву Л, 1 - на Н и т.д.  Это не так уж сложно сделать вручную, но можно и написать прог...
 Простые числа: как их находить? Многие задачи ЕГЭ требуют либо находить простые числа, либо проверять их на простоту. В этой статье мы рассмотрим, как быстро проверять, является ли данное число простым, а также находить простые числа. Метод "грубой силы": просто, но медленно Если чисел немного и они на слишком велики, то вполне годится "метод грубой силы": пробуем делить наше число на все числа меньше его. Если не найдется чисел, на которые наше число делится без остатка, то оно простое. Приведем фрагмент программы, который осуществляет проверку числа n:   prime = True for i in range(2,n):     if n%i == 0:         prime = False         break  По завершении цикла переменная prime будет иметь значение True, если число n простое, и False в противном случае. Процедуру можно существенно ускорить, если проверять делимость на числа в диапазоне от 2 до квадратного корня из проверяемого числа. Мо...