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

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

Здравствуйте, rg45.

Как вариант — робот ходит по диагонали от оси x до y.

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

T>Здравствуйте, rg45.

T>Как вариант — робот ходит по диагонали от оси x до y.

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

Движение "уголком" (на С++):

#include <iostream>
#include <stdlib.h>
#include <conio.h>
using namespace std;
////////////////////////////////////////////////////////////////////////////
void curr_robot_coords(int x, int y)
{
    cout<<" ("<<x<<", "<<y<<")"<<endl;
    _getch();
}
////////////////////////////////////////////////////////////////////////////
int main()
{
    int x(0), y(0);
    curr_robot_coords(x, y);

    for (;;)
    {
        //Шаг вправо
        cout<<"\nstep right"<<endl;
        ++x;
        curr_robot_coords(x, y);
        
        //Движение вверх
        cout<<"\nupward motion"<<endl;
        for (;;)
        {
            ++y;
            --x;
            curr_robot_coords(x + y, y);
            
            if (x == 0 || y == 0)
                break;
        }

        //Движение влево
        cout<<"\nleft motion"<<endl;
        x = y;
        for (;;)
        {
            --x;
            curr_robot_coords(x, y);
            
            if (x == 0 || y == 0)
                break;
        }

        //Шаг вверх
        cout<<"\nstep up"<<endl;
        ++y;
        curr_robot_coords(x, y);

        //Движение вправо
        cout<<"\nright motion"<<endl;
        for (;;)
        {
            ++x;
            --y;
            curr_robot_coords(x, y + x);
            
            if (x == 0 || y == 0)
                break;
        }

        //Движение вниз
        cout<<"\ndownward motion"<<endl;
        y = x;
        for (;;)
        {
            --y;
            curr_robot_coords(x, y);
            
            if (x == 0 || y == 0)
                break;
        }
    }

    system("pause");
    return 0;
}
////////////////////////////////////////////////////////////////////////////

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

N>Движение "уголком" (на С++):

N> curr_robot_coords(x + y, y);

Почему координата вдруг x+y?

N> if (x == 0 || y == 0)
N> break;

А вот это как раз и есть УСЛОВНЫЙ ЦИКЛ, который Вы замаскировали под break.

N> x = y;

Прыжок?

N> if (x == 0 || y == 0)
N> break;

Опять.

N> if (x == 0 || y == 0)
N> break;

И опять...

N> y = x;

Прыжок.

N> if (x == 0 || y == 0)
N> break;

И опять.

В условии был один бесконечный безусловный цикл (их не может быть два, т.к. из таких циклов не выходят).

Здравствуйте, 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 шага вправо, один вниз, может быть где-то в этом собака и зарыта. Вообще, похоже на какой-то детский трюк типа как нарисовать окружность и поставить точку в центре не отрывая карандаша от бумаги.

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

V>В условии был один бесконечный безусловный цикл (их не может быть два, т.к. из таких циклов не выходят).

Хе-хе. Рекурсия поможет нам удовлетворить формальностям

#include <iostream>
#include <conio.h>
using namespace std;
////////////////////////////////////////////////////////////////////////////
void curr_robot_coords(int x, int y)
{
    cout<<" ("<<x<<", "<<y<<")"<<endl;
    _getch();
}
////////////////////////////////////////////////////////////////////////////
void upward_motion(int &x, int &y)
{
    ++y;
    --x;
    curr_robot_coords(x + y, y);

    if (x == 0 || y == 0)
        return;
    else
        upward_motion(x, y);
}
////////////////////////////////////////////////////////////////////////////
void left_motion(int &x, int &y)
{
    --x;
    curr_robot_coords(x, y);

    if (x == 0 || y == 0)
        return;
    else
        left_motion(x, y);
}
////////////////////////////////////////////////////////////////////////////
void right_motion(int &x, int &y)
{
    ++x;
    --y;
    curr_robot_coords(x, y + x);

    if (x == 0 || y == 0)
        return;
    else
        right_motion(x, y);
}
////////////////////////////////////////////////////////////////////////////
void downward_motion(int &x, int &y)
{
    --y;
    curr_robot_coords(x, y);

    if (x == 0 || y == 0)
        return;
    else
        downward_motion(x, y);
}
////////////////////////////////////////////////////////////////////////////
int main()
{
    int x(0), y(0);
    curr_robot_coords(x, y);

    for (;;)
    {
        //Шаг вправо
        cout<<"\nstep right"<<endl;
        ++x;
        curr_robot_coords(x, y);

        //Движение вверх
        cout<<"\nupward motion"<<endl;
        upward_motion(x, y);

        //Движение влево
        cout<<"\nleft motion"<<endl;
        x = y;
        left_motion(x, y);

        //Шаг вверх
        cout<<"\nstep up"<<endl;
        ++y;
        curr_robot_coords(x, y);

        //Движение вправо
        cout<<"\nright motion"<<endl;
        right_motion(x, y);

        //Движение вниз
        cout<<"\ndownward motion"<<endl;
        y = x;
        downward_motion(x, y);
    }

    return 0;
}
////////////////////////////////////////////////////////////////////////////

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

V>>Почему координата вдруг x+y?

N>Потому что нельзя нигде хранить индексы, состояния и т.п. (x+y) — это новая координата, подаваемая роботу. Что не так?

Как-то это нечестно. Если роботу можно передавать координаты, то он может скакать как лошадь шахматная, и вообще как угодно. Роботу можно передать только направление одного шага в виде константы. Точнее сказать, программа — это сам робот и есть.

И вообще, x+y — это и есть использование переменной в неявном виде.

Здравствуйте, 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>Какой-такой прыжок? Где? Запусти программу и посмотри на выдаваемые координаты. Нет никаких прыжков.

Ну опять же, Вы используете переменные в своих целях.

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

N>Хе-хе. Рекурсия поможет нам удовлетворить формальностям

Робот — это вот что такое:

int x=0;
int y=0;
void step(int dir)
{
   switch(dir)
   {
      case 0: --x; break;
      case 1: --y; break;
      case 2: ++x; break;
      case 3: ++y; break;
   }
}

Больше ничего нельзя — x,y в управляющей программе можно только читать.

Здравствуйте, 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.

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

N>Порядок обхода
И как тут без переменных узнать, что пора поворачивать налево?

Здравствуйте, 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 шага вправо, один вниз, может быть где-то в этом собака и зарыта. Вообще, похоже на какой-то детский трюк типа как нарисовать окружность и поставить точку в центре не отрывая карандаша от бумаги.

Как говорят разведчики, мыслите в правильном направлениии. Успехов!

Здравствуйте, 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). Делаю дополнение на всякий случай (хотя сомневаюсь, что отсутствие этих дополнений было главным затруднением в решении задачи )

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

N>Движение "уголком" (на С++):

N>

N>#include <iostream>
N>#include <stdlib.h>
N>#include <conio.h>
N>using namespace std;
N>////////////////////////////////////////////////////////////////////////////
N>void curr_robot_coords(int x, int y)
N>{
N>    cout<<" ("<<x<<", "<<y<<")"<<endl;
N>    _getch();
N>}
N>////////////////////////////////////////////////////////////////////////////
N>int main()
N>{
N>    int x(0), y(0);
N> //snipped
N>

Уже не катит, из-за выделенного. В условии сказано ясно: нельзя заводить никаких переменных.

Здравствуйте, 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 не надо уходить из квадранта,
а надо делать шаг от начала координат, и решение (четкое, без циклов и переменных)
у тебя в кармане.