Я столкнулся с этим вопросом в интервью. Любое число с 3 в его позиции единиц имеет по крайней мере один кратный, содержащий все. Например, кратное 3 равно 111, кратное 13 - 111111. Учитывая число, заканчивающееся на 3, мне предложили наилучший метод найти его множественное число, содержащее все 1. Теперь возможен простой подход, когда вы не рассматриваете проблемы с пространством, но по мере роста числа, а иногда даже если это не так, int (или long int при этом!) в C не может удерживать это несколько. Каков оптимальный способ реализации такого алгоритма в C?
Алгоритм в C - игра с цифрами - число с 3 в единицах места
Ответ 1
ОБНОВЛЕНИЕ: включение наблюдений Ante и создание ответной вики сообщества.
Как обычно в этом типе проблем, кодирование любого алгоритма работы с грубой силой относительно просто, но чем больше математика. вы используете карандаш и бумагу, лучший (более быстрый) алгоритм, который вы можете получить.
Позвольте использовать сокращенное обозначение: пусть 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. Вы можете реализовать long division, но арифметика произвольной точности медленный. Вместо этого учтите следующее:
Предположим, что вы уже знаете, начиная с предыдущих итераций, значение 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 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 */
}
Ответ 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" .
Ответ 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
Ответ 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;
}