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

问题描述

我在接受采访时碰到了这个问题。 任何数目与在其单元位置3具有至少一个多含全1。例如，3的倍数是111，13的倍数为111111给定一个号码3的结局，有人问我是最好的方法找到它含有多全1。 现在，一个简单的方法是可行的，在这里你不用考虑空间问题，但随着数量的增加，有时甚至如果没有，一个 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?

推荐答案

更新：结合安特的意见和作出的回答社区维基

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（我的）

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 ，所以这种方法并不一定是最佳

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整除。你可以实现长除法，但是的 arbitrary- precision算术是缓慢的。相反，考虑以下几点：

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:

假设你已经知道，从previous迭代，的M（i）的值模N 。如果 M（I）模N = 0 ，然后就大功告成了（ M（I）是答案） ，所以我们假设它不是。你想找到 M（1 + 1）模N 。由于 M（1 + 1）= 10 * M（I）+ 1 ，你可以很容易地计算 M（1 + 1）模N ，因为它是（10 *（M（I）MOD N）+ 1）模N 。这可以通过使用固定precision算术甚至对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整除（从安特的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屋！