Cool Folders ФотоЛандия КиноЭкран ИсраБард "Леда"
ГлавнаяНовостиИгрыФорумыДневникиЧатыВходРегистрация  Пейджер Пейджер Справка  88:88 

В список тем|Статистика|Поиск

 Посты: | 1-19  Форумы:

О вагонах и алгоритмах№ 1
Большой Грызь

Дата : 16-05-06, Втр, 05:46:43

Еще одна относительно простая, но красивая задачка

Есть бесконечная железная дорога, рядом с которой в каких-то местах стоят два светофора. Около светофоров на рельсах стоят два вагона:


Вагонами можно управлять, загрузив в каждый из них программу, в которой можно использовать следующие команды:
1) ВЛЕВО НА X - Сдвинуться влево на Х длин вагона
2) ВПРАВО НА Х - Сдвинуться вправо на Х длин вагона
3) ПЕРЕЙТИ К СТРОЧКЕ № - перейти к указанной строчке в программе
4) ПЕРЕЙТИ К СТРОЧКЕ №, ЕСЛИ (условие) - перейти к указанной строчке в программе, если выполняется условие. Если условие не выполняется, тогда программа переходит к следующей команде.
5) В программе можно пользоваться глобальными переменными (к примеру Х=1, Х=Х+1, Х=Х-1)
6) Можно пользоваться условием "ОКОЛО СВЕТОФОРА", которое выполняется, если вагон в этот момент находится рядом с любым из светофоров.

Задача: написать такую программу, которая будучи загруженной без каких-либо модификаций в оба вагона, столкнёт их друг с другом.
 ...everything is possible cause noone has to hide beyond the invisible...
[ 16-05-06, Втр, 14:46:40 Отредактировано: Большой Грызь ]
Профиль 

О вагонах и алгоритмах№ 2
madoldman

Дата : 17-05-06, Срд, 00:32:06

Да, эт хорошая задачка!

Можно чуть-чуть усложнить условие: вместо 1) и 2)

1А) ВЛЕВО НА 1 - Сдвинуться влево на 1 длину вагона
2А) ВПРАВО НА 1 - Сдвинуться вправо на 1 длину вагона

Надо также чуть-чуть уточнить
6) Можно пользоваться условием "ОКОЛО СВЕТОФОРА", которое выполняется, если вагон в этот момент находится рядом с любым из светофоров.

"ОКОЛО СВЕТОФОРА" не различает светофоры! Нельзя использовать, к примеру, "ОКОЛО СВЕТОФОРА с которого начали".

Профиль 

О вагонах и алгоритмах№ 3
Большой Грызь

Дата : 17-05-06, Срд, 01:06:07

1А) ВЛЕВО НА 1 - Сдвинуться влево на 1 длину вагона
2А) ВПРАВО НА 1 - Сдвинуться вправо на 1 длину вагона

С этим уже возникла некоторая проблема


"ОКОЛО СВЕТОФОРА" не различает светофоры! Нельзя использовать, к примеру, "ОКОЛО СВЕТОФОРА с которого начали".

Ну, в условии вообще-то и не говорится о том, что светофоры отличаются
Но, используя переменные, можно "пометить" начальный светофор
 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 

О вагонах и алгоритмах№ 4
madoldman

Дата : 17-05-06, Срд, 02:13:46

Автор: Большой Грызь
Дата : 17-05-06, Срд, 08:06:07

1А) ВЛЕВО НА 1 - Сдвинуться влево на 1 длину вагона
2А) ВПРАВО НА 1 - Сдвинуться вправо на 1 длину вагона

С этим уже возникла некоторая проблема



Какая?

Профиль 

О вагонах и алгоритмах№ 5
Большой Грызь

Дата : 17-05-06, Срд, 02:17:48

Какая?

Такая, что нужно еще определять, за какое время выполняется каждая команда.. и учитывать это (т.е. по сути учитывать кол-во команд)
 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 

О вагонах и алгоритмах№ 6
madoldman

Дата : 17-05-06, Срд, 20:36:07

Автор: Большой Грызь
Дата : 17-05-06, Срд, 09:17:48

Какая?

Такая, что нужно еще определять, за какое время выполняется каждая команда.. и учитывать это (т.е. по сути учитывать кол-во команд)



Это еше зачем?? Вовсе нет!
Достаточно что бы были выполнены след. два условия:
1. Вагоны одинаковые, так что время выполнения любои команды одинаково для обоих вагонов.
2. Время выполнения команды "влево на один" равно времени выполнения команды "вправо на один"

А если эти условия не выполнены тогда и исxодная задача не имеет решения!

Профиль 

О вагонах и алгоритмах№ 7
madoldman

Дата : 17-05-06, Срд, 20:42:21

В дополнение, для тех кто слышал про машины Тьюринга:

На ленте есть две единицы, остальное - нули.

1.Наидите Т-машину такую что если две ее копии начинают с единиц, они окажутся на однои клетке (Подсказка: достаточно 1 STATE машины!!!)

2.Наидите Т-машину такую что если две ее копии начинают с единиц, они окажутся на однои клетке при дополнительном условии: писать на ленту запрешено. (У мну получилось с 7 STATES, наверное можно и лучше!)
 
[ 18-05-06, Чтв, 05:22:38 Отредактировано: madoldman ]
Профиль 

О вагонах и алгоритмах№ 8
Урод и мразь

Дата : 18-05-06, Чтв, 07:14:26

Можно и без переменных.

1. Налево
2. Налево
3. Направо
4. Если не у светофора, к строке 1
5. Налево
6. К строке 5
Профиль 

О вагонах и алгоритмах№ 9
Большой Грызь

Дата : 18-05-06, Чтв, 07:16:13

Можно и еще короче

1. Налево
2. Если не у светофора, к строке 1
3. Налево
4. Налево
5. к строке 3
 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 

О вагонах и алгоритмах№ 10
Урод и мразь

Дата : 18-05-06, Чтв, 18:38:44

Оба будут двигаться влево. или имеется в виду, что вычисления занимают ненулевое время?
Профиль 

О вагонах и алгоритмах№ 11
madoldman

Дата : 18-05-06, Чтв, 18:55:13

Автор: Урод и мразь
Дата : 19-05-06, Птн, 01:38:44

Оба будут двигаться влево. или имеется в виду, что вычисления занимают ненулевое время?


Ага, но можно обойтись без этого и, даже, почти в два раза короче

1. Налево
2. Если не у светофора, к строке 1
3. К строке 2

Профиль 

О вагонах и алгоритмах№ 12
Феликс

Дата : 19-05-06, Птн, 00:57:39

Автор: madoldman
Дата : 19-05-06, Птн, 01:55:13

1. Налево
2. Если не у светофора, к строке 1
3. К строке 2



Не понял. Левый вагон будет всё время двигаться налево, а правый стоять у левого светофора.
Как дже они столкнутся?
 
[ 19-05-06, Птн, 07:58:16 Отредактировано: Феликс ]
Профиль 

О вагонах и алгоритмах№ 13
Большой Грызь

Дата : 19-05-06, Птн, 01:18:18

Автор: Урод и мразь
Дата : 19-05-06, Птн, 01:38:44

Оба будут двигаться влево. или имеется в виду, что вычисления занимают ненулевое время?

Вот об этом я и говорил:
нужно еще определять, за какое время выполняется каждая команда.. и учитывать это (т.е. по сути учитывать кол-во команд)

Т.е., нужно учитывать, что в первом цикле (строчки 1-2) есть две команды, из которых одна команда смещения, а во втором цикле (строки 3-4-5) есть три команды, из которых две команды смещения. Так что вагон, "крутящийся" во втором цикле будет догонять.

К примеру возьмём 12 "шагов" в программе. Первый цикл выполнится 6 раз и вагон, соответственно, сдвинется на 6 своих длин. Второй цикл выполнится 4 раза и вагон, соответственно, сдвинется на 4*2=8 своих длин.
 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 

О вагонах и алгоритмах№ 14
Krasnaja Shapka

Дата : 19-05-06, Птн, 04:12:07

Автор: Урод и мразь
Дата : 18-05-06, Чтв, 14:14:26

1. Налево
2. Налево
3. Направо
4. Если не у светофора, к строке 1
5. Налево
6. К строке 5

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

п.с. хотя конечно и на строчку длиннее...
 Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.
[ 19-05-06, Птн, 11:12:38 Отредактировано: Krasnaja Shapka ]
Профиль 

О вагонах и алгоритмах№ 15
Большой Грызь

Дата : 19-05-06, Птн, 04:34:49

да и скорость догоняющего вагона в три раза выше!

Каким образом ты получил три раза??
Что первый, что второй вагон будут смещаться на одну длину влево за цикл.
Первый цикл ровно в два раза длинее второго.. Так что у меня выходит только в два раза.. Если выполнение каждой команды занимает одно и то же время (включая и команды проверки и перехода к строчкам)
 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 

О вагонах и алгоритмах№ 16
Krasnaja Shapka

Дата : 19-05-06, Птн, 05:07:29

Автор: Большой Грызь
Дата : 19-05-06, Птн, 11:34:49

да и скорость догоняющего вагона в три раза выше!

Каким образом ты получил три раза??
Что первый, что второй вагон будут смещаться на одну длину влево за цикл.
Первый цикл ровно в два раза длинее второго.. Так что у меня выходит только в два раза.. Если выполнение каждой команды занимает одно и то же время (включая и команды проверки и перехода к строчкам)


да... было немного не корректно сравнивать скорость решения УиМа при условии что операторы неперемещения выполняются мгновенно, а в твоем и моем за тоже время что и операторы перемещения , ну ладно... у него в два раза, а у нас в 4/3...
 Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.
[ 19-05-06, Птн, 12:08:03 Отредактировано: Krasnaja Shapka ]
Профиль 

О вагонах и алгоритмах№ 17
Большой Грызь

Дата : 19-05-06, Птн, 05:10:31

у нас в 4/3

у вас - не знаю, а у меня - 3/2
 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 

О вагонах и алгоритмах№ 18
Krasnaja Shapka

Дата : 19-05-06, Птн, 05:17:10

Автор: Большой Грызь
Дата : 19-05-06, Птн, 12:10:31

у нас в 4/3

у вас - не знаю, а у меня - 3/2


у тебя:
1/2 одного, 2/3 догоняющего... 2/3:1/2=2/3*2/1=4/3
 Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.
Профиль 

О вагонах и алгоритмах№ 19
Большой Грызь

Дата : 19-05-06, Птн, 05:23:02

уговорил
 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 


Вы не зарегистрированы либо не вошли в портал!!!
Регистрация или вход в портал - в главном меню.

 Посты: | 1-19  Форумы:

В список тем|Статистика|Поиск

 Просмотров:   003859    Постингов:   000019 

Сейчас на портале (последние действия): 9 гостей, 1 зарегистрированный, 0 скрытых, LogUl
Сейчас на странице (были):никого нет
0.100 сек (14 запросов за 0.032 сек) © 2002-2020, Cool Folders by Cool Programmer from Nazareth, admin@coolfold.com