Thuật toán đơn giản, ngắn, logic (hướng đi nào?)

Question

Giả sử chúng ta có một vòng tròn được đánh số. Chúng tôi muốn đi từ điểm A đến điểm B nhưng chúng tôi không biết liệu chúng tôi có nên đi sang trái hay phải. Làm thế nào bạn, bằng cách sử dụng con số, tính toán trong đó hướng bạn nên đi?

Ví dụ:

Chúng tôi hiện đang trên 1. Chúng tôi muốn đi trên 5. Tôi có thể thấy rằng vissualy 5 là gần gũi hơn vì vậy chúng tôi đi về phía bên phải. Cũng lưu ý rằng bạn luôn phải đối mặt với bên trong.

Answer 1

Trước tiên hãy đảm bảo rằng mọi phép tính bạn thực hiện là modulo 6 (hoặc n). Điều đó có nghĩa là -2 modulo 6 = 4. Sau đó, bạn có thể tính toán một lần một chuyến đi theo chiều kim đồng hồ và một bộ đếm ngược chiều kim đồng hồ. Chuyến đi theo chiều kim đồng hồ là B-A, ngược chiều kim đồng hồ A-B. Sau đó so sánh hai kết quả đó, kết quả thấp hơn sẽ thắng.

Ví dụ:

A = 1, B = 5

chiều kim đồng hồ di chuyển: BA = 4
truy cập cw di chuyển: AB = -4 = 2

Ví dụ 2:

A = 5, B = 1

di chuyển theo chiều kim đồng hồ: BA = 2
lượt truy cập di chuyển: -B = 4

Answer 2

clockWise = B - A < A + MAX - B 

với B> vị trí A, hoán đổi cho phù hợp.

Answer 3

Xét a == điểm đầu tiên, và b == điểm thứ hai

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 

tức là nếu không vượt bọc xung quanh điểm (6-1) là hơn nửa vòng trái đất, băng qua điểm quấn quanh!

Answer 5

Đây là giải pháp của tôi với bảng chân lý (chỉ để kiểm tra bên phải). ABS là shor để cho giá trị tuyệt đối.

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 

lượt chiều kim đồng hồ = (x1 = abs (b-a) < max/2) == (x2 = b-a> 0)

Answer 6

Tôi có hai, giải pháp đơn giản scala đệ quy cho bạn. Ý tưởng cơ bản là, như vậy không được vượt quá một vòng rưỡi, mà sẽ xảy ra là 3 trong trường hợp của chúng tôi, nhưng tất nhiên có thể được parametrized:

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

Khoảng cách không được vượt quá 3, nhưng để tránh trừ 1 - 5, chúng ta chuyển các tham số và đảo ngược kết quả, nếu a> b.

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

Một cách khác là, chỉ cần thêm 6, kích thước của vòng tròn, thành b, nếu nó thấp hơn.

Cả hai công việc, nhưng đôi khi khác nhau về kết quả, nếu cả hai cách có chiều dài bằng nhau.

Với tham số cho kích thước và kích thước lẻ, bạn sẽ có được kết quả tương tự cho cả hai:

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 } 

thử nghiệm (sản lượng ngưng tụ):

(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