Подсчитать количество N-значных чисел - Pascal

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

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

Составить алгоритм, подсчитывающий количество всех N-значных чисел, сумма цифр которых равна данному числу N.

Решение задачи: «Подсчитать количество N-значных чисел»

textual
Листинг программы
const
  maxValue = 25;
var
  tbl : array[0 .. maxValue, 0 .. maxValue] of qword;
 
function CR(n : integer; s : integer) : qword;
var
  R : qword;
  i : integer;
begin
  if n = 0 then exit(Ord(s = 0));
  R := 0;
 
  if(tbl[n, s] <> qword(-1)) then exit(tbl[n, s]);
 
  for i := 0 to 9 do
    if s - i >= 0 then Inc(R, CR(Pred(n), s - i));
 
  tbl[n, s] := R;
  result := R;
end;
 
function FC(n : integer; s : integer) : qword;
var
  R : qword;
  i : integer;
begin
  fillqword(tbl, sizeof(tbl) div sizeof(qword), qword(-1));
  R := 0;
 
  for i := 1 to 9 do
    if s - i >= 0 then Inc(R, CR(Pred(n), s - i));
  result := R;
end;
 
var n : integer;
begin
  write('n = '); readln(n);
  writeln('result: ', FC(n, n));
end.

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

  1. В первой функции CR мы используем массив tbl размером от 0 до maxValue в обоих направлениях для хранения результатов. Если значение tbl[n, s] не равно qword(-1), то оно уже было учтено, иначе мы добавляем его в R. Мы также используем цикл for для увеличения R на результат вызова функции CR для предыдущего значения n, уменьшенного на i. В конце мы обновляем значение tbl[n, s] на R.
  2. Во второй функции FC мы сначала заполняем массив tbl значениями -1, используя функцию fillqword. Затем мы инициализируем R значением 0. Затем мы используем тот же цикл for, что и в первой функции, но вместо вызова функции CR мы вызываем функцию FC для предыдущего значения n, уменьшенного на i. В конце мы обновляем значение tbl[n, n] на R.
  3. В основной части программы мы считываем значение n с помощью функции readln. Затем мы вызываем функцию FC(n, n) и выводим результат.

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


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

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

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