Помощь - Поиск - Пользователи - Календарь
Полная версия: Ладьи
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
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
Цитата(Lapp @ 16.06.2007 12:19) *

Введи два множества: для букв и для цифр. Затем выбирай расположение так, чтобы ни буква, ни цифра не была в соответствующем множестве (случайный перебор). Найденные позиции добавляй к множествам.
То есть примерно вот так (опускаю тут ручной ввод позиций первых трех ладей) :
  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
На сомом деле не лучший вариант, и по идее чисто теоретически возможен вариант когда решение никогда не будет найдено, считай фактически зацикливание, маловероятно конечно но всеже ...
Michael_Rybak
А по-моему вариант хороший smile.gif Вероятность того, что оно зациклится хотя бы на пять секунд, я думаю, меньше вероятности того, что за эти пять секунд вырубится электричество в комп. классе во время проверки smile.gif А раз просят не какое-то определенное решение, то прикольно, чтоб выдавало рандомное.
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.

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

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

Могу дать ссылку где почитать, если интересно smile.gif
Lapp
Цитата(Michael_Rybak @ 20.06.2007 12:01) *

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

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

Да, с множествами я лопухнулся, понял наутро smile.gif. 255 - и отвали..
Значит, надо иначе
volvo
Цитата
255 - и отвали..
Или реализуй BigSet (почему я и пользуюсь всегда Include/Exclude вместо +/-) и работай хоть до 10000 ...
Michael_Rybak
Цитата
Фи, ссылка...


Договорились - давайте придумывать smile.gif
Lapp
Цитата(Michael_Rybak @ 20.06.2007 16:09) *

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

Я некоторое время чувствовал себя некомфортно, как бы с долгом smile.gif. Сегодня нашел минутку подумать над этой задачей. Вот результат.. smile.gif
Я привожу код, который заполняет массив [1..n] неповторяющимися случайными числами от 1 до n. Код не использует множеств, так что размер массива ограничен выбранным типом переменных (в ТР - по сути, размером блока). Код должен работать, мне кажется, быстрее предыдущего моего варианта.
Принцип такой:
- заполняем массив (RestNum) номерами по порядку (это те номера, которые остались);
- в цикле выдергиваем из этого массива по одному элементу случайным образом и кладем в массив Num, заполняя его по порядку;
- образовавщуюся в RestNum от изымания элемента дыру заполняем, сдвигая хвост массива на один элемент влево, начиная с номера сразу за дырой;
- размер RestNum при этом как бы эффективно уменьшается на 1 (переменная m), что мы учитываем, уменьшая диапазон случайных чисел.
Вот сам код. Его можно оформить в виде процедуры при желании smile.gif. Если нужно только выводить номера на печать или в файл, то массив 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.
Michael_Rybak
Lapp, +1. А я знаете как решил ее относительно недавно? За n log n. Берем группу, идем по ней, и разбиваем на две случайным образом: каждый элемент с равной вероятностью оказывается в первой или второй. Потом рекурсивно перемешиваем подгруппы, и сливаем вместе smile.gif

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

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