Меня зовут — Анатолий Ларин

Роботы умеют rand()?

В использовании технологий программист не ограничен. Можно использовать хоть ядерный синтез, хоть теорию струн )

В качестве решения, приветствуется код на Python, хотя язык не существенен. Можно и просто формулами решить задачу )

Если да, то программа выглядит так:

if(!len)
len = 1

dir = rand(left, right)
move(dir)
len++

Эм… какая-то триальная версия ))) а как роботы поймут, что встретились?

Даже так:

if(!len)
len = 1

dir = rand(left, right)
move(dir, len)
len++

Они столкнутся :)

Кстати, как code, так и pre тут гробят форматирование :(

И где описан факт их столкновения? И главное, почему ты уверен, что при таком алгоритме они обязательно столкнуться?
Я думаю, такой алгоритм будет работать не во всех случаях )

Sam Dark: Кстати, как code, так и pre тут гробят форматирование :(

Нет, просто вначале надо вставить тег pre, а в него вложить code.

example = True
if example:
    print 'Cool!'

if(!len)
  len = 1

dir = rand(left, right)
for(i=0;i<len;i++){
  move(dir)
  if(check(left) || check(right))
    success;
}
len=len*100

Так как апмплитуда у нас увеличивается, а честный рандом выдаёт примерно одинаковое количество нулей и единиц, роботы встретятся:

1. Варианты вроде left-left и right-right можно выкинуть сразу т.к. они в принципе ни на что не влияют.
2. Предыдущие движение несущественны на фоне следующего.

Короче, сначала публикую своё решение, а затем объясняю его прелести с частичным разбором :)

Будем считать, что на каждом шаге цикла роботу задается целое число шагов L, если оно положительно, то робот движется вправо, а если отрицательное, то влево.
Язык Pascal; random(2) означает целое число: либо 0, либо 1.

Будем считать, что n – это n-ый шаг цикла программы.

Итак:

if n=1 then
L:=2*(random(2)-0,5)
else
L:=2*(random(2)-0,5) * 3^(n-2)*2;

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

L:=2*(random(2)-0,5) * 3^(n-2)*2;

Теперь, как это всё работает. На каждом шаге роботу задаётся случайное направление, определяемое формулой 2*(random(2)-0,5). Эта формула принимает случайное значение: либо 1, либо -1. Проверить не сложно, т.к. у random(2) всего два значения на выходе.

Идём дальше. Формула 3^(n-2)*2 начиная со второго шага задает такое расстояние, которое равно сумме всех(!) расстояний при всех предшествующих n. При n равном 1 у нас из условия подставляется другая формула, где расстояние равно 1. На самом деле, как я уже писал, можно обойтись и без условия, тогда расстояние на первом шаге будет равно 2/3, что нам тоже подходит, т.к. формула 3^(n-2)*2 будет заведомо больше (на 1/3), чем сумма всех пройденных расстояний.
Я приведу пример последовательности, которая получается по формуле
Шаг Значение
1 2/3 (или 1 при формуле с условием)
2 2 = (1)*2
3 6 = (2+1)*2
4 18 = (6+2+1)*2
5 54 = (18+6+2+1)*2
6 162 = (54+18+6+2+1)*2
Дальше закономерность понятна. При необходимости доказывается это всё методом индукции.

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

Я могу гарантировать, что при некотором шаге m, который высчитывается по формуле log3(X/2)+2, где X – начальное расстояние между роботами, причем не имеет значения, сколь угодно большим оно может быть… так вот, при шаге m вероятность столкновения роботов равна 25%. Т.е. после шага m достаточно еще 4 шагов (ну как бы:) ), чтобы роботы встретились наверняка. А вероятность зависит от благоприятного выбора обоих роботов, т.е. равна 1/2 * 1/2 = 1/4.

Станислав
Хорошее решение.

Кроме варианта с рендомным движением, ничего в голову не приходит.

Что-то мало новых вкусняшек на сайте стало, все времени нет?

donflash, какого рода “вкусняшки” Вас интересуют?
А в целом, да, времени очень мало, большую часть времени занимает основная работа и московские пробки :(

Решение без рандома на С++:

class Line;
class Bot;

line = Line();
bot1 = Bot(line.randomPosition());
bot2 = Bot(line.randomPosition());

int step_size=1;
int b1vector = 1;
int b2vector = -1;
for(int i = 1; bot1.meetOtherBot() || bot2.meetOtherBot(); i++) {
   bot1.move(b1);
   bot2.move(b2);
   if(i>step_size) {
      i = 1;
      step_size *=2;
      b1vector *=-1;
      b2vector *=-1;
   }
}

Прошу прощения, сделал несколько ошибок
Вот исправленный вариант:

class Line;
class Bot;

line = Line();
bot1 = Bot(line.randomPosition());
bot2 = Bot(line.randomPosition());

int step_size=1;
int b1vector = 1;
int b2vector = -1;
for(int i = 1; bot1.meetOtherBot(); i++) {
    bot1.move(b1vector);
    bot2.move(b2vector);
    if(i>step_size) {
        i = 1;
        step_size *=2;
        b1vector *=-1;
        b2vector *=-1;
    }
}

Sagifire, спасибо!

Да, хорошее решение с увеличением амплитуды. Похожее решение описывал Станислав.

UPD: я ошибся, решение не верное, см. ниже.

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

Хм… а я не досмотрел ) Точно! Решение не верно. Т.к. программа должна быть загружена в каждого робота.

Дмитрий, спасибо за внимательность! Вы спасли роботов )

Немного недочитал условия задачи, наверное повлияла усталость.

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

Можно делать и без рандома… с использованием периодических функций и увеличением амплитуды

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

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