Простой, короткий, логический алгоритм (в каком направлении идти?)

Question

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

Пример:

Мы в настоящее время на 1. Мы хотим, чтобы идти на 5. Я могу видеть, что vissualy 5 ближе, поэтому мы идем направо. Также обратите внимание, что вы всегда обращены внутрь.

Answer 1

Сначала убедитесь, что каждый расчет, который вы делаете, является модулем 6 (или n). Это означает -2 по модулю 6 = 4. Затем вы можете рассчитать один раз по часовой стрелке и один против часовой стрелки. По часовой стрелке - B-A, против часовой стрелки A-B. Затем сравните эти два результата, нижний побеждает.

Пример:

А = 1, В = 5

по часовой стрелке ход: BA = 4
счетчик непрерывного ход: АВ = -4 = 2

Пример 2:

A = 5, B = 1

Перемещение по часовой стрелке: BA = 2
счетчик cw move: A -B = 4

Answer 2

clockWise = B - A < A + MAX - B 

с B> позиции А, своп соответственно.

Answer 3

Учитывая a == первой точки, и b == вторую точку

pointAtoPointB = 0 

for a to b 
    pointAtoPointB ++ 

pointBtoPointA = 0 

for b to a 
    pointBtoPointA ++ 

if pointBtoPointA > pointAtoPointB 
    go a to b 
else 
    go b to a 

Answer 4

If B > A 
    If B - A > max/2, head CCW, else CW 
Else 
    If A - B > max/2, head CW, else CCW 

т.е. если не пересекая наматывается вокруг точки (от 6 до 1) более чем на полпути вокруг, пересечь точку обертывания!

Answer 5

Вот мое решение с таблицей правды (просто для проверки справа). ABS - это абсолютное значение.

a,b | x1 = abs(b-a) < max/2 | x2 = b-a > 0 | x1 == x2 
2,3 | true     | true   | true 
1,6 | false     | true   | false 
6,1 | false     | false  | true 
5,4 | true     | false  | false 

оборота по часовой стрелке = (x1 = абс (б-а) < макс/2) == (х2 = Ь-а> 0)

Answer 6

У меня есть два рекурсивных, простые SCALA решения для Вас. Основная идея заключается в том, что путь не должен превышать половину раунда, который, случается, 3 в нашем случае, но может быть, конечно, параметризованная:

def fromAtoBClockwise (a: Int, b: Int) : Boolean = { 
    if (a > b) ! fromAtoBClockwise (b, a) 
    else b - a <= 3 } 

расстояние не должно превышать 3, но, чтобы избежать вычитания 1 - 5, мы поворачиваем параметры и инвертируем результат, если a> b.

def fromAtoBClockwise (a: Int, b: Int) : Boolean = { 
    if (a > b) fromAtoBClockwise (a, b + 6) 
    else b - a <= 3 } 

Альтернативный способ состоит в том, чтобы просто добавить 6, размер круга, в b, если он ниже.

Оба работают, но иногда отличаются результатом, если оба способа имеют одинаковую длину.

С параметром для размера и нечетного размера, вы получите тот же результат для обоих:

def fromAtoBClockwise (a: Int, b: Int, size: Int) : Boolean = { 
    if (a > b) ! fromAtoBClockwise (b, a, size) 
    else b - a <= size/2 } 


def fromAtoBClockwise (a: Int, b: Int, size: Int) : Boolean = { 
    if (a > b) fromAtoBClockwise (a, b + size, size) 
    else b - a <= size/2 } 

Test (выход конденсируется):

(1 to 5).map (a => (1 to 5).map (b => { if (a != b) println (a + " " + b + " " + fromAtoBClockwise (a, b, 5))})) 

1 2 true 1 3 true 1 4 false 1 5 false 
2 1 false 2 3 true 2 4 true 2 5 false 
3 1 false 3 2 false 3 4 true 3 5 true 
4 1 true 4 2 false 4 3 false 4 5 true 
5 1 true 5 2 true 5 3 false 5 4 false