Должен сразу сказать, дабы избежать обвинений в плагиате, задачу придумал не я, но она мне очень нравиится. Делюсь.
Итак, есть плоская бесконечная регулярная сетка с прямоугольной ячейкой (или квадратной — не имеет значения). Каждая ячейка имеет пару координат — X и Y. По этой сетке ходит робот, управляемый заложенной в него программой. Система команд робота: "шагнуть по X", "шагнуть против X", "шагнуть по Y", "шагнуть против Y" — всего 4 направления движения. В начальный момент времени робот находится в ячейке с координатами X=0, Y=0. Задача: написать для робота программу движения. Маршрут робота должен проходить по всем ячейкам (без пропусков), удовлетворяющим условию: X >= 0 и Y >= 0, при этом робот должен посетить каждую ячейку ровно один раз. Ограничения: 1) нельзя заводить никаких переменных (счетчиков, указателей... никаких); 2) Для ветвления программы можно использовать только лишь проверку условия: X==0||Y==0 и бесконечный безусловный цикл. Разумеется, текст программы должен быть конечным (более того, не очень длинным).
Решение можно представить либо в виде псевдокода, либо графически, изобразив маршрут движения робота (как показывает практика, этого вполне достаточно).
... << RSDN@Home 1.2.0 alpha rev. 787>>
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, vadimcher, Вы писали:
V>Почему координата вдруг x+y?
Потому что нельзя нигде хранить индексы, состояния и т.п. (x+y) — это новая координата, подаваемая роботу. Что не так?
N>> if (x == 0 || y == 0) N>> break;
V>А вот это как раз и есть УСЛОВНЫЙ ЦИКЛ, который Вы замаскировали под break.
Тут согласен. Но тогда есть дополнительный вопрос по условию. Можно использовать только ОДИН цикл и только ОДНУ проверку?
ИМХО, нет, т.к. в условии есть приписка "текст программы должен быть ... не очень длинным". Значит структур может быть больше.
Впрочем, этот вопрос к автору.
N>> x = y; V>Прыжок?
Какой-такой прыжок? Где? Запусти программу и посмотри на выдаваемые координаты. Нет никаких прыжков.
V>В условии был один бесконечный безусловный цикл (их не может быть два, т.к. из таких циклов не выходят).
В решении есть один безусловный цикл — самый верхний. Из него и не выходят — ведь ячеек бесконечное множество
Здравствуйте, rg45, Вы писали:
T>>Как вариант — робот ходит по диагонали от оси x до y.
R>Возьми листок в клетку и нарисуй, ты увидишь, что таким образом некоторые клетки на осях оказываются непосещенными.
Если можно проверять ветвление только на (x==0||y==0), то отсюда следует, что движение должно выполняться по диагонали и никак иначе — если X увеличивается, то Y должно уменьшаться и наоборот. В противном случае робот неизбежно устремляется в бесконечность. Не обязательно по линии в 135 градусов — возможно что-то типа 2 шага вправо, один вниз, может быть где-то в этом собака и зарыта. Вообще, похоже на какой-то детский трюк типа как нарисовать окружность и поставить точку в центре не отрывая карандаша от бумаги.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, Nuzhny, Вы писали:
V>>Почему координата вдруг x+y?
N>Потому что нельзя нигде хранить индексы, состояния и т.п. (x+y) — это новая координата, подаваемая роботу. Что не так?
Как-то это нечестно. Если роботу можно передавать координаты, то он может скакать как лошадь шахматная, и вообще как угодно. Роботу можно передать только направление одного шага в виде константы. Точнее сказать, программа — это сам робот и есть.
И вообще, x+y — это и есть использование переменной в неявном виде.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, Nuzhny, Вы писали:
N>Здравствуйте, vadimcher, Вы писали:
V>>Почему координата вдруг x+y?
N>Потому что нельзя нигде хранить индексы, состояния и т.п. (x+y) — это новая координата, подаваемая роботу. Что не так?
Я так понимаю, что у робота состояние внутренне, а Вы только используете команды "вверх", "вправо" и т.п., а также можете "спросить" его, не достиг ли он границы. Но не передавать ему координаты, которые Вы храните.
N>>> if (x == 0 || y == 0) N>>> break;
V>>А вот это как раз и есть УСЛОВНЫЙ ЦИКЛ, который Вы замаскировали под break.
N>Тут согласен. Но тогда есть дополнительный вопрос по условию. Можно использовать только ОДИН цикл и только ОДНУ проверку?
На счет проверок ничего такого не сказано. Ну а цикл, видимо, один, т.к. он использован в условии в единственном числе, к тому же он безусловный и бесконечный!
N>>> x = y; V>>Прыжок?
N>Какой-такой прыжок? Где? Запусти программу и посмотри на выдаваемые координаты. Нет никаких прыжков.
Ну опять же, Вы используете переменные в своих целях.
Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, Nuzhny, Вы писали:
N>>Хе-хе. Рекурсия поможет нам удовлетворить формальностям
MS>Робот — это вот что такое: MS>
MS>int x=0;
MS>int y=0;
MS>void step(int dir)
MS>{
MS> switch(dir)
MS> {
MS> case 0: --x; break;
MS> case 1: --y; break;
MS> case 2: ++x; break;
MS> case 3: ++y; break;
MS> }
MS>}
MS>
MS>Больше ничего нельзя — x,y в управляющей программе можно только читать.
Да, я также думаю. Только еще можно спросить его, не достиг ли он границы.
Здравствуйте, Nuzhny, Вы писали:
N>Здравствуйте, vadimcher, Вы писали:
V>>В условии был один бесконечный безусловный цикл (их не может быть два, т.к. из таких циклов не выходят).
N>Хе-хе. Рекурсия поможет нам удовлетворить формальностям
N>void upward_motion(int &x, int &y) N>{ N> ++y; N> --x; N> curr_robot_coords(x + y, y);
N> if (x == 0 || y == 0) N> return; N> else N> upward_motion(x, y); N>}
Блин, ну сплошной cheating... У Вас координата (x+y,y) и Вы сравниваете не равно ли x==0? Т.е. попросту, не достиг ли я диагонали. Хотя в условии явно сказано, что координаты равны (x,y) и их только можно проверять на 0.
Здравствуйте, McSeem2, Вы писали:
MS>Как-то это нечестно. Если роботу можно передавать координаты, то он может скакать как лошадь шахматная, и вообще как угодно. Роботу можно передать только направление одного шага в виде константы. Точнее сказать, программа — это сам робот и есть.
MS>И вообще, x+y — это и есть использование переменной в неявном виде.
Робот не скачет как лошадь! Он двигается строго по указанным командам.
Робот — это hardware, которому можно послать одну из комманд: шаг влево, шаг вправо, шаг вверх, шаг вниз.
Им управляет программа, в которой есть две переменные: x и у. Она может делать с ними всё, что угодно.
Все эти (x+y) — это просто вывод для удобства проверки правильности движения робота. Если так хочется, то вот то же самое, но без координат — одни команды:
#include <iostream>
#include <conio.h>
using namespace std;
////////////////////////////////////////////////////////////////////////////enum commands { left_, right_, up_, down_ };
void send_command(commands cmd)
{
switch (cmd)
{
case left_:
cout<<"left"<<endl;
break;
case right_:
cout<<"right"<<endl;
break;
case up_:
cout<<"up"<<endl;
break;
case down_:
cout<<"down"<<endl;
break;
}
_getch();
}
////////////////////////////////////////////////////////////////////////////void upward_motion(int &x, int &y)
{
++y;
--x;
send_command(up_);
if (x == 0 || y == 0)
return;
else
upward_motion(x, y);
}
////////////////////////////////////////////////////////////////////////////void left_motion(int &x, int &y)
{
--x;
send_command(left_);
if (x == 0 || y == 0)
return;
else
left_motion(x, y);
}
////////////////////////////////////////////////////////////////////////////void right_motion(int &x, int &y)
{
++x;
--y;
send_command(right_);
if (x == 0 || y == 0)
return;
else
right_motion(x, y);
}
////////////////////////////////////////////////////////////////////////////void downward_motion(int &x, int &y)
{
--y;
send_command(down_);
if (x == 0 || y == 0)
return;
else
downward_motion(x, y);
}
////////////////////////////////////////////////////////////////////////////int main()
{
int x(0), y(0);
for (;;)
{
++x;
send_command(right_);
upward_motion(x, y);
x = y;
left_motion(x, y);
++y;
send_command(up_);
right_motion(x, y);
y = x;
downward_motion(x, y);
}
return 0;
}
////////////////////////////////////////////////////////////////////////////
Здравствуйте, VEAPUK, Вы писали:
VEA>Здравствуйте, Nuzhny, Вы писали:
N>>Порядок обхода VEA>И как тут без переменных узнать, что пора поворачивать налево?
Переменные есть — х и у. На их использование ограничений, вроде, не налагается.
При таком обходе необходимо также запоминать состояние робота: т.е. куда он движется. Это делается с помощью рекурсивных функций.
Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, rg45, Вы писали:
T>>>Как вариант — робот ходит по диагонали от оси x до y.
R>>Возьми листок в клетку и нарисуй, ты увидишь, что таким образом некоторые клетки на осях оказываются непосещенными.
MS>Если можно проверять ветвление только на (x==0||y==0), то отсюда следует, что движение должно выполняться по диагонали и никак иначе — если X увеличивается, то Y должно уменьшаться и наоборот. В противном случае робот неизбежно устремляется в бесконечность. Не обязательно по линии в 135 градусов — возможно что-то типа 2 шага вправо, один вниз, может быть где-то в этом собака и зарыта. Вообще, похоже на какой-то детский трюк типа как нарисовать окружность и поставить точку в центре не отрывая карандаша от бумаги.
Как говорят разведчики, мыслите в правильном направлениии. Успехов!
... << RSDN@Home 1.2.0 alpha rev. 787>>
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, 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, то также доступно и условие !(X==0||Y==0). Эти условия можно использовать как в операторах if, так и в циклах.
2. В качеастве безусловного ветвления программы можно использовать: безусловные циклы, безусловные переходы (goto), операторы continue и break.
Когда я писал условие задачи, мне эти моменты казались само собой разумеющимися, по скольку задача не привязывается ни к какому языку программирования (ну типа: никто не запрещает оператор опрератор do-while заменить на оператор do-until). Делаю дополнение на всякий случай (хотя сомневаюсь, что отсутствие этих дополнений было главным затруднением в решении задачи )
... << RSDN@Home 1.2.0 alpha rev. 787>>
--
Не можешь достичь желаемого — пожелай достигнутого.