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

[KoTnaoborot]

Вот решение самой задачки.

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

Вот отрывок переписки с моей мамой в котором собсно все понятно что я имею ввиду и она.

виталя: ну вообщем это все неважно, т к в программе есть ОДНА вещь и она делает нерешаемой твою задачу. А именно, здесь есть проверка, ЕСЛИ свет включен она финиширует. То есть как только она зайдет в вагон где свет уже будет она финиширует, а поэтому логично предположить что условия задачи были такие - во всех вагонах вырублен свет и нужно все включить, как только включил программа дойдет по кругу к первому вагону где включил свет и финиширует. тем самым выполнит условия задачи
Марина: нет, условия, что где то есть, где то нет света. и программа видимо реагирует на количество вагонов и на точку где будет выключен свет
виталя: ну вообщем эта прога нифига не решает
виталя: эту задачу
виталя : а I=0 и т д это просто для того что бы нумеровать вагоны и потом она выводит число в финиширует. например прошла прога 17 вагонов, она выведет цифру 17 и завершится
виталя : а завершится прога как только дойдет до вагона где свет уже включен
виталя : можно кстати ради интереса на форум программистов выложить
виталя: там они точно скажут
виталя : я прав или нет
Марина: нет она не завершится где свет включен, так как реагирует на счет и выключеный свет
виталя: ну я на форуме выложу
виталя: ради интереса
виталя: посмотрим что ответят

Если кратко то я вижу что блок схема которая на изображении не может выполнить условия задачи потому что если в вагоне будет включен свет она выведет значение и финиширует. Я прав или нет ?

[Afrit]

sc2tv = форум програмистов... okay
Согласно блок схемы, прога выйдет на первом (по i, втором по счету) же вагоне: этот "возвращаемся на i" будет содержать номер текущего вагона, а там мы только что включили свет, GG.

[A_K]

Я так понял нарисованное решение.
Встаём в конкретный вагон - пусть он будет первым. Выключаем в нём свет, если он был включен (если выключен - ничего не делаем). Дальше двигаемся в выбранную сторону на 1 вагон, и если там был выключен свет - мы его включаем (если включен - ничего не делаем). Потом возвращаемся в первый вагон и смотрим, не включился ли там свет. Если нет - сдвигаемся в выбранную сторону на 1 вагон дальше и если там выключен свет - мы его включаем (если включен - ничего не делаем), возвращаемся обратно и смотрим. Повторяем цикл, пока рано или поздно не обнаружим, что свет в первом вагоне включился. Когда включился - значит мы обошли все вагоны.
Выглядит как корректное решение, если тебе надо посчитать количество вагонов или если тебе надо везде включить свет.

[A_K]

ну если число вагонов неизвестно и признака закольцовки нет, то невозможно написать программу которая завершится...
это не очевидно ?

Число вагонов неизвестно, но известно, что они закольцованы. Признак закольцовки тебе и надо предложить по сути с помощью включения/выключения света.

[A_K]

это невозможно.

Может быть ты условие задачи не до конца понял? Есть n вагонов, расположенных по кругу, каждый соединён с двумя соседними. Число n неизвестно, но оно конечно. В каждом вагоне изначально свет либо горит, либо не горит. Ты можешь передвигаться по вагонам в любую сторону, и включать/выключать свет на своё усмотрение. Тебе надо придумать алгоритм, который поможет посчитать количество вагонов (или включить во всех вагонах свет, например).
Что именно невозможно?

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

когда человека просят придумать случайное число он выдает 55782740. а не 1111111 потому что второе кажется (только кажется карл) ему менее случайным.
на самом деле они оба равнослучайные, но имеют разную колмагоровскую (или алгоритмическую) сложность.

Это задача не на вероятность.

[A_K]

еще раз прочти что я написал.

Я не понимаю смысла этой фразы. Мы разное значение, видимо, вкладываем в словосочетание "признак закольцовки". Для меня это правило, по которому можно определить, что ты вернулся в тот же самый вагон, сделав полный круг. Как в контексте этого определения понять фразу "никакой признак не будет надежнее простой последовательности включенных вагонов." - я не знаю.

[RobosergTV]

A_K, Как ты узнаешь, что сделал круг?

[A_K]

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

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

[Kadabra]

алгоритм наркомана аж переклинило

[A_K]

RobosergTV, свет в первом вагоне может измениться, только если мы по кругу в него пришли с обратной стороны, больше мы никак в него попасть не можем.

[A_K]

как ты поймешь что это первый вагон ?

Ты на каждом шаге возвращаешься в первый вагон и смотришь, не изменился ли там свет. Потом только сдвигаешься на 1 вагон дальше.

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

ты же не знаешь числа вагонов.

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

[RobosergTV]

A_K, Хммм, умно Вроде да, вроде решение.

[A_K]

A_K, Хммм, умно Вроде да, вроде решение.

Это стандартная задачка с какого-нибудь сайта головоломок. То есть я решение до этого уже видел. Правда, немного другое, но это вроде тоже подходит.

[Funyoka]

Проверка "Включен ли свет" всегда происходит в самом первом вагоне, потому что перед проверкой стоит переход в этот самый первый вагон.

[[Nemesis]]

Мне кажется алгоритм неверный из-за того, что он проверяется на свет (как писали выше), т.е. если свет выключен, то мы идем в начало цикла, включаем свет идем в след вагон, если свет включен, то завершаем цикл. По условию задачи, в вагонах он может быть включен или выключен хаотично, при этом длина поезда не указана. Следовательно правильнее создать цикл именно по вагонам. Что-то типа:"Идти вперед проверять при этом включен ли свет(циклом) пока поезд не закончится"
Если поезд закольцован и нет какой либо метки начала, то задача скорей всего не решаема. Имхо. (не очень силен в таких вопросах)

[Funyoka]

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

[Kadabra]

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

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

[A_K]

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

Да, блок-схема несколько упрощена - вместо "включаем если выключен и не трогаем если включен" написано просто "включаем". Ну и в конце, видимо, нужно выводить i, а не i+1, если мы количество вагонов хотим получить. То есть придраться можно, но по сути схема должна работать.

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

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

[Sader]

а что не так то он ходит по всем вагонам включает свет потом возвращается в первый и если там не горит процесс повторяется, но тут проблема в том что допустим он везде включил свет а в пятом кто то выключил он идет в первый видит что включен и финиширует

[Kadabra]

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

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