python - 计算两个不同数字的倍数之间的差

Question

这是一个算法问题。为了简单起见，假设我有两个 double ，A 和 B。我想构造一个函数，该函数将在 A 的下一个倍数或 B 的下一个倍数之前给出差值(如果有意义的话)。

例如，假设 A 是 3，B 是 5。

考虑倍数:(3,6,9,12,15) 和 (5,10,15)。

我希望函数输出:(3, 2, 1, 3, 1, 2, 3)，因为需要 3 个单位才能达到 3，然后再需要 2 个单位才能达到 5，然后 1 到 6，然后 3 到 9，等等...

我希望这是有道理的。理想情况下，它是一个 Python 风格的生成器(尽管我是用 Arduino ~ C++ 编写的)。我需要它快点 - 非常快。

任何帮助将不胜感激。我的伪代码如下，但并不是那么好。

a = 3
b = 5

current = 0
distToA = a
distToB = b
for i in xrange(100):
  if distToA > distToB: #B comes first
    print "Adding {0}".format(distToB)
    current += distToB
    distToA -= distToBb
    distToB = b
  elif distToB > distToA: #A comes first
    print "Adding {0}".format(distToA)
    current += distToA
    distToB -= distToA
    distToA = a
  else: #Equal
    print "Adding {0}".format(distToA)
    current += distToA #Arbitrarily, could be distToB
    distToA = a
    distToB = b

编辑:如果有多个值，这看起来怎么样？不仅是a和b，还有c、d、e等等。我想我会做更多的 if 语句，但成本更高(每个分支更多的操作)。

Answer 1

不清楚为什么您对现有的代码不满意。如果是因为有“太多” if 测试，那么无需进行任何测试就很容易:

def diffgen(a, b):
    from itertools import cycle
    diffs = []
    current = 0
    ab = a*b
    while current < ab:
        nextone = min((current // a + 1) * a,
                      (current // b + 1) * b)
        diffs.append(nextone - current)
        yield nextone - current
        current = nextone
    for d in cycle(diffs):
        yield d

请注意，一旦到达 a*b，差异序列就会重复，因此无需再进行计算。