Различия между версиями 3 и 4
⇤ ← Версия 3 от 2011-01-26 22:24:01 →
Размер: 2831
Редактор: PavelSutyrin
Комментарий:
← Версия 4 от 2011-01-27 15:07:09 → ⇥
Размер: 997
Редактор: PavelSutyrin
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 5: Строка 5:
= Тема занятия: кратко = = Немного комбинаторики =
Строка 7: Строка 7:
<<Include(VMSHClassTemplate/Legend,,from="##begin class legend##",to="##end class legend##")>>
   1. Разбор решений задачи о ломаных и о Ханойских башнях.
  2. Оптимизация количества операций в формулах.
Строка 11: Строка 11:
<<Include(VMSHClassTemplate/Legend,,from="##begin home legend##",to="##end home legend##")>>
Строка 17: Строка 16:
  1. Министерство дорожного транспорта решило построить себе новый офис. Поскольку министр регулярно выезжает с инспекцией наиболее важных трасс, было решено, что офис министерства не должен располагаться слишком далеко от них. Наиболее важные трассы представляют собой прямые на плоскости. Министерство хочет выбрать такое расположение для своего офиса, чтобы максимум из расстояний от офиса до трасс был как можно меньше. Требуется написать программу, которая по заданному расположению наиболее важных трасс определяет оптимальное расположение дома для офиса министерства дорожного транспорта. Первая строка входного файла содержит одно целое число n — количество наиболее важных трасс (1 ≤ n ≤ 104). Последующие n строк описывают трассы. Каждая трасса описывается четырьмя целыми числами x1, y1, x2 и y2 и представляет собой прямую, проходящую через точки (x1, y1) и (x2, y2). Координаты заданных точек не превышают по модулю 104. Точки (x1, y1) и (x2, y2) ни для какой прямой не совпадают.
    (возможно, эту задачу лучше отложить до PyGame -- PavelSutyrin <<DateTime(2011-01-26T22:24:01+0300)>>)		   1. (задачку про министерство отложим до PyGame).
  1.

Немного комбинаторики

  1. Разбор решений задачи о ломаных и о Ханойских башнях.
  2. Оптимизация количества операций в формулах.

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

  1. Оптимизировать комбинаторные формулы для вычисления числа ломаных на окружности. Получить самое эффективное решение задачи!
    1. Сократить куски факториалов
    2. Вынести общий факториал для i+j = l
    3. Сократить дробь из биномиальных коэффициентов и других факториалов

  2. (задачку про министерство отложим до PyGame).

CategoryClass CategoryVmsh

LecturesVMSH/2011-01-26 (последним исправлял пользователь PavelSutyrin 2011-01-27 15:18:44)