Question

Укажите наибольшее натуральное трёхзначное число , при вводе которого будут напечатаны числа 1 и 2. #include int main() {
int x, a = 0, b = 0;
std::cin >> x;
while (x > 0) {
if (x % 8 % 3 > 1) a++;
if (x % 8 % 3 < 1) b++;
x /= 8;
}
std::cout << a << " " << b;
}

Что делает код, в принципе, понятно. Хотелось б алгоритм решения подобного для подбора числа.

Answer 1

949

Объяснение:

Так как каждый раз производится целочисленное деление на 8, удобно рассмотреть восьмеричную запись числа. Алгоритм анализирует последнюю цифру текущего значения: если при делении на 3 она даёт остаток 2, то увеличивается a; если остаток 0 — увеличивается b.

Приоритет подбора числа таков:

1. Количество цифр (чем больше цифр, тем больше число; если бы требовалось найти наименьшее число, мы бы первым делом уменьшали количество цифр);

2. Цифры слева направо (чтобы число было максимальным, нужно максимизировать самую первую цифру, затем вторую и т. д.; аналогично для поиска минимального числа — минимизируем слева направо).

Количество цифр уже известно — 3, но это применимо для числа в десятичной системе счисления. Пусть x — искомое число. Тогда $100_{10}\leq x_{10}\leq 999_{10}\Leftrightarrow 144_8\leq x_8\leq 1747_8$. Максимальное количество цифр в его восьмеричной записи — 4. Попробуем подобрать четырёхзначное число.

Известно, что цифр с остатками при делении на 3, отличными от 1, ровно 3 (1 с остатком 2 и 2 с остатком 0). Первая цифра — это 1, больше быть не может. Она даёт остаток 1 и не влияет на a и b. Тогда остальные цифры не должны иметь остаток 1. Пусть вторая цифра — 7. Она даёт остаток 1, что не подходит. Тогда пусть вторая цифра — 6. Она даёт остаток 0, увеличивает b на 1. Аналогично третья цифра не может быть 7, а только 6. b снова увеличилось на 1 и стало равным 2. Значит, больше цифр с остатком 0 быть не может. Четвёртая цифра не может быть 7, 6. Пусть она равна 5. Тогда a увеличилось на 1, a = 1, b = 2. Искомое число — 1665₈ = 949₁₀.