Ладьи Опции

[nastya_ab]

Помогите пожалуйста!

Ладьи.
Требуется найти такую расстановку 8 ладей на шахматной доске, при которой они не будут угрожать друг другу. Первые три фигуры расставляет пользователь.

[Lapp]

Введи два множества: для букв и для цифр. Затем выбирай расположение так, чтобы ни буква, ни цифра не была в соответствующем множестве (случайный перебор). Найденные позиции добавляй к множествам.
То есть примерно вот так (опускаю тут ручной ввод позиций первых трех ладей) :

  for i:=4 to 8 do begin
    repeat l:=Chr(Random(8)+65) until not (l in Letters);
    repeat n:=Random(8)+1 until not (n in Numbers);
    WriteLn(l,' ',n);
    Include(Letters,l);
    Include(Numbers,n);
  end;

[nasta_ab]

Введи два множества: для букв и для цифр. Затем выбирай расположение так, чтобы ни буква, ни цифра не была в соответствующем множестве (случайный перебор). Найденные позиции добавляй к множествам.
То есть примерно вот так (опускаю тут ручной ввод позиций первых трех ладей) :

  for i:=4 to 8 do begin
    repeat l:=Chr(Random(8)+65) until not (l in Letters);
    repeat n:=Random(8)+1 until not (n in Numbers);
    WriteLn(l,' ',n);
    Include(Letters,l);
    Include(Numbers,n);
  end;

Спасибо.

[klem4]

На сомом деле не лучший вариант, и по идее чисто теоретически возможен вариант когда решение никогда не будет найдено, считай фактически зацикливание, маловероятно конечно но всеже ...

Сообщение отредактировано: klem4 - 18.06.2007 10:36

[Michael_Rybak]

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

[Lapp]

А мне кажется, что klem4 прав. По сути, я ждал этого вопроса. Клем только забыл главный аргумент - масштабируемость. Ведь никто не сказал, что доска не может быть, скажем, 1000х1000 или еще больше.. И тогда эффективность алгоритма резко упадет..

Вот реализация алгоритма, который существенно повышает эффективность при сохранении случайности выбора:

const
  b=8;    {размер доски}
  m=3;    {начальное число ладей}

var
  l:char;
  n,k:byte;
  i:integer;
  Letters:set of char;
  Numbers:set of byte;

begin
  Letters:=[];
  Numbers:=[];
  for i:=1 to m do begin
    Write('Введите положение (буква и цифра через пробел) ладьи ',i,': ');
    ReadLn(l,n);
    Include(Letters,UpCase(l));
    Include(Numbers,n);
  end;
  WriteLn('Остальные ладьи можно расставить так:');
  for i:=m+1 to b do begin
    k:=Random(b-i+1)+1;
    l:='@';
    repeat
      Inc(l);
      while l in Letters do Inc(l);
      Dec(k)
    until k=0;
    Include(Letters,l);
    k:=Random(b-i+1)+1;
    n:=0;
    repeat
      Inc(n);
      while n in Numbers do Inc(n);
      Dec(k)
    until k=0;
    Include(Numbers,n);
    WriteLn(l,' ',n)
  end;
  ReadLn
end.

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

[Michael_Rybak]

Во-первых, 1000х1000 не получится из-за set.

А быстрее можно, используя специальную структуру данных, которая позволит находить нужную позицию за логарифмическое время. Т.е. будет n log n

Могу дать ссылку где почитать, если интересно

[Lapp]

Могу дать ссылку где почитать, если интересно

Фи, ссылка...
А мозги на что? ))

Да, с множествами я лопухнулся, понял наутро . 255 - и отвали..
Значит, надо иначе

[volvo]

255 - и отвали..

Или реализуй BigSet (почему я и пользуюсь всегда Include/Exclude вместо +/-) и работай хоть до 10000 ...

[Michael_Rybak]

Фи, ссылка...

Договорились - давайте придумывать

[Lapp]

Договорились - давайте придумывать

Я некоторое время чувствовал себя некомфортно, как бы с долгом . Сегодня нашел минутку подумать над этой задачей. Вот результат..
Я привожу код, который заполняет массив [1..n] неповторяющимися случайными числами от 1 до n. Код не использует множеств, так что размер массива ограничен выбранным типом переменных (в ТР - по сути, размером блока). Код должен работать, мне кажется, быстрее предыдущего моего варианта.
Принцип такой:
- заполняем массив (RestNum) номерами по порядку (это те номера, которые остались);
- в цикле выдергиваем из этого массива по одному элементу случайным образом и кладем в массив Num, заполняя его по порядку;
- образовавщуюся в RestNum от изымания элемента дыру заполняем, сдвигая хвост массива на один элемент влево, начиная с номера сразу за дырой;
- размер RestNum при этом как бы эффективно уменьшается на 1 (переменная m), что мы учитываем, уменьшая диапазон случайных чисел.
Вот сам код. Его можно оформить в виде процедуры при желании . Если нужно только выводить номера на печать или в файл, то массив Num по сути не нужен, можно вдвое сэкономить память.

const
  n=20;

type
  tRange=array[1..n]of integer;

var
  Num,RestNum:tRange;
  i,j,k,m:integer;

begin
  for i:=1 to n do RestNum[i]:=i;
  m:=n;
  for i:=1 to n do begin
    k:=Random(m)+1;
    Num[i]:=RestNum[k];
    if k<m then Move(RestNum[k+1],RestNum[k],(m-k)*SizeOf(Integer));
    Dec(m)
  end;
  for i:=1 to n do Write(Num[i]:3);
  ReadLn
end.

Сообщение отредактировано: Lapp - 23.06.2007 7:50

[Michael_Rybak]

Lapp, +1. А я знаете как решил ее относительно недавно? За n log n. Берем группу, идем по ней, и разбиваем на две случайным образом: каждый элемент с равной вероятностью оказывается в первой или второй. Потом рекурсивно перемешиваем подгруппы, и сливаем вместе

Кстати, std::random_shuffle в C++ работает именно так, как вы описали.

А что касается специальных структур данных, о которых я говорил - с их помощью можно работать с массивом, сохраняя порядок (не перемещая хвост в дырку).