Реализовать рекурсивный алгоритм построения цепочки из имеющегося набора костей домино - PascalABC.NET (25080)

Узнай цену своей работы

Формулировка задачи:

Помогите пожалуйста... Реализовать рекурсивный алгоритм построения цепочки из имеющегося набора костей домино. Способ задания информации о количестве очков на костях выбрать самостоятельно.

Решение задачи: «Реализовать рекурсивный алгоритм построения цепочки из имеющегося набора костей домино»

textual
Листинг программы
const
   N = 10;
   D : array[0 .. N - 1, False .. True] of Integer =
   (
      (5,5), (1,2), (2,3), (4,5), (6,2),
      (4,2), (4,3), (3,1), (5,6), (6,6)
   );
var
   used : array[0 .. N - 1] of Boolean;
 
function Find_Sequence(First : Integer) : Boolean;
var
   i : Integer;
   Pair : Boolean;
begin
   result := True;
   i := 0;
   while (i < N) and used[i] do inc(i);
   if i = N then Exit;
 
   for i := 0 to N - 1 do
   begin
      if used[i] then Continue;
 
      if (First <> D[i, False]) and (First <> D[i, True]) then Continue;
      used[i] := True;
      Pair := False;
      if First = D[i, False] then Pair := True;
      if Find_Sequence(D[i, Pair]) then // <--- Вот она, рекурсия
      begin
         writeln(Format('{0}:{1}', D[i, Pair], D[i, not Pair]));
         Exit;
      end;
      used[i] := False;
   end;
   result := False;
end;
 
var i : Integer;
begin
   for i := 0 to Pred(N) do
       used[i] := False;
 
   for i := 0 to 6 do
      if Find_Sequence(i) then Break;
end.

Объяснение кода листинга программы

В данном коде реализуется рекурсивный алгоритм построения цепочки из имеющегося набора костей домино.

  1. В первой строке объявляется константа N, которая определяет количество костей в наборе (в данном случае 10).
  2. Далее объявляется двумерный массив D, который содержит информацию о каждой кости. Первый индекс указывает на номер кости, а второй - на ее свойство (True - это дубль, False - это простая кость).
  3. Затем объявляется массив used, который используется для отслеживания использованных костей.
  4. Далее идет объявление функции Find_Sequence, которая принимает в качестве параметра номер первой кости и возвращает булево значение (True, если цепочка найдена, False - если нет). Внутри функции объявляется цикл, который ищет первую неиспользованную кость с заданным свойством. Если такая кость найдена, то функция вызывает саму себя рекурсивно для поиска цепочки на основе этой кости.
  5. После определения функции идет блок кода, который ищет цепочки для каждого номера первой кости. Для этого используется цикл, который перебирает все возможные значения первой кости.
  6. Внутри цикла каждая кость проверяется на использование. Если кость не использована, то проверяется, является ли она дублем или простой костью. Если да, то вызывается функция Find_Sequence рекурсивно для поиска цепочки на основе этой кости. Если цепочка найдена, то она выводится на экран и функция возвращает True. Если нет, то кость помечается как использованная и цикл продолжается.
  7. В конце блока кода вызывается функция Find_Sequence для каждого номера первой кости. Если хотя бы одна цепочка найдена, то цикл прерывается.
  8. В конце программы выводится сообщение о том, что цепочки найдены. Таким образом, данный код реализует рекурсивный алгоритм построения цепочки из имеющегося набора костей домино.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 4.455 из 5
Похожие ответы