Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 13   вперед  Ctrl
 Относительно простые задачки  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 637
Чтобы не плодить топики, здесь будет всякая ерунда на один укус.

Для начала поглумимся над классикой. Есть поезд, со множеством вагонов, без окон и т.д., замкнутый в круг, то есть последний вагон скреплен с первым. В каждом вагоне можно только включать и выключать свет, больши ничего менять нельзя, и все вагоны одинаковы.
Изначально неизвестно, где свет горит а где нет.
Надо посчитать количество вагонов, находясь внутри этого поезда и умея переходить между вагонами. Окон нет, наружу выглянуть нельзя.

Алгоритм должен работать за линейное время. То есть если вагонов окажется N штук, то всяких действий не более чем O(N)
15 янв 20, 13:35    [22059720]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 60635
Ходить вперед-назад можно?
15 янв 20, 13:49    [22059739]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 637
Aklin
Ходить вперед-назад можно?
да.

по сути всё то же самое как в оригинале, плюс ограничение на асимптотику
15 янв 20, 13:52    [22059742]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
iOracleDev
Member

Откуда:
Сообщений: 1029
Обозначим стартовый вагон буковкой A, выключим в нем свет и пойдем по ходу поезда, идем пока свет в вагонах горит, дошли до вагона с выключенным светом, обозначим его буковкой B, включаем в нем свет и идем обратно в A, если в A горит свет, значит мы обошли все вагоны, если свет в A выключен, то включаем его и возвращаемся в вагон B, выключаем в вагоне B свет, назначаем вагон B вагоном A и далее повторяем описанную процедуру, до тех пор пока не обнаружим в A свет.
16 янв 20, 00:15    [22060302]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
mayton
Member

Откуда: loopback
Сообщений: 45545
Представляя себя машиной Тьюринга.

Я могу бегать вправо(+1) влево(-1). Справа - включать свет во всех вагонах. Влево выключать.
Сначала +1,-1. Потом +2,-2 и так далее пока половина вагонов не будет включена.
При этом в уме считать.

Получается асимптоматика вроде квадратичной. Цикл с увеличивающимся внутренним циклом.

Сообщение было отредактировано: 16 янв 20, 01:27
16 янв 20, 01:26    [22060311]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
iOracleDev
Member

Откуда:
Сообщений: 1029
У меня получается по три пробежки между точками A->B->A->B, далее точка B превращается в A и все повторяется, плюс одна финальная пробежка, когда во всех вагонах будет одинаковое состояние, по моей стратегии получается максимум 4*N проходов, вроде как удовлетворяет O(N).
16 янв 20, 01:39    [22060315]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
982183
Member

Откуда: VL
Сообщений: 3350
iOracleDev
когда во всех вагонах будет одинаковое состояние,

Когда в старом вагоне будет состояние, отличное от установленного ранее.
16 янв 20, 07:26    [22060350]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 637
iOracleDev
Обозначим стартовый вагон буковкой A, выключим в нем свет и пойдем по ходу поезда, идем пока свет в вагонах горит, дошли до вагона с выключенным светом, обозначим его буковкой B, включаем в нем свет и идем обратно в A, если в A горит свет, значит мы обошли все вагоны, если свет в A выключен, то включаем его и возвращаемся в вагон B, выключаем в вагоне B свет, назначаем вагон B вагоном A и далее повторяем описанную процедуру, до тех пор пока не обнаружим в A свет.
все верно, сейчас проверил, действительно 4N в худшем случае (когда непосредственно перед самым первым вагоном выключен свет).

у меня было решение немного хуже, от 4N до 8N: ходить от некоего постоянного стартового вагона (с выключенным светом) вправо, включая везде свет и запоминая, в каком по счету вагоне последний раз был выключен, потом возвращаться и проверять стартовый. Забеги делать сначала на 1, потом на 2, потом на 4, на 8 вагонов и т.д.
16 янв 20, 10:49    [22060460]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 60635
iOracleDev
Обозначим стартовый вагон буковкой A, выключим в нем свет и пойдем по ходу поезда, идем пока свет в вагонах горит, дошли до вагона с выключенным светом, обозначим его буковкой B, включаем в нем свет и идем обратно в A, если в A горит свет, значит мы обошли все вагоны, если свет в A выключен, то включаем его и возвращаемся в вагон B, выключаем в вагоне B свет, назначаем вагон B вагоном A и далее повторяем описанную процедуру, до тех пор пока не обнаружим в A свет.


Как я понял, нельзя И метить и включать свет.
либо одно, либо другое
16 янв 20, 13:04    [22060593]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Dima T
Member

Откуда:
Сообщений: 14606
iOracleDev
Обозначим стартовый вагон буковкой A, выключим в нем свет и пойдем по ходу поезда, идем пока свет в вагонах горит, дошли до вагона с выключенным светом, обозначим его буковкой B, включаем в нем свет и идем обратно в A, если в A горит свет, значит мы обошли все вагоны, если свет в A выключен, то включаем его и возвращаемся в вагон B, выключаем в вагоне B свет, назначаем вагон B вагоном A и далее повторяем описанную процедуру, до тех пор пока не обнаружим в A свет.

Это не O(N), а O(N2), т.к. действие это не проход от А до Б, а переход из вагона в вагон.
16 янв 20, 13:34    [22060615]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 12231
Dima T
Это не O(N), а O(N2), т.к. действие это не проход от А до Б, а переход из вагона в вагон.
Там все правильно, за исключением того, что это 5N.
Ключевое место: назначаем вагон B вагоном A, т.е переход A(старый)<->B будет только при завершении обхода.
16 янв 20, 13:44    [22060621]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 637
Соколинский Борис
5N.
да, точно.
финальная пробежка будет туда и обратно по всему поезду.
16 янв 20, 13:52    [22060630]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 12231
Имя пользователя1
Соколинский Борис
5N.
да, точно.
финальная пробежка будет туда и обратно по всему поезду.
Кстати, 4N можно добиться инверсией подключения и направления основного обхода
16 янв 20, 13:57    [22060632]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Dima T
Member

Откуда:
Сообщений: 14606
Соколинский Борис
Dima T
Это не O(N), а O(N2), т.к. действие это не проход от А до Б, а переход из вагона в вагон.
Там все правильно, за исключением того, что это 5N.
Ключевое место: назначаем вагон B вагоном A, т.е переход A(старый)<->B будет только при завершении обхода.

Он ходит туда-сюда увеличивая проходимый отрезок. В худшем случае (изначально в вагоны в состоянии: 01010101010) будет такая последовательность переходов из вагона в вагон: 1,3,5,7...N, это арифметическая прогрессия, ее сумма ((1+N)/2)*N, т.е. O(N2)
16 янв 20, 14:00    [22060637]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Dima T
Member

Откуда:
Сообщений: 14606
Все-таки сначала надо определиться что означает термин "действие". Проверка света в одном вагоне это действие?
16 янв 20, 14:03    [22060639]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 637
Соколинский Борис
Имя пользователя1
пропущено...
да, точно.
финальная пробежка будет туда и обратно по всему поезду.
Кстати, 4N можно добиться инверсией подключения и направления основного обхода
не очень понял, как это.


Dima T
Соколинский Борис
пропущено...
Там все правильно, за исключением того, что это 5N.
Ключевое место: назначаем вагон B вагоном A, т.е переход A(старый)<->B будет только при завершении обхода.

Он ходит туда-сюда увеличивая проходимый отрезок. В худшем случае (изначально в вагоны в состоянии: 01010101010) будет такая последовательность переходов из вагона в вагон: 1,3,5,7...N, это арифметическая прогрессия, ее сумма ((1+N)/2)*N, т.е. O(N2)
нет.
Пройдя очередной отрезок АВАВ (то есть пройдя по нему 3 раза), он делает точку В стартовой и уже не будет за неё возвращаться.
16 янв 20, 14:04    [22060643]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 637
Dima T
Все-таки сначала надо определиться что означает термин "действие". Проверка света в одном вагоне это действие?
действие - переход в соседний вагон.
Можно ещё переключение света и проверку так назвать, но на линейность асимптотики это не влияет, потому не заморачиваемся.

Сообщение было отредактировано: 16 янв 20, 14:09
16 янв 20, 14:06    [22060644]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
iOracleDev
Member

Откуда:
Сообщений: 1029
982183
iOracleDev
когда во всех вагонах будет одинаковое состояние,

Когда в старом вагоне будет состояние, отличное от установленного ранее.

Да, оба выражения отражают одно и то же.

Aklin
Как я понял, нельзя И метить и включать свет.
либо одно, либо другое

Ничего метить нельзя, можно только ходить из вагона в вагон по ходу или против хода поезда и включать
или выключать свет в вагоне, кроме того можно считать вагоны. Буквами я их называю чтобы проще было
понять алгоритм. Например вагон с которого начали пусть будет 0-й, следующий вагон принятый новой точкой
отсчета например будет 5-й по счету от нулевого, следующий будет например 7-й по счету от 0-го и 2-й по
счету от 5-го, т.е. никаких букв мы в вагонах не рисуем.

Соколинский Борис
Там все правильно, за исключением того, что это 5N.
Ключевое место: назначаем вагон B вагоном A, т.е переход A(старый)<->B будет только при завершении обхода.

Да, посчитал последнюю пробежку по всему кругу только туда, обратно упустил, получается 5N в худшем случае, в лучшем 2N.
16 янв 20, 14:14    [22060653]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Dima T
Member

Откуда:
Сообщений: 14606
Имя пользователя1
Пройдя очередной отрезок АВАВ (то есть пройдя по нему 3 раза), он делает точку В стартовой и уже не будет за неё возвращаться.

Как не будет если
iOracleDev
... обозначим его буковкой B, включаем в нем свет и идем обратно в A ...


O(N) будет если добавить возможность "телепортации" между А и Б, т.е. переход из А в Б это одно действие, т.к. вагоны между А и Б не интересны, их состояние известно.
16 янв 20, 14:23    [22060659]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
mayton
Member

Откуда: loopback
Сообщений: 45545
Я наверное был не прав. По моему методу также нелья понять при движении вправо - выключил ли я лампочку
либо она просто уже была выключена.
16 янв 20, 14:25    [22060661]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
iOracleDev
Member

Откуда:
Сообщений: 1029
Dima T,

Нет, каждый вагон посещается не более пяти раз, в самом плохом случае получаем 5*N.
16 янв 20, 14:28    [22060664]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 12231
Имя пользователя1
Соколинский Борис
пропущено...
Кстати, 4N можно добиться инверсией подключения и направления основного обхода
не очень понял, как это.

Если при проходе B->A выключать во всех вагонах свет, то можно обратно в B не возвращаться, просто искать не первый выключенный, а первый включенный.
4N, на самом деле не получается, но будет <5N.

Сообщение было отредактировано: 16 янв 20, 14:39
16 янв 20, 14:39    [22060674]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 637
Dima T
Как не будет если
iOracleDev
... обозначим его буковкой B, включаем в нем свет и идем обратно в A ...
так ведь буквицей А каждый раз будет назван новый вагон, а не тот, с которого начали:
iOracleDev
назначаем вагон B вагоном A и далее повторяем описанную процедуру
16 янв 20, 14:41    [22060678]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 637
Соколинский Борис
Если при проходе B->A выключать во всех вагонах свет, то можно обратно в B не возвращаться, просто искать не первый выключенный, а первый включенный.
так первый включенный и будет В :) то есть всё то же самое.
16 янв 20, 14:44    [22060679]     Ответить | Цитировать Сообщить модератору
 Re: Относительно простые задачки  [new]
Dima T
Member

Откуда:
Сообщений: 14606
iOracleDev
Dima T,

Нет, каждый вагон посещается не более пяти раз, в самом плохом случае получаем 5*N.

Понял, ты продвигаешься постоянно вперед, т.е. А всегда смещается вперед, а Б где-то впереди А. Тогда O(N)
16 янв 20, 14:48    [22060687]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 13   вперед  Ctrl
Все форумы / Программирование Ответить