Supongamos que tenemos un círculo numerado. Queremos ir del punto A al punto B, pero no sabemos si debemos ir hacia la izquierda o hacia la derecha. ¿Cómo calcularías, usando números, en qué dirección deberías ir?Algoritmo lógico simple, corto (¿qué dirección seguir?)
Ejemplo:
Actualmente estamos en 1. Queremos seguir 5. Puedo ver que vissualy 5 está más cerca de lo que nos vamos a la derecha. También tenga en cuenta que siempre está mirando hacia adentro.
Primero asegúrese de que cada cálculo que haga es módulo 6 (o n). Eso significa -2 módulo 6 = 4. Entonces puede calcular una vez en el sentido de las agujas del reloj y una en sentido contrario a las agujas del reloj. El viaje en sentido horario es B-A, antihorario A-B. Luego compara esos dos resultados, el más bajo gana.
Ejemplo:
A = 1, B = 5
las agujas del reloj movimiento: BA = 4
de contraataque cw: AB = -4 = 2
Ejemplo 2:
A = 5, B = 1
movimiento en el sentido de las agujas del reloj: BA = 2
counter cw move: A -B = 4
¡Simple, rápido, excelente! Gracias –
Considerando a == el primer punto, y b == el segundo punto
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
Esta es una solución simple, OK para mi proyecto, supongo. Pero cuando hay más números, esto no es realmente eficiente. –
If B > A
If B - A > max/2, head CCW, else CW
Else
If A - B > max/2, head CW, else CCW
es decir, si no cruza el punto wrap-around (de 6 a 1) es más de la mitad alrededor de, ¡cruza el punto de envoltura!
Aquí está mi solución con una tabla de verdad (solo para verificar a la derecha). ABS es shor to para Absolute Value.
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
vuelta hacia la derecha = (x1 = abs (b-a)/2 < max) == (x2 = b-a> 0)
Tengo dos, soluciones Scala simples recursivo para usted. La idea básica es que el camino no debe exceder de una media caña, que pasa a ser 3 en nuestro caso, pero por supuesto puede ser parametrizada:
def fromAtoBClockwise (a: Int, b: Int) : Boolean = {
if (a > b) ! fromAtoBClockwise (b, a)
else b - a <= 3 }
la distancia no debe ser superior a 3, pero para evitar restando 1 - 5, giramos los parámetros e invertimos el resultado, si a> b.
def fromAtoBClockwise (a: Int, b: Int) : Boolean = {
if (a > b) fromAtoBClockwise (a, b + 6)
else b - a <= 3 }
Una forma alternativa es, simplemente agregar 6, el tamaño del círculo, a b, si es menor.
Ambas funcionan, pero a veces difieren en el resultado, si ambas formas son de la misma longitud.
Con el parámetro para el tamaño, y un tamaño impar, se obtiene el mismo resultado para los dos:
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 }
prueba (salida de condensado):
(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
son los números siempre en orden? ¿Cuál es su "rango" de visibilidad? – Nicholas
Sí, los números están siempre en orden y usted "ve" (sabe) todos los números. –
Realiza una resta modular (base n) y usa un umbral en n/2. – ElKamina