VPF::Задача о 8 шахматных слонах - Форум программистов

Dioniz

Дата 15.2.2005, 18:29 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

У меня проблема с такой задачей:
Расставить 8 слонов на шахматной доске(8x8) так,чтоб каждое поле было под боем.
Как реализовать это на паскале?Кажется.нужно использовать рекурсию.
Помогите,please!!!

Guest

Дата 10.11.2005, 19:47 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

А как это реализовать на ПАСКАЛЕ или СИ??

Pakshin A. S.

Дата 10.11.2005, 22:18 (ссылка)

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

Загрузка ...

Эксперт

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

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

Модератор: не относящиеся к сути темы посты были удалены моератором.

darkart

Дата 10.11.2005, 23:21 (ссылка)

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

Загрузка ...

Опытный

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

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

Примерно так...

Код


program Chess;
const
  n=8;{размерность поля}
type
  TChessBoard=array[1..n,1..n] of boolean;{описание доски}
  TElephants=array[1..n] of 1..n;{описание положения слона}
var
  Elephant:TElephants;
  CB:TChessBoard;
  bol:boolean;{есть ли результат}
function Test(var Elephant:TElephants;var ChessBoard:TChessBoard):boolean;
{функция проверяет все ли поля биты}
var
  i,x,y:integer;
  bolResult:boolean;
begin
  for x:=1 to n do
    for y:=1 to n do
      ChessBoard[x,y]:=False;{инициализация}
  for i:=1 to n do{заполнение полей битых i-ым слоном}
  begin
    x:=i;
    y:=Elephant[i];
    while (x>0) and (y>0) do
    begin
      ChessBoard[x,y]:=True;
      dec(x);
      dec(y);
    end;
    x:=i;
    y:=Elephant[i];
    while(x<=n) and (y>0) do
    begin
      ChessBoard[x,y]:=True;
      inc(x);
      dec(y);
    end;
    x:=i;
    y:=Elephant[i];
    while(x>0) and (y<=n) do
    begin
      ChessBoard[x,y]:=True;
      dec(x);
      inc(y);
    end;
    x:=i;
    y:=Elephant[i];
    while(x<=n) and (y<=n) do
    begin
      ChessBoard[x,y]:=True;
      inc(x);
      inc(y);
    end;
  end;
  bolResult:=true;
  for x:=1 to n do
    for y:=1 to n do
      bolResult:=bolResult and ChessBoard[x,y];
  Test:=bolResult;
end;
function Next(var Elephant:TElephants):boolean;
{функция вычисляет следующее положение слонов}
var
  i:integer;
  bol:boolean;
begin
  bol:=true;
  for i:=1 to n do
    bol:=bol and (Elephant[i]=n);
  if bol then
    Next:=False
  else
  begin
    i:=1;
    while (Elephant[i]=n) and (i<=n) do
    begin
      Elephant[i]:=1;
      inc(i);
    end;
    inc(Elephant[i]);
    Next:=True;
  end;
end;
procedure InitElephants(var Elephant:TElephants);
{начальное положение слонов}
var
  i:integer;
begin
  for i:=1 to n do
    Elephant[i]:=1;
end;
procedure PrintResults(var Elephant:TElephants);
{вывод результата}
var
  i:integer;
begin
  writeln('Result:');
  for i:=1 to n-1 do
    write('(',i,',',Elephant[i],'),');
  writeln('(',n,',',Elephant[n],')');
end;
begin
  writeln('ChessBoard');
  InitElephants(Elephant);
  repeat
    bol:=Test(Elephant,CB);
  until bol or (not Next(Elephant));
  if bol then Printresults(Elephant);{печать первого варианта}
  readln;
end.

Это сообщение отредактировал(а) darkart - 10.11.2005, 23:24

Nestea

Дата 11.11.2005, 19:02 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Что-то она выводит толко название доски на экран - ChessBoard.. Пробовала пошагово прогонять, она в нек-е циклы вроде как не заходит..please, если можно доработать?

darkart

Дата 11.11.2005, 22:32 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

Что-то она выводит толко название доски на экран - ChessBoard.

Надо подождать...
У меня выводит:
ChessBoard
Result:
(1,2),(2,4),(3,6),(4,3),(5,3),(6,6),(7,4),(8,2)
_

Guest

Дата 12.11.2005, 09:41 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

darkart Спасибки большие! smile

А еще не подскажешь аналогичную задачку : как подсчитать кол-во слонов, чтобы под боем находилось все поле?

darkart

Дата 12.11.2005, 16:56 (ссылка)

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

Загрузка ...

Опытный

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

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

Вообще вот, но количество слонов для доски (nxn) будет n штук:

Код


program chess;
const
  n=4;{Размерность доски}
type
  TChessBoard=array[1..n,1..n] of boolean;{описание доски}
  TElephant=record{описание положения слона}
    x,y:integer;
  end;
  TElephants=array[1..n] of TElephant;{описание положения слонов}
  TStrIndexes=array[1..n] of integer;{строки доски которые используются}
var
  Elephant:TElephants;
  CB:TChessBoard;
  bol:boolean;{есть ли результат}
  k:integer;{количество слонов}
  strIndex:TStrIndexes;
function mink(n:integer):integer;
{вычисление минимально разумного количества слонов}
{т. к. один слон не может побить более 2*n-1 клеток поля}
begin
  mink:=trunc((n*n)/(2*n-1))+1;
end;
procedure InitStrIndexes(var strIndex:TStrIndexes;k:integer);
{инициализация номеров используемых строк}
var
  i:integer;
begin
  for i:=1 to k do
    strIndex[i]:=i;
end;
procedure InitElephants(var Elephant:TElephants;var strIndex:TStrIndexes;k:integer);
{инициализация положения слонов}
var
  i:integer;
begin
  for i:=1 to k do
  begin
    Elephant[i].x:=strIndex[i];
    Elephant[i].y:=1;
  end;
end;
function Test(var Elephant:TElephants;var ChessBoard:TChessBoard;k:integer):boolean;
{функция проверяет все ли поля биты}
var
  i,x,y:integer;
  bolResult:boolean;
begin
  for x:=1 to n do
    for y:=1 to n do
      ChessBoard[x,y]:=False;{инициализация}
  for i:=1 to k do{заполнение полей битых i-ым слоном}
  begin
    x:=Elephant[i].x;
    y:=Elephant[i].y;
    while (x>0) and (y>0) do
    begin
      ChessBoard[x,y]:=True;
      dec(x);
      dec(y);
    end;
    x:=Elephant[i].x;
    y:=Elephant[i].y;
    while(x<=n) and (y>0) do
    begin
      ChessBoard[x,y]:=True;
      inc(x);
      dec(y);
    end;
    x:=Elephant[i].x;
    y:=Elephant[i].y;
    while(x>0) and (y<=n) do
    begin
      ChessBoard[x,y]:=True;
      dec(x);
      inc(y);
    end;
    x:=Elephant[i].x;
    y:=Elephant[i].y;
    while(x<=n) and (y<=n) do
    begin
      ChessBoard[x,y]:=True;
      inc(x);
      inc(y);
    end;
  end;
  bolResult:=true;
  for x:=1 to n do
    for y:=1 to n do
      bolResult:=bolResult and ChessBoard[x,y];
  Test:=bolResult;
end;
procedure PrintResults(var Elephant:TElephants;k:integer);
{печать результата}
var
  i:integer;
begin
  writeln('Result:');
  for i:=1 to k-1 do
    write('(',Elephant[i].x,',',Elephant[i].y,'),');
  writeln('(',Elephant[k].x,',',Elephant[k].y,')');
end;
function NextStrIndex(var strIndex:TStrIndexes;k:integer):boolean;
{вычисление следующих номеров строк}
var
  i:integer;
  bol:boolean;
begin
  bol:=True;
  for i:=1 to k do
    bol:=bol and (strIndex[i]=n);
  if bol then NextStrIndex:=False
  else
  begin
    i:=1;
    while (strIndex[i]=n) and (i<k) do
    begin
      strIndex[i]:=1;
      inc(i);
    end;
    inc(strIndex[i]);
    NextStrIndex:=True;
  end;
end;
function Next(var Elephant:TElephants;var strIndex:TStrIndexes;k:integer):boolean;
{функция вычисляет следующее положение слонов}
var
  i:integer;
  bol:boolean;
begin
  bol:=true;
  for i:=1 to k do
    bol:=bol and (Elephant[i].x=n-k+i) and (Elephant[i].y=n);
  if bol then Next:=False
  else
  begin
    bol:=True;
    for i:=1 to k do
      bol:=bol and (Elephant[i].y=n);
    if bol then
    begin
      if NextStrIndex(strIndex,k) then InitElephants(Elephant,strIndex,k);
    end
    else
    begin
      i:=1;
      while (Elephant[i].y=n) and (i<k) do
      begin
        Elephant[i].y:=1;
        inc(i);
      end;
      inc(Elephant[i].y);
    end;
    Next:=True;
  end;
end;
begin
  writeln('ChessBoard');
  k:=mink(n);
  repeat
    writeln(k);
    InitStrIndexes(strIndex,k);
    InitElephants(Elephant,strIndex,k);
    repeat
      bol:=Test(Elephant,CB,k);
    until bol or (not Next(Elephant,strIndex,k));
    inc(k);
  until bol or (k>n);
  if bol then Printresults(Elephant,k-1) else writeln('No result.');{печать результата}
  readln;
end.

P.S.
Не задавай большое n(2<=n<=6), ждать за... мучаешься.

Nestea

Дата 12.11.2005, 21:16 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Прям выручил!! )) А еще один вопросик, это не метод бэктрекинга случайно?

Nestea

Дата 12.11.2005, 21:28 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

darkart
При выполнении пишет
3
4
Эти циферки что обозначают?

darkart

Дата 12.11.2005, 22:16 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

Прям выручил!! )) А еще один вопросик, это не метод бэктрекинга случайно?

Да.

Цитата

При выполнении пишет
3
4
Эти циферки что обозначают?

Для какого количества слонов считается.

Nestea

Дата 13.11.2005, 10:23 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

[/QUOTE]
Для какого количества слонов считается.

Всмысле 4 - это сколько нужно слонов, чтобы побить все поле? а 3 что значит?

darkart

Дата 13.11.2005, 11:01 (ссылка)

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

Загрузка ...

Опытный

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

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

Работа алгоритма:
1)Вычисление минимально разумного количества слонов - mink,
т. к. один слон не может бить более 2*n-1 клеток поля, где n-размерность поля, то
mink=[(n*n)/(2*n-1)]+1
2)для всех k(mink=<k<=n) идет всевозможная расстановка k слонов на поле и проверяется всяли доска бита
Так вот выводимые числа - это k для которого идет расчет в данный момент. smile

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