Помогите понять задачку в блок схеме за 9 класс. Спор с мамой, она считает я не прав.

[Hibonicus]

Я буду выражатся наиболее популярным языком будющего

// Сразу выключаем свет в предидущем вагоне (для простоты пока )
current.prev.isOn = false

// Вот функция для решения
function solve(x,y){

// идём в следующий вагон
const next = x.next

// проверяем включён ли в нём свет
if(next.isOn){

// если включён, то идём в следующем вагон и запомним что для того чтобы вернутся назад нужно пройти ещё один вагон и как бы вызваем эту функцию снова
return solve(next.next,y+1)
} else {

// если выключен, то возвращаемся на столько вагонов назад, сколько мы прошли до этого и проверяем включён ли он
if(vagon(-y-1).isOn === false) {

// если он выключен, то снова как бы вызываем эту функцию, только последний вагон теперь начальный, а текущий - последний (ну мы типа начали идти с конца ) и при этом включаем там свет
vagon(-y-1).isOn = true
solve(vagon(-y).prev, y)

// если он включён, то поздравляем себя и испытываем чувство гордости - мы везде включили свет и количство вагонов которое мы прошли является длиной этого рекурсивного поезда
} else {return y}
}
}

const result = solve(vagon(0),0)

если кто-то будет выключать свет, то мы можем просто включать его по пути пока идём до конца, это не влияет тут не на что

[Funyoka]

да это понятно, только когда ты пройдёшь все вагоны то получится так ты ещё до возвращения на это самое количество вагонов один раз круг уже прошёл и получится так что в первом вагоне когда ты его увидишь свет будет включён, но ты не будешь знать что это первый вагон, а потом пойдёшь круг обратно, и тут вопрос если триггер срабатывает не один раз и не только на включение то когда ты вернёшься в первый вагон он всё равно будет выключен если же он срабатывает одноразово, то тогда да, это решение :frog:

Ты делаешь моему мозгу больно. мне трудно понять твой текст.

[Konstantin.V]

return solve(next.next,y+1)

Так ты ограничишь длину возможного состава размером стека, причем, на ровном месте

if(vagon(-y-1).isOn === false) {

Если вагоны можно индексировать, задача во многом теряет смысл, не так ли

[Hibonicus]

Если вагоны можно индексировать, задача во многом теряет смысл, не так ли

Мы не индексируем, мы просто считаем количество которое нужно пройти
а vagon(-y-1) это просто я как бы координаты так написал для простоты ну типо нужно пройти у+1 вагонов назад

Так ты ограничишь длину возможного состава размером стека, причем, на ровном месте

Ващето из-за хвостовой рекурсии ограничения стека не будет

[Revvy]

Ты делаешь моему мозгу больно. мне трудно понять твой текст.

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

[Konstantin.V]

Мы не индексируем, мы просто считаем количество которое нужно пройти
а vagon(-y-1) это просто я как бы координаты так написал для простоты ну типо нужно пройти у+1 вагонов назад

Oops, пардон, я поленился разобраться до конца в том, что ты пишешь, перед тем, как комментировать. Но тогда vagon нужен еще параметр -- относительно чего ходим

И вот здесь:

if(vagon(-y-1).isOn === false) {

// если он выключен, то снова как бы вызываем эту функцию, только последний вагон теперь начальный, а текущий - последний (ну мы типа начали идти с конца ) и при этом включаем там свет
vagon(-y-1).isOn = true
solve(vagon(-y).prev, y)

Ты точно с индексами не намудрил? Зачем нам специально включать свет в самом первом вагоне?

Ващето из-за хвостовой рекурсии ограничения стека не будет

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

[Hibonicus]

Ты точно с индексами не намудрил? Зачем нам специально включать свет в самом первом вагоне?

Для простоты объясненения, на самом деле это конечно не обязательно Ну и если во всех вагонах свет изначально включён, то всё сломается

Но тогда vagon нужен еще параметр -- относительно чего ходим

Ну да, но тогда уж не относительно чего ходим, а направлиние, т.е. при разворотах .next меняется на .prev и наоборот

[Konstantin.V]

Hibonicus, Не, что-то мне всё равно не нравится. Почему у тебя и под if и в присвоении стоят одинаковые индесы: -y-1

- - - Добавлено - - -

тогда уж не относительно чего ходим, а направлиние

В смысле? А наша текущая точка? Глобальная переменная? Зачем тогда первый параметр в solve?

[Hibonicus]

Hibonicus, Не, что-то мне всё равно не нравится. Почему у тебя и под if и в присвоении стоят одинаковые индесы: -y-1

Ну vagon это как состояние же я имел ввиду что нужно пройти назад y-1 шагов и посмотреть, включён ли он там, если включён, то мы закончили, если выключен, то мы разворачиваемся и идём в обратную сторону

[Konstantin.V]

Ну vagon это как состояние же я имел ввиду что нужно пройти назад y-1 шагов и посмотреть, включён ли он там, если включён, то мы закончили, если выключен, то мы разворачиваемся и идём в обратную сторону

Вот тут конкретно что происходит, можешь объяснить?

if(vagon(-y-1).isOn === false) {
vagon(-y-1).isOn = true

[A_K]

Зря сомневаешься. Можно улучшить

Ну кстати я могу попробовать за O(n*log(n)).
Сначала идём на 1 вагон влево включаем свет, возвращаемся проверяем, потом на 2, везде включаем, возвращаемся проверяем, потом на 4, везде включаем, возвращаемся, проверяем, потом на 8, везде включаем, возвращаемся проверяем и так далее. Через O(n) операций мы обнаружим, что свет в первом вагоне включен, и мы знаем, что на последнем шаге мы включали свет в k вагонах, где n/2 <= k <= n. То есть теперь нам нужно найти один из k вагонов, и после каждой операции нужно возвращаться назад максимум на n+k вагонов, чтобы проверять, горит ли свет в первом. Двоичный поиск вроде подходит. То есть пробегаемся по всем k вагонам, в половине зажигаем свет, в половине гасим. Возвращаемся назад, смотрим, в какой из половин находится первый вагон, эту половину также разбиваем пополам и так далее. На пробегание по k элементам тратим O(n), на возвращение тратим O(n), количество таких итераций O(log(n)), плюс первые O(n), в итоге получаем O(n)+[O(n)+O(n)]*O(log(n))=O(n*log(n)).

[Konstantin.V]

O(n*log(n))

Умница!

[Hibonicus]

В смысле? А наша текущая точка? Глобальная переменная? Зачем тогда первый параметр в solve?

ну считай что вместо vagon(x) должно быть
for (let i =0; i!==x; i++){
current = current.prev
}

[SlGunz]

Ну vagon это как состояние же я имел ввиду что нужно пройти назад y-1 шагов и посмотреть, включён ли он там, если включён, то мы закончили, если выключен, то мы разворачиваемся и идём в обратную сторону

Не ломай голову в реальности такой задачи не будет, а что-то похожее ты сможешь решить проще.

[Konstantin.V]

O(n*log(n))

Я бы даже сказал... Умница!!!

[Hibonicus]

А ваще самый простой вариант это просто напахомить в первом вагоне

[Konstantin.V]

ну считай что вместо vagon(x) должно быть
for (let i =0; i!==x; i++){
current = current.prev
}

OK. Т.е. current таки глобальная переменная? А что тогда такое х?

- - - Добавлено - - -

То, которое

solve(x

[Funyoka]

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

Я не понимаю, что ты хочешь мне сказать.
Мы отсчитываем каждый раз сколько вагонов прошли и запоминаем каждый раз это число.
Да один круг сначала мы пройдем в одну сторону, потом вернемся. Увидим, что свет в вагоне изменился, значит мы сделали круг. Всё, задача решена.

[Hibonicus]

Konstantin.V,
Я имел ввиду
function vagon(current, x){
for (let i =0; i!==y; i++){
current = current.prev
}
}
и внутри той штуки
vagon(x,y+1)

[Kawaii Worm]

Вы все думаете не о том - почему у него мама подписана как Марина и с какой радости мама - взрослый человек закусилась с сыном из-за такой фигни.

На основе вышеприведенных условий можем сделать 2 вывода:

Мама - не мама
Мама девочку хотела

Нужно больше данных для продолжения