Question

На прямой в начале координат сидит кузнечик. Из любой точки, где он находится, он может прыгнуть на 33 см или на 55 см в любую сторону. На какое наименьшее (ненулевое) расстояние он может удалиться от начала координат? Пример. Если кузнечик может прыгать на 5 см или 3 см, то он может удалиться на 1 см. Например, так: прыгнуть два раза вправо на 5 см, а затем три раза влево на 3 см.

Answer 1

# Код на ruby 2.2.3p173
def zadanie(jump1, jump2)
    min = jump1
    for i in 1..1000
        next if (i*jump1)%jump2 == 0 or (i*jump2)%jump1 == 0

        if min > (i*jump1)%jump2
            min = (i*jump1)%jump2
            p [min, "#{i} * #{jump1} - #{i*jump1/jump2} * #{jump2}"]
        end

        if min > (i*jump2)%jump1
            min = (i*jump2)%jump1
            p [min, "#{i} * #{jump2} - #{i*jump2/jump1} * #{jump1}"]
        end
    end
    return min
end
# # Примеры применения
p zadanie(33, 55)

Вывод
[22, "1 * 55 - 1 * 33"]
[11, "2 * 33 - 1 * 55"]
11

Т.е. минимум при 2 * 33 - 1 * 55 = 11

Answer 2

Эта задача может быть решена с помощью математической теории чисел. В частности, она связана с теорией Эрдёша-Гиндса, которая изучает расстояния между точками на числовой прямой, когда точки могут перемещаться только на определенные значения.

Заметим, что любое расстояние, которое может быть получено кузнечиком, является неотрицательным целым числом. Мы можем рассмотреть все возможные расстояния, которые можно получить, и найти наименьшее из них.

Для этого мы начнем с расстояния 0 и будем последовательно добавлять к нему все возможные значения, которые может достичь кузнечик. При этом мы будем отбрасывать все значения, которые мы уже получили ранее. Мы продолжим этот процесс, пока не найдем следующее значение, которое мы не можем получить.

Воспользуемся алгоритмом, который будет хранить все возможные значения, которые мы получили, и добавлять новые значения в процессе перебора. Мы можем использовать множество (set) для этого, так как оно автоматически отбрасывает повторяющиеся значения. В начале, мы будем иметь только значение 0 во множестве.

Каждый раз, когда мы добавляем новое значение в множество, мы будем проверять, не может ли кузнечик достичь этого значения, прыгнув из любого из предыдущих значений. Для этого мы будем генерировать все возможные комбинации прыжков из предыдущих значений, чтобы достичь нового значения.

После того, как мы нашли наименьшее значение, которое мы не можем получить, мы можем вывести его.

В Python коде это может выглядеть так:

pythonCopy code
def find_smallest_distance(jumps):
    values = {0}
    for i in range(1, 100):
        new_values = set()
        for v in values:
            new_values.add(v + jumps[0])
            new_values.add(v + jumps[1])
        for j in range(2, i + 1):
            for v1 in values:
                for v2 in values:
                    new_values.add(abs(v1 - v2) + jumps[0])
                    new_values.add(abs(v1 - v2) + jumps[1])
        missing_values = sorted(set(range(i + 1)) - values)
        if missing_values:
            return missing_values[0]
        values = new_values

Здесь jumps - это список возможных прыжков кузнечика (в нашем случае [33, 55]).

Мы начинаем с множества values,