Укажите наибольшее натуральное трёхзначное число , при вводе которого будут напечатаны числа 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;
}
Что делает код, в принципе, понятно. Хотелось б алгоритм решения подобного для подбора числа.
#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;
}
Что делает код, в принципе, понятно. Хотелось б алгоритм решения подобного для подбора числа.
More Questions From This User See All
Answers & Comments
Verified answer
Ответ:
949
Объяснение:
Так как каждый раз производится целочисленное деление на 8, удобно рассмотреть восьмеричную запись числа. Алгоритм анализирует последнюю цифру текущего значения: если при делении на 3 она даёт остаток 2, то увеличивается a; если остаток 0 — увеличивается b.
Приоритет подбора числа таков:
1. Количество цифр (чем больше цифр, тем больше число; если бы требовалось найти наименьшее число, мы бы первым делом уменьшали количество цифр);
2. Цифры слева направо (чтобы число было максимальным, нужно максимизировать самую первую цифру, затем вторую и т. д.; аналогично для поиска минимального числа — минимизируем слева направо).
Количество цифр уже известно — 3, но это применимо для числа в десятичной системе счисления. Пусть x — искомое число. Тогда
. Максимальное количество цифр в его восьмеричной записи — 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₁₀.