Задачник Базовый курс EN

Где встречается

игры

Статьи

SRT Алгоритм Перемешивание Фишера — Йетса Честная случайная перестановка за O(n): каждая из n! — с вероятностью 1/n!, и почему «обмен с любым» нечестен. O(n) 2 задачи GRA Алгоритм Поиск в ширину Обходит граф слоями и находит пути с наименьшим числом рёбер за O(V + E). O(V + E) 2 задачи GRA Алгоритм A* Дейкстра с подсказкой «сколько ещё до финиша»: волна тянется к цели, а путь остаётся кратчайшим. O((V + E) log V) 2 задачи PAR Приём Перебор с возвратом Строить решение по шагу, сразу проверять и отступать из тупика: судоку, ферзи, раскраски. O(bᵈ) в худшем случае 2 задачи GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи GEO Алгоритм Пересечение отрезков Где встречаются два отрезка — точно, в дробях; и как найти все встречи среди тысяч отрезков без перебора пар. O(1) на пару; O(n²) перебором для n отрезков 2 задачи GEO Алгоритм Точка в многоугольнике Луч из точки пересекает границу нечётное число раз — точка внутри; число оборотов — то же со знаками. O(n) на точку 2 задачи NUM~ Алгоритм Методы Эйлера и Рунге — Кутты Шаг за шагом по закону движения: Эйлер, РК4, адаптивный шаг, Верле для орбит и неявные схемы. O(T/h) шагов, у РК4 четыре вычисления правой части на шаг 2 задачи RND Алгоритм Генетический алгоритм Популяция решений, отбор, скрещивание и мутация: эволюция траектории на настоящем автодроме. O(G · N · c) 2 задачи

Задачи

Банк головоломок Поправка на сезон Судья прогнозов Время круга Есть ли лучшая кривая Когда начинать заново Погасить все лампочки Пятнашки за наименьшее число ходов

Часто рядом

классика 9 собеседования 7 карты и навигация 4 олимпиады 3 эвристика 3 точки на плоскости 3 точность вычислений 3 геоданные 3 кратчайший путь 2 граф 2 предподсчёт 2 пересечения 2