Предлагаю книгу "Графомания" (Деревенец О.В.). Алгоритмы на графах реализованы на языке Delphi (Object Pascal) Все исходники и контрольные примеры в наличии. Скачивается бесплатно. Содержание: Знакомство с объектами, отношениями и множествами Представление объектов в языке Delphi Представление множеств, операции с множествами Понятие о сложности (трудоёмкости) алгоритмов Задачи на множествах: • разбиение множества на подмножества; • задача о наименьшем разбиении (ЗНР); • задача о наименьшем покрытии (ЗНП). Представление отношений графами Программная реализация графов, ввод и вывод графов Группа задач на достижимость: • взаимная достижимость вершин; • кратчайшие пути между вершинами; • выделение сильно связанных компонент. Группа задач на размещение: • независимые вершины и клики; • доминирующие множества; • раскраски; • центры; • p-центры; • p-медианы. Остовные деревья Группа задач о потоках: • максимальный поток в сети; • поток, ограниченный сверху и снизу; • минимальная стоимость потока. Паросочетания: • паросочетание в двудольном графе; • паросочетание в произвольном графе. Цикл Эйлера и задача почтальона: • на неориентированном графе; • на орграфе. Задачи Гамильтона и коммивояжёра: • разомкнутая задача Гамильтона; • замкнутая задача Гамильтона (цикл); • комбинирование методов для задач Гамильтона; • замкнутая и разомкнутая задачи коммивояжёра.
Так а где все? Деревья, компоненты сильной связности, мосты, двусвязность, точки сочленения, двудольность, потоки, lca, центройды, хэви лайт декомпазиция и тому подобное
Предлагаю книгу "Графомания" (Деревенец О.В.). Алгоритмы на графах реализованы на языке Delphi (Object Pascal) Все исходники и контрольные примеры в наличии. Скачивается бесплатно. Содержание: Знакомство с объектами, отношениями и множествами Представление объектов в языке Delphi Представление множеств, операции с множествами Понятие о сложности (трудоёмкости) алгоритмов Задачи на множествах: • разбиение множества на подмножества; • задача о наименьшем разбиении (ЗНР); • задача о наименьшем покрытии (ЗНП). Представление отношений графами Программная реализация графов, ввод и вывод графов Группа задач на достижимость: • взаимная достижимость вершин; • кратчайшие пути между вершинами; • выделение сильно связанных компонент. Группа задач на размещение: • независимые вершины и клики; • доминирующие множества; • раскраски; • центры; • p-центры; • p-медианы. Остовные деревья Группа задач о потоках: • максимальный поток в сети; • поток, ограниченный сверху и снизу; • минимальная стоимость потока. Паросочетания: • паросочетание в двудольном графе; • паросочетание в произвольном графе. Цикл Эйлера и задача почтальона: • на неориентированном графе; • на орграфе. Задачи Гамильтона и коммивояжёра: • разомкнутая задача Гамильтона; • замкнутая задача Гамильтона (цикл); • комбинирование методов для задач Гамильтона; • замкнутая и разомкнутая задачи коммивояжёра.
глупость. Какой мотоциклист остановится на 2 часа, если весь путь занимает один час? Че он, проедет 20-30 минут и такой - чето я устал ездить (что вообще нон-сенс из уст мотоциклиста), дай-ка два часа постою. И потом постоял два часа и решил поехать. Чушь) У задачи только одно решение.
Справедливости ради, в задаче 4 стратегия для первого игрока отдать первым ходом первые 4 карточки и следующими ходами отдавать до ближайшего 5k-1 - вполне рабочая. Легко показать, что как бы не ходил игрок 2, самое позднее - при получении карточки с номером 75 игрок 1 будет иметь 10 "5", тогда как игрок 2 - максимум 8 "5". Необходимое кол-во "2" доказывается чуть дольше - разбивая ходы игрока 2 на 3 типа - оптимальные(такая же стратегия как у игрока 1), больше(по кол-ву отдаваемых за ход карточек) оптимальных и меньше оптимальных.
Согласен . У меня такая же стратегия за первого. По если второй действует аналогично первому то второй всегда будет догонять первого по количеству пятерок в разложении на простые произведения чисел на его карточках. На 2 нам наплевать , так как их очень много, это можно строго доказать но грубо проще так. Для 2 других действий второго результат аналогичен , он всегда догоняет первого по пятеркам .
У вас, кажется, лажа на 1:26:42, по скольку вершины рассматриваемого подграфа совсем не обязательно имеют степень 10 внутри этого подграфа, а значит лемму о рукопожатиях мы не имеем права использовать
В группе как максимум 10 человек и у каждого как максимум 10 знакомств. Ну а если в подграфе 100 знакомств, то каждый из 10 имеет 10 знакомств, только так
Вообще-то, цифры - это знаки, которые ни на что не делятся. Делятся на что-то только числа, которые представлены цифрами (в том числе, когда в представлении цифра одна).
4:50:32 а мы же выделяли максимальное паросочетание, как так вышло, что в итоге мы нашли другое паросочетание на большее кол-во вершин? изначально же взяли максимальное?
9:26 неожиданное решение. По условию бельчата не могут бросать шишки в самого себя, значит каждый из 3 бельчат не попадает в сам себя, что удовлетворяет утверждению:" Найдётся группа из трёх бельчат, не бросивших шишки в бельчонка из этой группы "
8:00 Владимир Артурович Лёвшин (автор Магистра рассеянных наук) - великий человек. Многие советские и российские математики "зацепились" за математику именно из-за его книг. Я тоже читал в том же возрасте, что и Андрей Павликов. И сын у меня сейчас читает в том же возрасте :)
12:12 Эту задачу можно нагляднее же: 0 = (a + b + c + d) + (a + b + c + d) + (a + b + c + d) = (a + b) + (a + c) + (a + d) + (b + c) + (b + d) + (c + d) <= 2 * (max(a, b) + ... + max(c, d)), значит наше выражение тоже >=0. По сути это то же самое, но нагляднее - никаких лишних рассуждений про порядок и симметричность.
А разве в последней задаче можно не любое число 2<=n<=123? Ну типо делим на графы смежности, по условию смежных графов длины 1 - нет. Не сложно доказать, что в любом смежном графе длины x, можно выбрать k вершин, чтобы они тоже составляли смежный граф(другие вершины со всеми выходящими из них ребрами условно уничтожаются). Так вот, чтобы условие на наличие друзей в выбранной куче выполнялось необходимо и достаточно того, чтобы не существовало смежного графа из которого мы взяли только одного человека, то есть можно из одного взять 2 из другого 5 и тд., но главное чтобы не было 1. Ну теперь не сложно придумать алгоритм с помощью которого можно выбрать любое количество людей : возьмем любой смежный граф длины > 2 (такой всегда существует, так так если бы существовали только длины 2, то общее количество людей было бы четным). Пусть у него длина равна y(а сам граф назовем gY), тогда мы можем выбрать из него 2 человека, 3 человека, ..., y человек, теперь мы берем y-1 человека из gY, выбираем уже любой другой граф gZ, пусть его длина z(она может быть и 2) и берем из него два человека, в итоге имеем y+1 человека, после этого возвращаем того человека из gY_ и имеем уже y+2 человека, дальше мы просто к двум человекам из _Z добавляем по очереди по одному человеку из Z и в итоге мы уже прошлись по всем n от 2 до y+z, ну таким образом мы сливаем и другие графы и в итоге мы прошлись по всем 2<=n<=123. А вот если бы n было четным, то тогда могло бы быть такое, чтобы существовали только смежные графы длины 2, тогда да, можно только четное количество выбрать(но если бы был хоть один смежный граф длины >2, то уже можно любое количество людей выбрать)
В 9-10 классе из олимпиад учавствовал только в региональном этапе всош (набирал в районе 20 баллов). В 11 решил заняться олимпиадами. Ваш курс действительно помог, думаю взял свой максимум ( 2 призёра 2 уровня + побед регионального этапа), так что за год в целом добиться некоторых результатов возможно
