Реализовать рекурсивный алгоритм построения цепочки из имеющегося набора костей домино - 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.
Объяснение кода листинга программы
В данном коде реализуется рекурсивный алгоритм построения цепочки из имеющегося набора костей домино.
- В первой строке объявляется константа N, которая определяет количество костей в наборе (в данном случае 10).
- Далее объявляется двумерный массив D, который содержит информацию о каждой кости. Первый индекс указывает на номер кости, а второй - на ее свойство (True - это дубль, False - это простая кость).
- Затем объявляется массив used, который используется для отслеживания использованных костей.
- Далее идет объявление функции Find_Sequence, которая принимает в качестве параметра номер первой кости и возвращает булево значение (True, если цепочка найдена, False - если нет). Внутри функции объявляется цикл, который ищет первую неиспользованную кость с заданным свойством. Если такая кость найдена, то функция вызывает саму себя рекурсивно для поиска цепочки на основе этой кости.
- После определения функции идет блок кода, который ищет цепочки для каждого номера первой кости. Для этого используется цикл, который перебирает все возможные значения первой кости.
- Внутри цикла каждая кость проверяется на использование. Если кость не использована, то проверяется, является ли она дублем или простой костью. Если да, то вызывается функция Find_Sequence рекурсивно для поиска цепочки на основе этой кости. Если цепочка найдена, то она выводится на экран и функция возвращает True. Если нет, то кость помечается как использованная и цикл продолжается.
- В конце блока кода вызывается функция Find_Sequence для каждого номера первой кости. Если хотя бы одна цепочка найдена, то цикл прерывается.
- В конце программы выводится сообщение о том, что цепочки найдены. Таким образом, данный код реализует рекурсивный алгоритм построения цепочки из имеющегося набора костей домино.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д