5

假设我们有一个编号的圆圈。我们想从 A 点到 B 点,但我们不知道应该向左还是向右。你会如何使用数字来计算你应该往哪个方向走?

例子:

我们目前在 1。我们想继续 5。我可以看到 5 更接近,所以我们向右走。另请注意,您始终面向内部。

图像

4

6 回答 6

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

即,如果未穿过环绕点(从 6 到 1)超过一半,则越过环绕点!

于 2012-02-08T21:46:58.360 回答
2

首先确保您所做的每个计算都是模 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

于 2012-02-08T21:55:09.903 回答
1

我有两个递归的、简单的 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
于 2012-02-09T02:10:19.840 回答
1

这是我的真值表解决方案(只是为了检查正确)。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)

于 2012-02-08T22:25:06.127 回答
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 
于 2012-02-08T21:41:00.033 回答
-1
clockWise = B - A <  A + MAX - B

当 B > A 时,相应地交换位置。

于 2012-02-08T21:40:43.247 回答