C中的算法 - 玩数字 - 3在单位位置的数字 [英] Algorithm in C - playing with numbers - number with 3 in units place

问题描述

我在一次采访中遇到了这个问题.任何单位位置为 3 的数字至少有一个包含所有 1 的倍数.例如，3 的倍数是 111，13 的倍数是 111111.给定一个以 3 结尾的数字，我被问到找到包含全 1 的倍数的最佳方法.现在有一种简单的方法是可能的，您不考虑空间问题，但随着数量的增长，有时即使不考虑，int(或 long int在那！)在C中不能容纳那个倍数.在 C 中实现这种算法的最佳方法是什么?

I came across this question in an interview. Any number with 3 in its units position has at least one multiple containing all ones. For instance, a multiple of 3 is 111, a multiple of 13 is 111111. Given a number ending in 3, I was asked the best method to find its multiple containing all 1's. Now a straightforward approach is possible, where you do not consider space issues but as the number grows, and sometimes even if it doesn't, an int (or a long int at that!) in C cannot hold that multiple. What is the optimal way to implement such an algorithm in C?

推荐答案

更新:结合 Ante 的观察并制作答案社区 wiki.

UPDATE: Incorporating Ante's observations and making the answer community wiki.

像往常一样，在这类问题中，编写任何可行的蛮力算法都相对容易，但更多的是数学.你用铅笔和纸做，你可以获得更好(更快)的算法.

As usual in this type of problems, coding any working brute-force algorithm is relatively easy, but the more math. you do with pencil and paper, the better (faster) algorithm you can get.

让我们使用简写符号:让 M(i) 表示 1111...1(i 个).

Let's use a shorthand notation: let M(i) mean 1111...1 (i ones).

给定一个数 n(假设 n = 23)，你想找到一个数 m，使得 M(m) 可以被 n 整除.一个直接的方法是检查 1, 11, 111, 1111, ... 直到我们找到一个能被 n 整除的数.注意:可能存在 封闭形式解决方案 用于在给定 n 的情况下找到 m，所以这种方法不一定是最优的.

Given a number n (let's say n = 23), you want to find a number m such that M(m) is divisible by n. A straightforward approach is to check 1, 11, 111, 1111, ... until we find a number divisible by n. Note: there might exist a closed-form solution for finding m given n, so this approach is not necessarily optimal.

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

When iterating over M(1), M(2), M(3), ..., the interesting part is, obviously, how to check whether a given number is divisible by n. You could implement long division, but arbitrary-precision arithmetic is slow. Instead, consider the following:

假设您已经从之前的迭代中知道 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 值，也可以使用固定精度算术计算.

Assume that you already know, from previous iterations, the value of M(i) mod n. If M(i) mod n = 0, then you're done (M(i) is the answer), so let's assume it's not. You want to find M(i+1) mod n. Since M(i+1) = 10 * M(i) + 1, you can easily calculate M(i+1) mod n, as it's (10 * (M(i) mod n) + 1) mod n. This can be calculated using fixed-precision arithmetic even for large values of n.

这是一个计算可被 n 整除的最小数目的函数(从 Ante 的 Python 答案翻译为 C):

Here's a function which calculates the smallest number of ones which are divisible by n (translated to C from Ante's Python answer):

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 */
}

这篇关于C中的算法 - 玩数字 - 3在单位位置的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！