Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Регистрация Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Flasher.ru > Флейм

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 24.01.2016, 18:56
miramax вне форума Посмотреть профиль Отправить личное сообщение для miramax Посетить домашнюю страницу miramax Найти все сообщения от miramax
  № 21  
Ответить с цитированием
miramax
 
Аватар для miramax

Регистрация: Oct 2005
Адрес: Борисоглебск
Сообщений: 1,702
Отправить сообщение для miramax с помощью ICQ Отправить сообщение для miramax с помощью AIM Отправить сообщение для miramax с помощью MSN Отправить сообщение для miramax с помощью Yahoo Отправить сообщение для miramax с помощью Skype™
Что-то как-то подозрительно, что никто не решил.
выключаем свет в нулевом вагоне

n = 0;
while (true)
n++
идём влево на n
если в вагоне -n+1 (который мы точно выключали) - свет горит - значит кол-во вагонов return n+1
вагон -n - выключаем свет

возвращаемся в начальную точку на +n вагонов, в нулевой вагон
идём вправо на n вагонов
влючаем свет

возвращаемся в исходную точку на -n вагонов.


Отдельно обработать случай для 1 и двух вагонов.
__________________
AS3 | www.FLAPS.ru | Русские флэшеры самые умные флэшеры в мире. ©

Старый 24.01.2016, 19:03
undefined вне форума Посмотреть профиль Отправить личное сообщение для undefined Найти все сообщения от undefined
  № 22  
Ответить с цитированием
undefined

Регистрация: Oct 2006
Сообщений: 2,269
вот только для составления ряда надо знать сколько в нем членов

Добавлено через 1 минуту
miramax,верно загуглил?)

Старый 24.01.2016, 19:05
miramax вне форума Посмотреть профиль Отправить личное сообщение для miramax Посетить домашнюю страницу miramax Найти все сообщения от miramax
  № 23  
Ответить с цитированием
miramax
 
Аватар для miramax

Регистрация: Oct 2005
Адрес: Борисоглебск
Сообщений: 1,702
Отправить сообщение для miramax с помощью ICQ Отправить сообщение для miramax с помощью AIM Отправить сообщение для miramax с помощью MSN Отправить сообщение для miramax с помощью Yahoo Отправить сообщение для miramax с помощью Skype™
Какого ряда ?
В моём псевдокоде есть только одна переменная - n
__________________
AS3 | www.FLAPS.ru | Русские флэшеры самые умные флэшеры в мире. ©

Старый 24.01.2016, 19:06
undefined вне форума Посмотреть профиль Отправить личное сообщение для undefined Найти все сообщения от undefined
  № 24  
Ответить с цитированием
undefined

Регистрация: Oct 2006
Сообщений: 2,269
это сложность порядка O(N^2) получается.Интересно есть ли более оптимальные решения?

Добавлено через 31 секунду
Цитата:
Какого ряда ?
это я дарку отвечал

Старый 24.01.2016, 19:08
miramax вне форума Посмотреть профиль Отправить личное сообщение для miramax Посетить домашнюю страницу miramax Найти все сообщения от miramax
  № 25  
Ответить с цитированием
miramax
 
Аватар для miramax

Регистрация: Oct 2005
Адрес: Борисоглебск
Сообщений: 1,702
Отправить сообщение для miramax с помощью ICQ Отправить сообщение для miramax с помощью AIM Отправить сообщение для miramax с помощью MSN Отправить сообщение для miramax с помощью Yahoo Отправить сообщение для miramax с помощью Skype™
Цитата:
Сообщение от undefined Посмотреть сообщение
это сложность порядка O(N^2) получается.Интересно есть ли более оптимальные решения?
Почему же ? мы линейно ходим по массиву влево и вправо по вектору, выключая и включая свет по одному разу за проход. сложность - n*2
Можем хранить ссылку на последний левый и правый вагоны после каждого прохода.
__________________
AS3 | www.FLAPS.ru | Русские флэшеры самые умные флэшеры в мире. ©

Старый 24.01.2016, 19:16
undefined вне форума Посмотреть профиль Отправить личное сообщение для undefined Найти все сообщения от undefined
  № 26  
Ответить с цитированием
undefined

Регистрация: Oct 2006
Сообщений: 2,269
ну да, тут можно оптимизировать с т.з. языка.Но для реального человека, перед которым стоит задача сложность нахождения ответа будет побольше т.к. придется таки честно все отбегать(считаем проход вагона+переключение лампочки за элементарную операцию).Насчет N^2 я не уверен.

Старый 24.01.2016, 19:18
miramax вне форума Посмотреть профиль Отправить личное сообщение для miramax Посетить домашнюю страницу miramax Найти все сообщения от miramax
  № 27  
Ответить с цитированием
miramax
 
Аватар для miramax

Регистрация: Oct 2005
Адрес: Борисоглебск
Сообщений: 1,702
Отправить сообщение для miramax с помощью ICQ Отправить сообщение для miramax с помощью AIM Отправить сообщение для miramax с помощью MSN Отправить сообщение для miramax с помощью Yahoo Отправить сообщение для miramax с помощью Skype™
Ок. Соль в том , что то что мы точно включали и выключали должны пересечься в какой-то точке.
посылаем двух человек влево.
Один за ход включает два вагона и двигается дальше, второй ВЫключает по одному и двигает дальше.
первый проверяет предыдущий вагон. Если предыдущий вагон - включен - значит они встретились.
__________________
AS3 | www.FLAPS.ru | Русские флэшеры самые умные флэшеры в мире. ©

Старый 24.01.2016, 19:19
dark256 вне форума Посмотреть профиль Отправить личное сообщение для dark256 Посетить домашнюю страницу dark256 Найти все сообщения от dark256
  № 28  
Ответить с цитированием
dark256
 
Аватар для dark256

блогер
Регистрация: Apr 2008
Адрес: SPb
Сообщений: 3,712
Записей в блоге: 5
Отправить сообщение для dark256 с помощью ICQ Отправить сообщение для dark256 с помощью Skype™
Нда. А теперь алгоритмически опредлим - жив ли кот в ящике Шредингера.
Когда правильный ответ будет опубликован - черкните плиз в личку кто-нть.
Следить за темой стало скучно.
__________________
FLASHER.MAP SOUNDSTAGE / CS3 / AS2

Старый 24.01.2016, 19:26
undefined вне форума Посмотреть профиль Отправить личное сообщение для undefined Найти все сообщения от undefined
  № 29  
Ответить с цитированием
undefined

Регистрация: Oct 2006
Сообщений: 2,269
вообщем упрощено так:
Последовательно проверяем гипотезы что в составе N вагонов:
проверка гипотезы что в составе n вагонов:
идем в одну сторону n вагонов и всюду выключаем свет.В n+1-ом -включаем.Возвращаемся назад на n+1 вагонов.Если в первом свет включен - значит в составе и было n - вагонов.Если нет - повторяем проверку для n+1 и т.д. до победного конца.

Старый 24.01.2016, 19:27
miramax вне форума Посмотреть профиль Отправить личное сообщение для miramax Посетить домашнюю страницу miramax Найти все сообщения от miramax
  № 30  
Ответить с цитированием
miramax
 
Аватар для miramax

Регистрация: Oct 2005
Адрес: Борисоглебск
Сообщений: 1,702
Отправить сообщение для miramax с помощью ICQ Отправить сообщение для miramax с помощью AIM Отправить сообщение для miramax с помощью MSN Отправить сообщение для miramax с помощью Yahoo Отправить сообщение для miramax с помощью Skype™
Цитата:
Сообщение от undefined Посмотреть сообщение
вообщем упрощено так:
Последовательно проверяем гипотезы что в составе N вагонов:
проверка гипотезы что в составе n вагонов:
идем в одну сторону n вагонов и всюду выключаем свет.В n+1 -включаем.Возвращаемся назад на n+1 вагонов.Если в первом свет включен - значит в составе и было n - вагонов.Если нет - повторяем проверку для n+1 и т.д. до победного конца.
Чем это отличается от псевдокода ? Я забыл умножить n на два, перед return ) Т.к. проходов "гипотез" будет в два раза меньше
Цитата:
Сообщение от miramax
n = 0;
while (true)
n++
идём влево на n
если в вагоне -n+1 (который мы точно выключали) - свет горит - значит кол-во вагонов return n+1
вагон -n - выключаем свет

возвращаемся в начальную точку на +n вагонов, в нулевой вагон
идём вправо на n вагонов
влючаем свет

возвращаемся в исходную точку на -n вагонов.
Задачка пустяк ) давай ещё =)
__________________
AS3 | www.FLAPS.ru | Русские флэшеры самые умные флэшеры в мире. ©

Создать новую тему Ответ Часовой пояс GMT +4, время: 14:15.
Быстрый переход
  « Предыдущая тема | Следующая тема »  
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 14:15.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2020, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.