Двоякі числа
Натуральне число називається двояким, якщо в його десятковому запису зустрічається не більше двох різних цифр.
1. Створіть програму, що знаходить двояке число, яке найменше відрізняється від заданого натурального числа N за модулем.
Вхідні дані
Значення N - натуральне число, що не перевищує 232 , вводиться з клавіатури або задається як константа.
Вихідні дані (виводяться на екран чи зберігаються у файл)
Значення M - найближче до N двояке число (якщо знайдеться два таких числа, то M - найменше з них), виводиться на екран.
2. Заповніть тестову таблицю за результатами роботи програми:
Номер тесту |
N |
M |
1 | 123 | 122 |
2 | 51 | |
3 | 7777 | |
4 | 1299 | |
5 | 9867 | |
6 | 9043 | |
7 | 9050 | |
8 | 10632 | |
9 | 26354 | |
10 | 998877 |
Аналіз розв'язку задачі «Двоякі числа»
Для вирішення задачі скористаємося методом послідовного перебору. Будемо перевіряти числа, починаючи з N і поступово віддаляючись від N: спочатку такі, що відрізняються від N на 1 (менше на -1, більше на +1), потім на 2 (менше на -2, більше на +2), потім на 3 і т.д.
Введемо допоміжні змінні:
M - поточне число, яке піддається перевірці;
модуль різниці між M і N зберігатимемо у змінній d, знак різниці - у змінній sign, яка набуватиме значень -1 (M < N) або +1 (M > N);
с[1] і с[2] - змінні для зберігання двох різних цифр двоякого числа;
k - кількість знайдених різних цифр у числі M;
a - допоміжна змінна, використовувана для виділення цифр числа M;
F - змінна-прапорець, яка зберігає значення 0, доки двояке число не знайдене, і набуває значення 1, якщо таке число знайдене.
Шукане значення M можна знайти за допомогою такого алгоритму:
{виводимо M - двояке число, найближче до заданого N}
Наведемо пояснення щодо роботи операторів d:= d+(sign+1)div2; sign:=-sign. Значення d зростає на 1, якщо sign дорівнює +1, і не змінюється, якщо sign дорівнює -1. Знак sign кожного разу змінюється на протилежний.
Отже, послідовність значень M, що перевіряються на двоякість у циклі repeat-until, є такою: M=N (d = 0, sign =+1), M=N-1 (d = 1, sign = -1), M=N+1 (d = 1, sign =+1), M=N-2 (d = 2, sign = -1), M=N+2 (d = 2, sign = +1) і т.д.
Тестова таблиця з результатами роботи програми:
Номер тесту |
N |
M |
1 | 123 | 122 |
2 | 51 | 51 |
3 | 7777 | 7777 |
4 | 1299 | 1311 |
5 | 9867 | 9888 |
6 | 9043 | 9009 |
7 | 9050 | 9090 |
8 | 10632 | 11000 |
9 | 26354 | 26266 |
10 | 998877 | 998888 |
Журі оцінило надіслані розв'язки наступним чином:
№ | Учасник | Кількість балів |
1 | Сергій Сальніков | 4 |