假设我们有一个编号的圆圈。我们想从 A 点到 B 点,但我们不知道应该向左还是向右。你会如何使用数字来计算你应该往哪个方向走?
例子:
我们目前在 1。我们想继续 5。我可以看到 5 更接近,所以我们向右走。另请注意,您始终面向内部。
If B > A
If B - A > max/2, head CCW, else CW
Else
If A - B > max/2, head CW, else CCW
即,如果未穿过环绕点(从 6 到 1)超过一半,则越过环绕点!
首先确保您所做的每个计算都是模 6(或n
)。这意味着 -2 模 6 = 4。然后您可以计算一次顺时针行程和一次逆时针行程。顺时针行程为BA,逆时针行程为AB。然后比较这两个结果,较低的获胜。
例子:
A = 1, B = 5
顺时针移动:BA = 4
逆顺时针移动:AB = -4 = 2
示例 2:
A = 5, B = 1
顺时针移动:BA = 2
逆顺时针移动:AB = 4
我有两个递归的、简单的 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 }
另一种方法是,如果 b 较小,只需将圆的大小加 6。
两者都有效,但如果两种方式的长度相等,有时结果会有所不同。
使用大小参数和奇数大小,两者的结果相同:
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 }
测试(输出压缩):
(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
这是我的真值表解决方案(只是为了检查正确)。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 = abs(ba) < max/2 ) == ( x2 = ba > 0)
考虑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
clockWise = B - A < A + MAX - B
当 B > A 时,相应地交换位置。