Это для вас
Чтобы ваши мозги сегодня закипели пораньше, вот вам сверхсложная задача.
Тимлид решил выдать новичку за хорошую работу новый ноутбук, а заодно решил убедиться, что его можно повысить в должности и поднять зарплату. Для этого он убрал ноутбук в сейф и сказал:
Ноутбук — в сейфе, и он твой, если ты сможешь открыть этот сейф. Пароль от сейфа — 9 цифр, от 1 до 9, причём каждая встречается только один раз. При этом:
- девятизначное число пароля делится на 9 без остатка
- если убрать последнюю цифру, то оставшееся восьмизначное число делится на 8 без остатка
- если ещё убрать последнюю цифру, то оставшееся семизначное число делится на 7 без остатка
- такое правило будет работать всё время: сколько цифр в числе, на эту цифру число делится без остатка.
Какой пароль нужно ввести новичку, чтобы получить ноутбук и повышение?
«А? Чё?» — произнёс новичок. Он не понял ничего из того, что ему сказал тимлид, поэтому решил задачу тупейшим перебором.
Сначала он написал функцию проверки, нет ли в числе повторяющихся цифр и ноля:
// проверяем число на уникальность цифр и на наличие ноля
function isUnique(digit) {
// переводим в строку
N = String(digit);
// если есть ноль — проверка не прошла
if (N.match(/0/)) {return false}
// если есть повторяющиеся цифры — проверка не прошла
if ((/([0-9]).*?\1/).test(N)) {return false} else {return true}
}Потом он сделал функцию, которая проверяет, делятся ли все внутренние числа на количество их разрядов:
// проверяем, делятся ли все вложенные числа на количество разрядов
function isDivided(digit) {
// переменная для промежуточных вычислений
var temp;
// по умолчанию считаем, что делятся
res = true;
// если число сразу не делится на 9 — проверка не прошла
if (digit % 9 != 0) {res = false}
// перебираем все остальные разряды
for (let i = 1; i < 9; i++) {
// отбрасываем ненужные разряды справа
temp = Math.floor(digit/10**i)
// если результат не делится на количество разрядов — проверка не прошла
if (temp % (9 - i) != 0) {res = false}
}
return res;
}А потом он написал цикл, который перебирает и сразу проверяет все девятизначные числа:
// перебираем все девятизначные числа
for (let i = 100000000; i < 999999999; i++) {
// если оно неуникальное — берём следующее
if (isUnique(i) == false) { continue }
// если оно делится по всем правилам — выводим его
if (isDivided(i)) { console.log(i) }
}Запустил в браузере и получилось:
Алгоритмическая сила!
А вот его код целиком:
// проверяем число на уникальность цифр и на наличие ноля
function isUnique(digit) {
// переводим в строку
N = String(digit);
// если есть ноль — проверка не прошла
if (N.match(/0/)) {return false}
// если есть повторяющиеся цифры — проверка не прошла
if ((/([0-9]).*?\1/).test(N)) {return false} else {return true}
}
// проверяем, делятся ли все вложенные числа на количество разрядов
function isDivided(digit) {
// переменная для промежуточных вычислений
var temp;
// по умолчанию считаем, что делятся
res = true;
// если число сразу не делится на 9 — проверка не прошла
if (digit % 9 != 0) {res = false}
// перебираем все остальные разряды
for (let i = 1; i < 9; i++) {
// отбрасываем ненужные разряды справа
temp = Math.floor(digit/10**i)
// если результат не делится на количество разрядов — проверка не прошла
if (temp % (9 - i) != 0) {res = false}
}
return res;
}
// перебираем все девятизначные числа
for (let i = 100000000; i < 999999999; i++) {
// если оно неуникальное — берём следующее
if (isUnique(i) == false) { continue }
// если оно делится по всем правилам — выводим его
if (isDivided(i)) { console.log(i) }
}Это сложная задача, поэтому чтобы не запутаться, обозначим все цифры буквами: ABCDEFGHI.
Теперь посмотрим на чётные группы цифр — каждая из них должна делиться на 2, а это значит, что последняя цифра в каждой группе чётная:
Получается, что B,D,F,H — чётные цифры. Соответственно, A,C,E,G,I — нечётные.
Чтобы понять, какие цифры где должны стоять, будем применять по очереди правила и свойства деления к каждой группе.
Делим на 5
Начнём с деления на 5: чтобы число делилось на 5 без остатка, оно должно заканчиваться на 0 или 5. Это значит, что E — или 0, или 5. Но в нашем наборе цифр нет ноля, поэтому E = 5:
Делим на 4
Чтобы число нацело делилось на 4, его последние две цифры вместе тоже должны делиться на 4. Получается, что CD делится нацело на 4. Мы знаем, что C нечётное, а D — чётное — выпишем все комбинации, при которых это делится на 4:
12 16
32 36
52 56
72 76
92 96
Видно, что D принимает только два значения — 2 и 6:
Делим на 8
Применим то же правило деления на 4 к восьмизначному числу ABCDEFGH. Логика такая: если число делится на 8, то и на 4 оно тоже делится как на делитель восьмёрки. Это значит, что H тоже равно 2 или 6:
Это значит, что оставшиеся числа B и F равны 4 или 8:
Делим на 3
Число из первых трёх цифр ABC делится на 3 — это ясно из условия задачи. Но число ABCDEF тоже делится на 3, потому что оно делится на 6, а значит — одновременно на 2 и 3. Но раз число из первых трёх цифр в ABCDEF делится на 3 (по условию), то и второе число из цифр DEF тоже делится на 3 без остатка:
Теперь применим сюда те знания о числах, которые мы получили раньше:
Выходит, что DEF может быть одним из четырёх чисел:
254
258
654
658
Но только два из них делятся на 3 без остатка — 258 и 654. Это значит, что если D = 2, то F = 8, а если D = 6, то F = 4. Добавим эту связь на общую схему:
Долгая и нудная работа с числами
Теперь так же проверим число ABC, учитывая, что в середине стоит 4 или 8. Вот все числа, которые можно так составить:
143 147 149
341 347 349
741 743 749
941 943 947
183 187 189
381 387 389
781 783 789
981 983 987
Выберем из них те, что делятся на 3 без остатка:
147 183 189
381 387 741
783 789 981
987
Но мы выяснили, что число DEF может быть только 258 или 654. Если мы добавим эти три цифры в те варианты ABC, что делятся на 3 без остатка, то получим ABCDEF, которое должно делиться на 6 без остатка:
147258 183258 189258 381258 387258 741258
783258 789258 981258 987258
147654 183654 189654 381654 387654 741654
783654 789654 981654 987654
Теперь отбросим все числа, где цифры встречаются больше одного раза. Вот что останется:
147258 183654 189654 381654
387654 741258 783654 789654
981654 987654
А теперь самое сложное: чтобы получить семизначное число, добавим к каждому в конец нечётную цифру, которая ещё не встречалась в этом числе. Например, в числе 147258 использовались 1, 7 и 5, поэтому в конец можно добавить только 3 или 9. Сделаем так с каждым числом и получим 20 чисел, которые нужно будет проверить:
1472583 1836547 1896543 3816547
3876541 7412583 7836541 7896541
9816543 9876541
1472589 1836549 1896547 3816549
3876549 7412589 7836549 7896543
9816547 9876543
Из этих чисел всего три делятся на 7 без остатка: 1472583, 3816547 и 7836549.
Теперь к этим трём числам добавим восьмую цифру. Помним правило выше: если D = 2, то H = 6:
14725836 38165472 и 78365492
Нацело на 8 делится только одно число — 38165472. При этом у нас осталась неиспользованная девятка, которая при добавлении в конец и даст нам нужное число: 381654729.
Проверим, выполняются ли все условия:
381654729 / 9 = 42406081
38165472 / 8 = 4770684
3816547 / 7 = 545221
381654 / 6 = 63609
38165 / 5 = 7633
3816 / 4 = 954
381 / 3 = 127
38 / 2 = 19
3 / 1 = 3
