Быстрое нахождение значений в паскалевом треугольнике без рекурсии

Delphi , Синтаксис , Массивы

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

Задача

В статье рассматривается задача быстрого нахождения значений в паскалевом треугольнике, используя одномерный массив, который хранит значения треугольника в упорядоченной последовательности слева направо.

Пример массива

int pascal[10] = { 1, 1, 1, 1, 2, 1, 1, 3, 3, 1 };

Вопрос пользователя

Как использовать данный массив для быстрого нахождения комбинаций двух чисел, например, для нахождения "3 из 1", где ответом будет число 3? Каким образом корректно вычислить индекс, по которому нужно обратиться к массиву? Также, как можно использовать существующий массив для продолжения построения паскалева треугольника без применения рекурсии, например, используя рекуррентное соотношение?

Альтернативный ответ

Пользователь также задает вопрос о необходимости использования массива для хранения треугольника, указывая, что, возможно, быстрее использовать формулу для вычисления комбинаций: C(n, k) = (n!)/((k!)(n-k)!).

Подтвержденный ответ

Если же настаивать на использовании массива, можно использовать следующий алгоритм для вычисления индекса в массиве на основе того, что каждая новая строка треугольника содержит на один элемент больше, чем предыдущая, и что сумма чисел от 1 до N вычисляется по формуле:

function Choose_N_over_K(N, K: Integer): Integer;
var
  pascal: array [0..15] of Integer = (1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1);
  index: Integer;
begin
  index := N * (N + 1) div 2 + K;
  Result := pascal[index];
end;

Пример использования функции:

procedure TForm1.Button1Click(Sender: TObject);
begin
  ShowMessage(IntToStr(Choose_N_over_K(4, 2))); // Выведет 6
end;

Пример кода на Object Pascal (Delphi)

Для демонстрации использования массива в контексте языка Object Pascal, можно реализовать функцию Choose_N_over_K следующим образом:

function Choose(N, K: Integer): Integer;
var
  pascal: array of Integer = [1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1];
  index: Integer;
begin
  index := (N * (N + 1) div 2) + K;
  Result := pascal[index - 1]; // Индексация начинается с 0, поэтому вычитаем 1
end;

Использование функции в коде на Delphi:

procedure TForm1.Button1Click(Sender: TObject);
begin
  Memo1.Lines.Add(IntToStr(Choose(4, 2))); // Выведет 6 в компонент Memo
end;

Заключение

В данной статье была рассмотрена проблема быстрого доступа к значениям паскалева треугольника через одномерный массив. Представлен пример реализации функции для вычисления индекса в массиве, что позволяет эффективно находить значения треугольника без использования рекурсии. Это может быть полезно для оптимизации алгоритмов, работающих с биномиальными коэффициентами, в том числе для программистов, использующих язык Delphi и Object Pascal.

Создано по материалам из источника по ссылке.

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

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Массивы ::