Вычислить произведение первых ста натуральных чисел (использовать динамическую память) - Pascal
Формулировка задачи:
Решение задачи: «Вычислить произведение первых ста натуральных чисел (использовать динамическую память)»
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
.
В конце кода вычисляется факториал числа, используя динамическую память, и выводится его строковое представление.
Общая структура кода напоминает реализацию стека с использованием массива. Каждая функция использует ранее определенные функции и переменные, что позволяет избежать дублирования кода.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д