Вычислить произведение первых ста натуральных чисел (использовать динамическую память) - Pascal

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

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

Написать программу, вычисляющую произведение первых ста натуральных чисел. Использовать динамическую память и указатели.

Решение задачи: «Вычислить произведение первых ста натуральных чисел (использовать динамическую память)»

textual
Листинг программы
program la;
type 
  bigint = array[0..100] of int64;
var 
  base : int64;
  x, y, z, res, fact, q, w : bigint;
  i, n : integer;
 
function get_max(a, b : integer) : integer;
begin
  if(a > b) then get_max := a else get_max := b;
end;
 
procedure copy_bigint(var bto : bigint; var bfrom : bigint);
var ii : integer;
begin
  for ii := 0 to 100 do bto[ii] := bfrom[ii];
end;
 
procedure make_bigint(var a : bigint; x : int64);
var ii: integer;
begin
  for ii := 0 to 100 do a[ii] := 0;
  ii := 0;
  while (x > 0) do begin
    a[ii] := x mod base;
    x := x div base;
    ii := ii + 1;
  end;
end;
 
function get_size_bigint(var a : bigint) : integer;
var ii, f: integer;
begin
  ii := 100;
  f := 0;
  while(ii >= 0) do begin
    if(a[ii] <> 0) then begin
      f := 1;
      break;
    end;
      
    ii := ii - 1;
  end;
  
  if(f <> 0) then get_size_bigint := ii + 1 else get_size_bigint := 1;
end;
 
procedure add_bigint(var a : bigint; var b : bigint; var c : bigint);
var carry : int64;
    ii, size : integer;
begin
  make_bigint(c, 0);
  carry := 0;
  size := get_max(get_size_bigint(a), get_size_bigint(b));
  ii := 0;
  while((ii < size) or (carry <> 0)) do begin
    c[ii] := carry + a[ii] + b[ii];
    if(c[ii] >= base) then carry := 1 else carry := 0;
    if(carry <> 0) then c[ii] := c[ii] - base;
    ii := ii + 1;
  end;
end;
 
//умножение(тривиальное, в столбик) O(n^2), для большего ускорения умножение можно делать через алгоритм карацубы ~ O(n^1.573), или БФТ (FFT) (быстрое преобразование фурье) O(n * log(n))
procedure mul_bigint(var a : bigint; var b : bigint; var c : bigint);
var carry, cur : int64;
    ii, jj, sizea, sizeb : integer;
begin
  make_bigint(c, 0);
  carry := 0;
  sizea := get_size_bigint(a); sizeb := get_size_bigint(b);
  
  for ii := 0 to sizea - 1 do begin
    jj := 0;
    while((jj < sizeb) or (carry <> 0)) do begin
      cur := carry + c[ii + jj] + a[ii] * b[jj];
      c[ii + jj] := cur mod base;
      carry := cur div base;
      jj := jj + 1;
    end;
  end;
end;
 
function to_str_bigint(var a : bigint) : string;
var ii, jj : integer;
    s, st : string;
begin
  ii := get_size_bigint(a);
  st := IntToStr(a[ii - 1]);
  jj := ii - 2;
  while(jj >= 0) do begin
    s := IntToStr(a[jj]);
    while(length(s) < 9) do s := '0' + s;
    st := st + s;
    jj := jj - 1;
  end;
  to_str_bigint := st;
end;
 
begin
  base := 1000000000;
  
  //считаем факториал:
  make_bigint(fact, 1);
  for i := 2 to 100 do begin
    //fact := fact * q
    make_bigint(q, i);
    mul_bigint(fact, q, w); //w := fact * q
    copy_bigint(fact, w); //fact := w
  end;
  
  writeln(to_str_bigint(fact));  
end.

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

Этот код написан на языке Pascal и предназначен для вычисления произведения первых ста натуральных чисел с использованием динамической памяти. В начале объявляются необходимые типы данных и переменные. Затем идет функция get_max, которая сравнивает два числа и возвращает максимальное из них. Далее идет функция get_size_bigint, которая вычисляет размер наибольшего числа, которое может быть помещено в массив типа bigint. Следующая функция add_bigint используется для сложения трех чисел с использованием массива типа bigint. Функция mul_bigint выполняет умножение двух чисел с использованием массива типа bigint. В конце кода вычисляется факториал числа, используя динамическую память, и выводится его строковое представление. Общая структура кода напоминает реализацию стека с использованием массива. Каждая функция использует ранее определенные функции и переменные, что позволяет избежать дублирования кода.

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


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

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

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