问C中的算法-使用数字-3在单位位置的数字

EN

更新：将Ante的观察结果和答案社区wiki结合起来。

像往常一样，在这类问题中，编写任何可行的蛮力算法都比较容易，但数学上的难度越大。你用铅笔和纸，你可以得到更好(更快)的算法。

让我们用一个速记符号:让M (i )表示1111.1(I 1)。

给定一个数n (假设n= 23)，你想要找到一个数m，使得M(m)可以被n整除。在我们找到一个可被n整除的数之前，注意:可能存在一个闭形解来求m给定的n，所以这个方法不一定是最优的。

当在M(1)，M(2)，M(3)，.上迭代时，有趣的部分显然是，如何检查给定的数是否可以被n整除，您可以实现长除法，但是任意精度算法是慢的。相反，请考虑以下几点：

假设您已经从以前的迭代中知道了M(i) mod n的值。如果是M(i) mod n = 0，那么您就完成了(M(i)是答案)，所以让我们假设它不是。你想找到M(i+1) mod n。从M(i+1) = 10 * M(i) + 1开始，您可以很容易地计算M(i+1) mod n，因为它是(10 * (M(i) mod n) + 1) mod n。这可以用固定精度算法计算，即使在n的大值下也是如此.

下面是一个函数，它计算可被n除的最小数目的函数(从Ante的Python答案转换为C)：

int ones(int n) {
        int i, m = 1;
        /* Loop invariant: m = M(i) mod n, assuming n > 1 */
        for (i = 1; i <= n; i++) {
                if (m == 0)
                        return i;  /* Solution found */
                m = (10*m + 1) % n;
        }
        return -1;  /* No solution */
}

你不必以“大数字”的方式来考虑这个问题。只要拿一张纸，用手做乘法，很快你就会找到最好的答案：)

First，让我们考虑3x结果的单位数字

 x  0 1 2 3 4 5 6 7 8 9

3x  0 3 6 9 2 5 8 1 4 7

因此，这种关系是：

what we want 0 1 2 3 4 5 6 7 8 9
 multiplier  0 7 4 1 8 5 2 9 6 3

第二个，做乘法，不要保存不必要的数字。举13为例，要生成一个'1'，我们必须选择乘数7，所以

13 * 7 = 91

好吧，省省“9”吧，现在我们面临的是9。我们必须选择乘数(11-9)%10。

13 * 4 = 52, 52 + 9 = 61

去吧！保存“6”。选择乘数(11-6)%10

13 * 5 = 65, 65 + 6 = 71

保存'7‘。选择乘数(11-7)%10

13 * 8 = 104, 104 + 7 = 111

省去“11”。选择乘数(11-11)%10

13 * 0 = 0, 0 + 11 = 11

保存“1”。选择乘数(11-1)%10

13 * 0 = 0, 0 + 1 = 1

保存“0”。哇~！当你看到'0‘时，算法就结束了！

最终，如果您在上面的一步中打印一个'1‘，这里您将得到一个'1’字符串的答案。

类似于Bolo的简单等式的解决方案，M(i+1) = 10*M(i) + 1。这里是python版本：

def ones( n ):
  i = m = 1
  while i <= n:
    if m == 0:
      return i
    m = ( ( 10 * m ) + 1 ) % n
    i += 1
  return None