GAECHKA
Твоя помощница в решении задач

Функция подсчета чисел Бернулли

Стоит задача: Написать функцию, которая считает числа Бернулли.(Формула снизу).
Вроде бы ничего сложного, но затруднение вызывает подсчет факториала(Он же биноминальный коефициент).
Попытался найти примеры реализаций на других языках, но ничего не нашел.

Напишите или функцию на паскале, или напишите словами, как должны происходить итерации.
Спасибо!

$$ B_0=1\\\\B_n=\frac{-1}{n+1}\sum_{k=1}^n \binom{n+1}{k+1} B_{n-k},\quad n\in\mathbb{N}. $$
0
вопрос задан

Источник


4 ответа
uses crt;
 {подсчет числа сочетаний без факториала}
function sochet(n,m:integer):extended;
var i:integer;
    c:extended;
begin
c:=1;
for i:=1 to m do
c:=c*(n-i+1)/i;
sochet:=c
end;
{подсчет чисел Бернулли с рекурсией}
function bernulli(n:integer):extended;
var k:integer;
    s,t:extended;
begin
if n=0 then bernulli:=1
else if n=1 then bernulli:=-0.5
else
 begin
  s:=0;
  for k:=1 to n do
   begin
    t:=bernulli(n-k);{запомним результат и очистим стек памяти}
    s:=s+sochet(n+1,k+1)*t;{вычислим следующее значение суммы}
   end;
  bernulli:=s*(-1)/(n+1);{вычислим число Бернулли}
 end;
if (n>1) and odd(n) then bernulli:=0{если N>1 и нечетное, то =0}
end;
var n:integer;
begin
clrscr;
write('n=');
readln(n);
write(bernulli(n):0:10);
readln
end.
при N>20 считает медленно...
Первые 20 сравнил с этим
https://ru.wikipedia.org/wiki/%D0%A7...BB%D0%BB%D0%B8
Поправил
Puporev, Спасибо, а можете комментарии к программе подправить? Некоторые комментарии с иероглифами.
Подниму тему, рассмотрев её решение с другой стороны.
Возможно, что преподаватель будет ждать решение, сходное с предложенным Puporev, тогда возникнут вопросы о "сверхзнаниях".

О другом алгоритме вычисления чисел Бернулли

Вычисления производятся по реккурентной формуле
$$B_0=1$$

$$B_n=\frac{-1}{n+1}\sum_{k=1}^{n}{C_{n+1}^{k+1}}{B_{n-k}}$$

Несложно заметить, что при вычислении отдельного числа Bn все коэффициенты
$$C_{n+1}^{k+1}$$
в формуле являются элементами одной строки треугольника Паскаля. При вычислении Bn+1 будет использоваться уже следующая строка этого треугольника. Казалось бы, что это ничего не даёт. Но, существуют компактные алгоритмы вычисляющие только одну строку треугольника Паскаля на основе предыдущей строки, причём новая строка располагается на месте предыдущей, т.е. бережно относятся к выделяемой памяти
Получить и напечатать первые n строк треугольника Паскаля

Код для Turbo Pascal
{
Вычисление чисел Бернулли (Bernoulli)
    числитель   OEIS:A027641
    знаменатель OEIS:A027642
}
program test;
 
type
  real = double;
  integer = longint;
 
const
  BN: array [0..21] of real = (1, -1 / 2, 1 / 6, 0, -1 / 30, 0, 1 / 42, 0, -1 / 30, 0,
    5 / 66, 0, -691 / 2730, 0, 7 / 6, 0, -3617 / 510, 0, 43867 / 798,
    0, -174611 / 330, 0);
 
  procedure Bernoulli(n: integer; var B: array of real);
  var
    C: array [0..33] of integer;
    i, k: integer;
    S: real;
  begin
    C[0] := 1;
    C[1] := 1;
    B[0] := 1;
    for i := 1 to n do
    begin
      C[i + 1] := 0;
      for k := i + 1 downto 1 do
        C[k] := C[k - 1] + C[k];
      S := 0;
      for k := i - 1 downto 0 do
        S := S + C[k] * B[k];
      B[i] := -S / (i + 1);
    end;
  end;
 
const
  n = 21;
var
  B: array [0..n] of real;
  i: integer;
 
begin
  Bernoulli(n, B);
 
  writeln('   Вычисленное          Точное               Погрешность');
  for i := 0 to 21 do
    writeln(B[i]: 20: 15, ' ', BN[i]: 20: 15, ' ', B[i] - BN[i]: 20: 15);
end.