Здравствуйте, rg45, Вы писали:

R>Должен сразу сказать, дабы избежать обвинений в плагиате, задачу придумал не я, но она мне очень нравиится. Делюсь.
R>Итак, есть плоская бесконечная регулярная сетка с прямоугольной ячейкой (или квадратной — не имеет значения). Каждая ячейка имеет пару координат — X и Y. По этой сетке ходит робот, управляемый заложенной в него программой. Система команд робота: "шагнуть по X", "шагнуть против X", "шагнуть по Y", "шагнуть против Y" — всего 4 направления движения. В начальный момент времени робот находится в ячейке с координатами X=0, Y=0. Задача: написать для робота программу движения. Маршрут робота должен проходить по всем ячейкам (без пропусков), удовлетворяющим условию: X >= 0 и Y >= 0, при этом робот должен посетить каждую ячейку ровно один раз. Ограничения: 1) нельзя заводить никаких переменных (счетчиков, указателей... никаких); 2) Для ветвления программы можно использовать только лишь проверку условия: X==0||Y==0 и бесконечный безусловный цикл. Разумеется, текст программы должен быть конечным (более того, не очень длинным).

R>Решение можно представить либо в виде псевдокода, либо графически, изобразив маршрут движения робота (как показывает практика, этого вполне достаточно).

Придумал (пока графическое только — код поленился писать) решение, верное при следующих поправках к условию:
1. Маршрут робота должен проходить по всем ячейкам (без пропусков), удовлетворяющим условию: X >= 0 и Y >= 0, однако робот может посещать и другие ячейки...
2. Для ветвления программы можно использовать проверку условия: X==0||Y==0, безусловный цикл и оператор выхода из цикла
Вот оно (сорри за качество — на телефон фоткал):

Там кружком обведен начальный этап, его программируем вручную, ну а дальше — в цикле
1. Вверх, лесенкой вправо вниз, влево
2. Дважды вниз, лесенкой влево вниз
3. Лесенкой влево вверх
4. Дважды вверх, лесенкой вправо вверх
Естественно, лесенки реализуются безусловными циклами, в которых есть if(X==0||Y==0) break;

Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, rg45, Вы писали:

R>>Должен сразу сказать, дабы избежать обвинений в плагиате, задачу придумал не я, но она мне очень нравиится. Делюсь.
R>>Итак, есть плоская бесконечная регулярная сетка с прямоугольной ячейкой (или квадратной — не имеет значения). Каждая ячейка имеет пару координат — X и Y. По этой сетке ходит робот, управляемый заложенной в него программой. Система команд робота: "шагнуть по X", "шагнуть против X", "шагнуть по Y", "шагнуть против Y" — всего 4 направления движения. В начальный момент времени робот находится в ячейке с координатами X=0, Y=0. Задача: написать для робота программу движения. Маршрут робота должен проходить по всем ячейкам (без пропусков), удовлетворяющим условию: X >= 0 и Y >= 0, при этом робот должен посетить каждую ячейку ровно один раз. Ограничения: 1) нельзя заводить никаких переменных (счетчиков, указателей... никаких); 2) Для ветвления программы можно использовать только лишь проверку условия: X==0||Y==0 и бесконечный безусловный цикл. Разумеется, текст программы должен быть конечным (более того, не очень длинным).

R>>Решение можно представить либо в виде псевдокода, либо графически, изобразив маршрут движения робота (как показывает практика, этого вполне достаточно).

MC>Придумал (пока графическое только — код поленился писать) решение, верное при следующих поправках к условию:
MC>1. Маршрут робота должен проходить по всем ячейкам (без пропусков), удовлетворяющим условию: X >= 0 и Y >= 0, однако робот может посещать и другие ячейки...
MC>2. Для ветвления программы можно использовать проверку условия: X==0||Y==0, безусловный цикл и оператор выхода из цикла
MC>Вот оно (сорри за качество — на телефон фоткал):
MC>
MC>Там кружком обведен начальный этап, его программируем вручную, ну а дальше — в цикле
MC>1. Вверх, лесенкой вправо вниз, влево
MC>2. Дважды вниз, лесенкой влево вниз
MC>3. Лесенкой влево вверх
MC>4. Дважды вверх, лесенкой вправо вверх
MC>Естественно, лесенки реализуются безусловными циклами, в которых есть if(X==0||Y==0) break;

Честно говоря, не ожидал увидеть ТАКОЕ. Но похоже, что решение
Моя оплошность: забыл указать, что робот не должен заходить в координаты X < 0, Y < 0, так что пища для размышлений есть

Здравствуйте, rg45, Вы писали:

R>Решение можно представить либо в виде псевдокода, либо графически, изобразив маршрут движения робота (как показывает практика, этого вполне достаточно).

Здравствуйте, deniok, Вы писали:

D>Здравствуйте, rg45, Вы писали:

R>>Решение можно представить либо в виде псевдокода, либо графически, изобразив маршрут движения робота (как показывает практика, этого вполне достаточно).

D>

Эврика!!!

Здравствуйте, rg45, Вы писали:

R>Завскребли на душе кошки, что я не очень точно сформулировал условие задачи. Поэтому, на всякий случай, хочу сделать парочку уточнений:

Правильно сделали, что заскребли...

R>Когда я писал условие задачи, мне эти моменты казались само собой разумеющимися, по скольку задача не привязывается ни к какому языку программирования (ну типа: никто не запрещает оператор опрератор do-while заменить на оператор do-until). Делаю дополнение на всякий случай (хотя сомневаюсь, что отсутствие этих дополнений было главным затруднением в решении задачи )

Сомневаешься? Именно оно и было! Попробуй придумать решение с одним безусловным бесконечным циклом (можешь не с одним), где ничего кроме команд и вопросов роботу типа "Ты не на границе?" делать нельзя.

P.S. бесконечный безусловный цикл в котором можно использовать break -- это НЕ бесконечный и НЕ безусловный цикл, ИМХО.

Здравствуйте, Nuzhny, Вы писали:

N>Робот не скачет как лошадь! Он двигается строго по указанным командам.

Не скачет. Я и не утверждал, что он скачет — читайте внимательнее. Но из за одного того факта, что он *может* скакнуть, все остальное решение утрачивает смысл.

N>Робот — это hardware, которому можно послать одну из комманд: шаг влево, шаг вправо, шаг вверх, шаг вниз.
N>Им управляет программа, в которой есть две переменные: x и у. Она может делать с ними всё, что угодно.

Не может. Может только добавлять +/-1 либо к x, либо к y за один шаг. Интерес не в том, чтобы обмануть условия задачи по формальным критериям, а в том, чтобы придумать алгоритм без обмана.

См. ниже по ветке правильное решение.

Здравствуйте, deniok, Вы писали:

D>http://files.rsdn.ru/52396/robot.PNG

Зач0000т!

Здравствуйте, deniok, Вы писали:

D>

должен проходить по всем ячейкам (без пропусков), удовлетворяющим условию: X >= 0 и Y >= 0,

вы побывали только в половине клеток

Здравствуйте, Sni4ok, Вы писали:


S>должен проходить по всем ячейкам (без пропусков), удовлетворяющим условию: X >= 0 и Y >= 0,

S>вы побывали только в половине клеток

Да не, в 96/+infty

Здравствуйте, deniok, Вы писали:

D>Да не, в 96/+infty

... вы правы

Здравствуйте, deniok, Вы писали:

D>Здравствуйте, rg45, Вы писали:

R>>Решение можно представить либо в виде псевдокода, либо графически, изобразив маршрут движения робота (как показывает практика, этого вполне достаточно).

D>

Хорошая задачка, только сформулирована немножко неточно была. Решение сложно запихнуть в один безусловный цикл. Тут можно сделать два бесконечных безусловных цикла, и прыгать из одного цикла в другой каким-нибудь goto по условию достижения границы.

Здравствуйте, vadimcher, Вы писали:

V>Хорошая задачка, только сформулирована немножко неточно была. Решение сложно запихнуть в один безусловный цикл. Тут можно сделать два бесконечных безусловных цикла, и прыгать из одного цикла в другой каким-нибудь goto по условию достижения границы.

Да, согласен, здесь, похоже, можно сформулировать красивое условие в терминах того, что умеет робот.

Здравствуйте, rg45, Вы писали:

R>Решение можно представить либо в виде псевдокода, либо графически, изобразив маршрут движения робота (как показывает практика, этого вполне достаточно).

Вот мой вариант решения(правда не выполняется условие X>0, Y>0):

поехали: {
 up, right, down, right, right,
 goto вжик_вверх_и_влево
}
 
вжик_вверх_и_влево: {
 
 loop {
   up, left,
   
   if ( (x==0)||(y==0) ) {
           
      down, left, up, up, right, up, // выруливаем
      goto вжик_вправо_и_вниз
   }
 }
   
}

вжик_вправо_и_вниз: {

 loop {
   rigth, down,
   
   if ( (x==0)||(y==0) ) {
   
      left, down, right, right, up, right, // выруливаем
      goto вжик_вверх_и_влево
   }
 }

}

R>Итак, есть плоская бесконечная регулярная сетка с прямоугольной ячейкой (или квадратной — не имеет значения). Каждая ячейка имеет пару координат — X и Y. По этой сетке ходит робот, управляемый заложенной в него программой. Система команд робота: "шагнуть по X", "шагнуть против X", "шагнуть по Y", "шагнуть против Y" — всего 4 направления движения. В начальный момент времени робот находится в ячейке с координатами X=0, Y=0. Задача: написать для робота программу движения. Маршрут робота должен проходить по всем ячейкам (без пропусков), удовлетворяющим условию: X >= 0 и Y >= 0, при этом робот должен посетить каждую ячейку ровно один раз. Ограничения: 1) нельзя заводить никаких переменных (счетчиков, указателей... никаких); 2) Для ветвления программы можно использовать только лишь проверку условия: X==0||Y==0 и бесконечный безусловный цикл. Разумеется, текст программы должен быть конечным (более того, не очень длинным).

R>Решение можно представить либо в виде псевдокода, либо графически, изобразив маршрут движения робота (как показывает практика, этого вполне достаточно).

Кривые Гильберта для n-мерного пространства?
http://en.wikipedia.org/wiki/Hilbert_curve

Здравствуйте, rg45, Вы писали:

R>Здравствуйте, Mr.Cat, Вы писали:

MC>>Здравствуйте, rg45, Вы писали:

MC>>Придумал (пока графическое только — код поленился писать) решение, верное при следующих поправках к условию:
MC>>1. Маршрут робота должен проходить по всем ячейкам (без пропусков), удовлетворяющим условию: X >= 0 и Y >= 0, однако робот может посещать и другие ячейки...
MC>>2. Для ветвления программы можно использовать проверку условия: X==0||Y==0, безусловный цикл и оператор выхода из цикла
MC>>Вот оно (сорри за качество — на телефон фоткал):
MC>>
MC>>Там кружком обведен начальный этап, его программируем вручную, ну а дальше — в цикле
MC>>1. Вверх, лесенкой вправо вниз, влево
MC>>2. Дважды вниз, лесенкой влево вниз
MC>>3. Лесенкой влево вверх
MC>>4. Дважды вверх, лесенкой вправо вверх
MC>>Естественно, лесенки реализуются безусловными циклами, в которых есть if(X==0||Y==0) break;

R>Честно говоря, не ожидал увидеть ТАКОЕ. Но похоже, что решение
R>Моя оплошность: забыл указать, что робот не должен заходить в координаты X < 0, Y < 0, так что пища для размышлений есть

Ага. А теперь догадайся, что при x==0 || y==0 не надо уходить из квадранта,
а надо делать шаг от начала координат, и решение (четкое, без циклов и переменных)
у тебя в кармане.