VPF::Задача про ферзей - Форум программистов

trav1s

Дата 25.11.2005, 23:49 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 25.11.2005

Репутация: нет
Всего: нет

Нужно раставить 8 ферзей на шахматной доске так чтобы они не "били" друг друга.
Только рекурсивным методом. Абсолютно не догоняю как .. :стена
Заранее спасибо
smile

mvdr

Дата 25.11.2005, 23:59 (ссылка)

(нет голосов)

Загрузка ...

физик

Профиль
Группа: Участник
Сообщений: 1349
Регистрация: 31.12.2004
Где: Волгоград, Россия

Репутация: 7
Всего: 42

1001 и одна ночь smile

такая задача тут была. Поищи.
И потом : что имено не понятно: как написать или сама математика задачи (как расставить?

--------------------

Появляюсь редко, но часто метко

Изображать идиота сложнее, чем изображать умного: полезнее и не каждому дано

S.A.P.

Дата 26.11.2005, 03:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2664
Регистрация: 11.6.2004

Репутация: 1
Всего: 71

На чем реализовать? или просто алгоритм нужен?

trav1s

Дата 26.11.2005, 10:00 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 25.11.2005

Репутация: нет
Всего: нет

Как расставить я знаю...
А алгоритм сделать не могу. По ходу с 2 рекурсиями.
Написать надо на паскале.

eskaflone

Дата 26.11.2005, 12:30 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 75
Регистрация: 5.11.2005

Репутация: 2
Всего: 3

Код


var up:array[2..16]of boolean;
    down:array[-7..7]of boolean;
    vert:array[1..8]of boolean;
    ihor:array[1..8]of integer;
    n:integer;

function d_hod(i,j:integer):boolean;  //проверка на допустимость хода в позицию (i,j)
begin
   d_hod:=vert[j] and up[i+j] and down[i-j];
end;

procedure hod(i,j:integer);  //сделать ход
begin
   ihor[i]:=j;
   vert[j]:=false;
   up[i+j]:=false;
   down[i-j]:=false;
end;

procedure o_hod(i,j:integer);  //отменить ход
begin
   vert[j]:=true;
   up[i+j]:=true;
   down[i-j]:=true;
end;

Нахождение одного варианта расстановки :

Код


procedure find_one(i:integer;var q:boolean);
var j:integer;
begin
   j:=0;
   repeat
      inc(j);
      q:=false;
      if d_hod(i,j) then
         begin
            hod(i,j);
            if i<n then begin
                           find_one(i+1,q);
                           if not q then o_hod(i,j);
                        end else q:=true;
         end;
   until q or (j=n);
end;

Нахождение всех рещений :

Код


procedure print;
var i:integer;
begin
   write('  ',s,'   ');for i:=1 to n do write(ihor[i],' ');writeln;
end;

procedure find_all(i:integer);
var j:integer;
begin
   if i<=n then
   begin
      for j:=1 to n do
         if d_hod(i,j) then begin
                               hod(i,j);
                               find_all(i+1);
                               o_hod(i,j);
                            end;
   end else
      begin
         inc(s);
         print;
      end;
end;

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »