Вавилонская башня

9 Август 2019 - Время чтения: 7 минуты

Условие задачи: Вавилоняне построили башню бесконечной высоты. На первом этаже - одна комната, на следующих двух - по две, и так далее. Башню оборудовали лифтом. Нужно научить его определять по номеру комнаты номер этажа, и какая она по счёту на этом этаже.

Первые десять этажей вавилонской башни:

27  28  29  30
23  24  25  26
19  20  21  22
15  16  17  18
  12  13  14
   9  10  11
   6   7   8
     4   5
     2   3
       1

Решение: Заметим, что этажи можно сгруппировать в блоки NxN комнат, где N - номер этажа. Можно довольно легко найти номер блока, в котором находится комната. Для этого нужно просто суммировать квадраты натуральных чисел. Возьмём для примера комнату №11. Суммируем квадраты:

1 = 1
1 + 4 = 5
1 + 4 + 9 = 13

Очевидно, комната №11 находится в третьем блоке. При этом, пока мы суммировали квадраты, мы нашли ещё и то, что на предыдущих двух этажах - 5 комнат. Значит, комната №11 является шестой в своём блоке. Зная номер комнаты внутри блока, можно найти номер этажа в блоке и смещение комнаты на этом этаже. Правда, нам нужен номер этажа в башне, а не в конкретном блоке, но это тоже довольно легко находится.

Ещё пара хинтов:

  1. Комнаты и этажи удобнее нумеровать с нуля.
  2. Лучше не складывать квадраты, а вычитать их из номера комнаты. Если номер комнаты стал отрицательным - значит, произошёл "перелёт", нужно отменить последнее вычитание. В результате получим номер комнаты в блоке.

Программа на языке C99
#include <stdio.h>
 
int main(void)
{
    int apart;
    scanf("%d", &apart);
    --apart;
    int block = 1;
    int floor = 0;
    for (;;) {
        apart -= block * block;
        if (apart < 0) break;
        floor += block;
        ++block;
    }
    apart += block * block;
    floor += apart / block;
    apart %= block;
    printf("%d %d\n", floor + 1, apart + 1);
    return 0;
}

Программа на языке Python
apart = int(input()) - 1
block = 1
floor = 0
while True:
    apart -= block * block
    if apart < 0: break
    floor += block
    block += 1
apart += block * block
floor += apart // block
apart %= block
print(floor + 1, apart + 1)

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

Currently there are no comments, so be the first!

Коротко обо мне

Меня зовут Вадим Тукаев, я репетитор по информатике и программированию. Вы можете сконтактировать со мной по почте vadimtukaev@gmail.com или по скайпу pol6energetik. Рассмотрю и другие предложения о сотрудничестве, включая, но не ограничиваясь, написание заказного ПО для Windows/Linux.

Категории