Переборная схема без рекурсии. Функции-генераторы. Задачи на замыкание транзитивного отношения

Алгоритм транзитивного замыкания изложить на следующем занятии

  • {o} — тема по Linux

  • <!> ­— необязательная тема

Домашнее задание

  • {i} — теоретическое задание

  • {*} — новая тема

  1. {i} Прочитать про генераторы в учебнике

  2. Зарегистрироваться на этом Wiki и оформлять ДЗ в виде attachment к соответствующим страницам. Имя прикладываемого файла должно начинаться с ivanov_1, где ivanov - фамилия ученика, 1 -- номер решенной задачи. Например smirnov_1_recursion.py, smirnov_1_better_solution.py. Зарегистрироваться рекомендуется под именем вида PetrIvanov. Можно заполнить свою личную страничку.

  3. Ввести число N, вывести все способы разложения на любые (не только простые) сомножители
    • Рекурсивный вариант с вычислением количества перестановок somnoj.py

    • Рекурсивный вариант с вычислением количества сочетаний somnojA.py

    • Переборный вариант с вычислением количества перестановок somnojAN.py

  4. {*} Имеется N городов и таблица стоимости проезда из любого города i в любой город k (если сообщения между городами нет, используется число > N*max стоимость проезда). Получить таблицу минимальной стоимости проезда с учётом произвольного количества пересадок

    • Идея в том, чтобы хранить на карте минимальные стоимости, и не более чем N раз проверить, нельзя ли из города i в город k попасть через город j дешевле, чем напрямую: peresad.py

    • Генератор входных данных: peresad_gen.py


CategoryClass CategoryVmsh

LecturesVMSH/2010-12-01 (last edited 2010-12-08 11:48:12 by FrBrGeorge)