Задача про программиста и сто дверей
easy

Задача про программиста и сто дверей

Обойди их все

В длинном коридоре есть сто дверей, подписанных номерами, изначально все двери закрыты. Программист проходит мимо дверей, меняя их состояние: закрытые открывает, а открытые — закрывает. В первый обход он касается всех дверей, чей номер кратен единице, во второй — чей номер кратен двум, в третий — трём, в четвёртый — четырём. Всего программист делает сто таких обходов. Если что, кратен — это значит, что номер двери делится на это число без остатка.

Какие двери останутся открытыми после сотого обхода?

Представим нашу задачу визуально. До первого обхода программиста все сто дверей закрыты:

Задача про программиста и сто дверей

В первый обход программист меняет состояние каждой двери, то есть открывает их:

Задача про программиста и сто дверей

Во второй обход он закрывает все двери с номером, кратным двум, то есть каждую вторую: 2, 4, 6, 8, 10, 12 и так далее.

Задача про программиста и сто дверей

В третий обход он закрывает или открывает все двери с номером, кратным трём, — каждую третью: 3, 6, 9, 12, 15, 18 и так далее.

Задача про программиста и сто дверей

Попробуем порассуждать и для примера возьмём дверь с номером 50. Поскольку число 50 кратно числам 1, 2, 5, 10, 25 и 50, получается, что программист коснётся этой двери в первый, второй, пятый, десятый, двадцать пятый и пятидесятый обходы. Вот как будет меняться состояние двери:

  1. Открыто (первый обход, когда программист коснётся всех дверей с номером, кратным 1).
  2. Закрыто (второй обход, когда программист коснётся всех дверей с номером, кратным 2).
  3. Открыто (пятый обход, когда программист коснётся всех дверей с номером, кратным 5).
  4. Закрыто (десятый обход, когда программист коснётся всех дверей с номером, кратным 10).
  5. Открыто (двадцать пятый обход, когда программист коснётся всех дверей с номером, кратным 25).
  6. Закрыто (пятидесятый обход, когда программист коснётся всех дверей с номером, кратным 50).

Получается, что двери, которых программист коснётся чётное число раз, после сотого обхода останутся закрытыми. А двери, которых программист коснётся нечётное число раз, останутся открытыми.

Проанализируем эту ситуацию и выведем закономерность. Дверь с номером 50 будет открыта и закрыта за шесть обходов:

Задача про программиста и сто дверей

При умножении номеров первого и последнего, второго и предпоследнего и третьего и четвёртого обходов мы получим число номера двери — 50:

1 × 50 = 50

2 × 25 = 50

5 × 10 = 50

Похожей будет закономерность для всех дверей, которых программист коснётся чётное число раз. А какой она будет для остальных дверей?

Представим дверь с номером X, которой программист коснётся нечётное число раз, например пять:

Задача про программиста и сто дверей

Получается, что для такой двери будут верны следующие уравнения:

F1 × F5 = X

F2 × F4 = X

F3 × F3 = X

Последнее уравнение получается квадратным:

F32 = X

Из этого следует, что открытыми останутся двери, номера которых получаются из умножения номера обхода на него же: 

1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

Задача про программиста и сто дверей

Для решения на Python нам нужно будет учесть два момента:

  1. Нумерация в списках идёт с нуля, поэтому для точного номера двери нам нужно будет прибавить к индексу единицу.
  2. Команда диапазона range() не включает в себя правую границу, поэтому если написано range(100), то в диапазоне окажутся числа от 0 до 99. А если мы укажем два параметра — range(1,101), то в диапазоне будут числа от 1 (оно включается) до 100 (потому что 101 не включается).

Зная это, напишем простой код, который за нас пройдёт по 100 раз мимо всех дверей и откроет (1) и закроет их (0) по правилам из условия.

# создаём пустой список дверей
doors = []
# теперь создаём сто новых дверей
for i in range(100):
    # и делаем все их закрытыми
    doors.append(0)
# делаем 100 проходов
for i in range(1,101):
    # и в каждом проходе смотрим все двери
    for j in range(100):
        # если номер двери нацело делится на номер прохода
        if (j+1) % i == 0:
            # если она закрыта
            if doors[j] == 0:
                # открываем её
                doors[j] =  1
            # а если открыта
            else:
                # то закрываем 
                doors[j] = 0
# смотрим в итоге все двери, в каком они состоянии
for i in range(100):
    # если очередная дверь открыта
    if doors[i] == 1:
        # то выводим её номер
        print(i+1)

Обложка:

Алексей Сухов

Корректор:

Ирина Михеева

Вёрстка:

Маша Климентьева

Соцсети:

Юлия Зубарева

Любите такие задачи? Подойдите поближе
Внизу кнопка, при нажатии на нее вы попадете на витрину курсов «Практикума» с нуля. Выбираете там то, что вам близко, и погружаетесь в профессию. Через год-полтора вы работаете в какой-нибудь ИТ-компании. И там вы решаете подобные задачи, но уже за деньги. Старт бесплатно.
Начать бесплатно
Любите такие задачи? Подойдите поближе Любите такие задачи? Подойдите поближе Любите такие задачи? Подойдите поближе Любите такие задачи? Подойдите поближе
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
easy