Вы не сможете решить эту задачу про повышение и пароль — Журнал «Код» программирование без снобизма

Попробуйте бесплатный тренажёр «Основы математики для цифровых профессий».

Любите математику? <br> Это для вас’ decoding=’async’ loading=’lazy’>
</a>
</div>
</section></div>

<p>Чтобы ваши мозги сегодня закипели пораньше, вот вам сверхсложная задача. </p>

<p>Тимлид решил выдать новичку за хорошую работу новый ноутбук, а заодно решил убедиться, что его можно повысить в должности и поднять зарплату. Для этого он убрал ноутбук в сейф и сказал:</p>

<p>Ноутбук — в сейфе, и он твой, если ты сможешь открыть этот сейф. Пароль от сейфа — 9 цифр, от 1 до 9, причём каждая встречается только один раз. При этом:</p>

<div class=

девятизначное число пароля делится на 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

Текст:

Михаил Полянин