Семинар 12.03 Подгруппа 106-2

Задачки на жадные алгоритмы:

Есть дорога с кочками. Лягушка прыгает с кочки на кочку и должна добраться из точки A в точку B за минимальное число прыжков с кочки на кочку. Известны координаты кочек на отрезке [A, B]. Лягушка может сделать прыжок длины не больше x. Придумать и доказать жадный алгоритм для достижения лягушкой цели.

Дан список степеней вершин. Можно ли построить граф, у которого степени вершин будут такими? Придумать и доказать жадный алгоритм решения задачи. В графе должны быть те и только те вершины, которые указаны в списке.