@Xiran

Через какой алгоритм решать эту задачу?

Вот текст задачи:
Вам была дана задача протестировать лифт нового поколения в новом 70-этажном бизнес-центре. На обычном лифте вас подняли на 12 этаж и сопроводили до нового лифта. В этом лифте нет кнопок с номерами этажей, есть только кнопки «ВВЕРХ» и «ВНИЗ». Так же вы замечаете рядом инструкцию:

Пусть x – номер текущего этажа.

Если x – чётное и нажата кнопка «ВВЕРХ», то лифт привезёт Вас на этаж с номером 2x-1

Если x – нечётное и нажата кнопка «ВВЕРХ», то лифт привезёт Вас на этаж с номером 2x

Если x – чётное и нажата кнопка «ВНИЗ», то лифт привезёт Вас на этаж с номером x/2

Если x – нечётное и нажата кнопка «ВНИЗ», то лифт привезёт Вас на этаж с номером (x+1)/2

Если номер этажа, на который должен отправиться лифт, отсутствует – лифт не сдвинется с места.

Нумерация этажей бизнес-центра начинается с 1.

Вам можно составлять любые последовательности нажатия кнопок, и в любой момент времени можете вернуться на стартовый этаж. Сколько различных этажей можно посетить из всех возможных таких последовательностей?


Я даже не могу предположить, как она решается.
Деревья поиска?
Или держать n возможных ходов в стеке?
Или перестановки генерировать?
Или если их перебирать, то до скольки?
Буду благодарен за пример кода на C++ или псевдокода.
  • Вопрос задан
  • 678 просмотров
Решения вопроса 2
Adamos
@Adamos
Когда не знаешь, как решать задачу программно - это нормально.
Надо взять листочек и начать решать ее руками.
12 этаж, есть два варианта - вверх или вниз. Считаем их, получаем этажи, на каждом два варианта...
Внезапно доходит, что если уже рассматривал варианты для этажа, то второй раз это можно не делать, результаты будут те же.
Значит, помечаем посещенные этажи - и крутим варианты, отсекая те, которые ведут на уже посещенные.
Банальной рекурсией, например...
Из кода осталось только написать функцию, которая выдаст два варианта для текущего номера этажа - по подробной инструкции из задачи.
Ответ написан
mayton2019
@mayton2019
Bigdata Engineer
Стоя на 12 этаже можно за 1 ход попасть на 23 этах (Вверх) или на 6 этаж (Вниз).
Стоя на 6 этаже можно за 1 ход попасть на 11 этаж (ВВ) или на 3 этах.
(и так далее)

Вот такой граф получается. Немного напоминает Гипотезу Коллатца. За счет минус единички
адрес меняется четность и есть надежда что мы не зациклимся а все таки куда-то двигаемся.
Значит можно упорным баловством с кнопками куда-то приехать.

Вобщем нужен орграф с 70 вершинами и опционально с 2 ребрами для каждой вершины.
Недостижимые вершины - это этажи куда нельзя будет попасть соотвественно.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Alexandroppolus
@Alexandroppolus
кодир
Тут можно заметить вот что.
1) если идем вверх, то обратный путь будет по тем же этажам:
туда 12-23-46, обратно 46-23-12
2) если идем вниз, то обратный путь может пойти по другим этажам:
туда 12-6, обратно 6-11-22-43

итого, решение простое - тебе сначала надо пройти от 12 вверх
потом от 12 спуститься до 6 и пройти вверх
потом от 6 спуститься до 3 и тоже пройти вверх (здесь выходим на предыдущий стартовый этаж 6, завершаем)
от 3 к 2 и тоже вверх
и т.д.
т.е. каждый раз спускаться вниз на одну, после чего идти вверх, если не попали на предыдущий стартовый.

код на js
function floorCount(start, max) {
    let result = 0;
    let prevStart = -1;
    
    while (start > 0) {
        for (let x = start; x <= max && x !== prevStart; x = x % 2 ? 2 * x : 2 * x - 1) {
            result++;
        }
        prevStart = start;
        start = start < 2 ? 0 : start % 2 ? (start + 1) / 2 : start / 2;
    }

    return result;
}


Это совсем частный случай ранее упомянутого поиска в ширину/глубину, где не понадобилось множество ранее посещенных этажей (достаточно проверки на prevStart), а так же очереди/стека. То есть обошлись О(1) памяти.
По скорости выходит O(ln(start) * ln(max)), и в принципе можно сократить до O(ln(start)), если не делать внутренний цикл, а сразу посчитать по формуле, но что-то на ночь глядя не могу эту формулу смекнуть...
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы