Решение задач на вложенные циклы

Болк задач

Повторение: Как идею алгоритма превратить в программу?

Общая идея:

0. Задача на вложенные циклы — это примитивная двойная задача, она имеет чётко выраженную «внутреннюю» подзадачу и множество вариантов входных данных, на каждом из которых эту подзадачу надо решить.

1. Если внутренняя задача (поиск элемента, вычисление свойств набора данных, преобразование набора и т. п.) решается итеративно, в решении образуются два вложенных цикла:
   • Внешний цикл (по всем наборам данных)
     • Сформируем очередной набор данных
     • Решим подзадачу
       • … внутренний цикл
     • Обработаем решение
2. Зачастую внешний и внутренний циклы можно отлаживать отдельно:

   • Взять один фиксированный невырожденный набор данных, реализовать на нём решение подзадачи

   • Написать внешний цикл и посмотреть, правильные ли наборы данных он формирует
   • Объединить

Ввести N Вывести все простые числа в диапазоне от 2 до N

• Формулировка решения
• Внешний цикл тривиален

  • Внутренний цикл — подсчёт числа делителей (делится ли на 2…N//2)

• Если таких делителей нет, число целое

• Реализовать

№328: Найти N первых простых чисел

• В чём разница, и что делать?

• решить

№363: Дана строка "s₀…s_n-1". Преобразовать строку, добавив как можно более короткую подстроку "s_n…s_m-1" так, чтобы строка "s₀…s_m-1" стала палиндромом: s₀=s_m-1, s₁=s_m-2 и т. д.

• Пример: "AbCdC" → "AbCdC" + "bA" = "AbCdCbA"

• Внутренний цикл: проверка на палиндром

• Внешний цикл: попытаемся решить вручную

  • Спойлер: Наихудший случай: та же строка задом наперёд. Наилучший: она уже палиндром. Что между? Вариант решения: добавочная строка сначала пуста, затем — "s₀", если нет — "s₁s₀", "s₂s₁s₀" и т. п., т. е. формируем добавочную строку из предыдущей + очередной символ исходной строки

• Перевести на Python и организовать цикл, который генерирует все добавочные строки

• Решить

• Дана строка. Найти все палиндромические подстроки длиной не менее 3 букв.

  • Пример: qwwewewwq:

    qwwewewwq
    wweweww
    wew
    wewew
    ewe
    wew

  • внутренний цикл: проверка подстроки длиной w с позиции i на палиндром

    • Пример: qwwewewwq 3 4 → "wew"; qwwewewwq 4 2 → ничего

  • в чём особенность всей задачи?

    • Спойлер: Здесь три вложенных цикла, два внешних — по началу и по размеру

    • Аккуратно посчитать максимальный размер подстроки, начинающейся с позиции i

  • Решить!

Если будет время/понимание: разбор полной задачи про второй максимум.

Д/З

• Решить оставшиеся 7 задач (c 11 по 17) Шестого занятия учебника

• Скопировать решения в соответствующие файлы и проверить, что они всё ещё работают!

  • Имена файлов — от prog_6_11.py до prog_6_17.py

• Прислать эти 10 файлов в виде семи приложений к одному письму по адресу <uneexlectures AT cs DOT msu DOT ru>

  • В поле Subject должно быть «слово» PhilosoPython2022 (другие слова тоже можно ☺)