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

Вот решение самой задачки. http://savepic.ru/8631973m.jpg

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

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

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

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

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

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

Цитата:

---

Сообщение от toster

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

---

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

Цитата:

---

Сообщение от toster

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

---

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

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

Цитата:

---

Сообщение от toster

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

---

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

Цитата:

---

Сообщение от toster

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

---

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

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

Цитата:

---

Сообщение от toster

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

---

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

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

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

Цитата:

---

Сообщение от toster

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

---

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

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

Цитата:

---

Сообщение от toster

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

---

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

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

Цитата:

---

Сообщение от RobosergTV

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

---

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

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

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

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

Цитата:

---

Сообщение от toster

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

---

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

Цитата:

---

Сообщение от Funyoka

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

---

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

Цитата:

---

Сообщение от Kadabra

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

---

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

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

Цитата:

---

Сообщение от A_K

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

---

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