Алгоритм C - игра с числами - число с 3 в месте

Question

Я наткнулся на этот вопрос в интервью. Любое число с 3 в позиции единиц имеет по крайней мере один кратный, содержащий все единицы. Например, кратное 3 - 111, кратное 13 - 111111. Учитывая число, заканчивающееся на 3, меня попросили найти лучший способ найти его кратное, содержащее все 1. Теперь возможен простой подход, когда вы рассматриваете не космические проблемы, а по мере роста числа, а иногда даже если этого не происходит, int (или long int при !) в C не может содержать это кратное число. Каков оптимальный способ реализации такого алгоритма в C?

Answer 1

ОБНОВЛЕНИЕ : Включение замечаний Анте и создание сообщества ответов на вики.

Как обычно в задачах такого типа, кодирование любого работающего алгоритма грубой силы является относительно простым, но более сложным. вы делаете с карандашом и бумагой, лучший (более быстрый) алгоритм вы можете получить.

Давайте используем сокращенную запись: пусть M (i) означает 1111 ... 1 (i).

Учитывая число n (скажем, n = 23), вы хотите найти число m такое, что M (m) делится на n. Простой подход заключается в проверке 1, 11, 111, 1111, ... до тех пор, пока мы не найдем число, делимое на 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 (переведено в C из ответа Ante's Python):

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

Answer 2

Вам не нужно рассматривать этот вопрос как «большое число». Просто возьмите бумагу, сделайте умножение вручную, и вскоре вы найдете лучший ответ:)

Сначала , давайте рассмотрим цифру единиц результата 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'. WOW ~! Когда вы видите «0», алгоритм заканчивается!

Наконец , если вы напечатаете «1» для одного шага выше, здесь вы получите строковый ответ «1».

Answer 3

Как и решение Боло с более простым равенством 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

Answer 4

, кратное 23: 1111111111111111111111

#include <stdio.h>

int
main () {
        unsigned int ones = 1;
        double result, by = 23, dividend = 1;
        while (dividend) {
            result = dividend / by;
                if (result < 1) {
                    dividend = dividend * 10 + 1;
                        ++ones;
                } else {
                    dividend -= by * (int)result;
                }
        }
        while (ones--) {
            printf("1");
        }
        printf("\n");
    return 0;
}