Once a month Newsletter

* We will keep your email in safe place and will never misuse it. Unsubscribe in one click.

Proc 46 - 49

В задаче Proc46 находим НОД двух чисел с помощью алгоритма Евклида. Proc47 описывает преобразование дроби к несократимому виду. Proc48 - вычисление НОК (наименьшего общего кратного двух чисел). Proc49 - процедура нахождения НОД трех чисел.

Proc46. Описать функцию GCD2(A, B) целого типа, находящую наибольший общий делитель (НОД, greatest common divisor) двух целых положительных чисел A и B, используя алгоритм Евклида:

НОД(A, B) = НОД(B, A mod B), если B ≠ 0; НОД(A, 0) = A,

где «mod» обозначает операцию взятия остатка от деления. С помощью GCD2 найти наибольшие общие делители пар (A, B), (A, C), (A, D), если даны числа A, B, C, D.

{ Функция возвращает НОД чисел А и В, 
 используя алгоритм Евклида }
function GCD2(A, B: integer): integer;
var
  a1, b1, c: integer;
begin
  c := A; //начальное значение результата функции
  b1 := B; //запоминаем B
 { Если остаток не меньше 1, то выполняем цикл: }
  while b1 >= 1 do
  begin
    a1 := c; //Запоминаем a1
    c := b1;  //результату присваиваем остаток B
    b1 := a1 mod b1 //находим новый остаток
  end;
  GCD2 := c
end;

var
  A, B, C, D: integer;

begin
  writeln('Введите целые положительные числа A, B, C и D:');
  readln(A, B, C, D);
  writeln;
  writeln('Результат:');
  writeln(' НОД(', A, ', ', B, ') = ', GCD2(A, B));
  writeln(' НОД(', A, ', ', C, ') = ', GCD2(A, C));
  writeln(' НОД(', A, ', ', D, ') = ', GCD2(A, D))
end.

**type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 A **mod** B - остаток при целочисленном делении А на В **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 Сравните с решением на странице НОД. Там также вы сможете вычислить наибольший общий делитель прямо на странице.

Proc47. Используя функцию GCD2 (см. Proc46), описать процедуру Frac1(a, b, p, q), преобразующую дробь a/b к несократимому виду p/q (все параметры процедуры — целого типа, a и b — входные, p и q — выходные). Знак результирующей дроби p/q приписывается числителю (т. е. q > 0). С помощью Frac1 найти несократимые дроби, равные a/b + c/d, a/b + e/f, a/b + g/h (числа a, b, c, d, e, f, g, h даны).

{ Функция возвращает НОД чисел А и В, 
 используя алгоритм Евклида }
function GCD2(A, B: integer): integer;
var
  a1, b1, gcd: integer;
begin
  gcd := A; //начальное значение результата функции
  b1 := B; //запоминаем B
 { Если остаток не меньше 1, то выполняем цикл: }
  while b1 >= 1 do
  begin
    a1 := gcd; //Запоминаем a1
    gcd := b1;  //результату присваиваем остаток B
    b1 := a1 mod b1 //находим новый остаток
  end;
  GCD2 := gcd
end;

{ Процедура приводит дробь a/b к несократимому виду p/q }
procedure Frac1(a, b: integer; var p, q: integer);
begin
 { Находим числитель и знаменатель сокращенной дроби: }
  p := abs(a) div GCD2(abs(a), abs(b));
  q := abs(b) div GCD2(abs(a), abs(b));
 { Числитель отрицательный, если а и b - противоположного знака: }
  if a * b < 0 then p := -p 
end;

var
  p, q, a, b, c, d, e, f, g, h: integer;

begin
  writeln('Введите целые чила a, b, c, d, e, f, g, h:');
  readln(a, b, c, d, e, f, g, h);
  writeln;
  writeln('Результат:');
  Frac1(a * d + b * c, b * d, p, q);
  writeln(' ', a, '/', b, ' + ', c, '/', d, ' = ', p, '/', q);
  Frac1(a * f + b * e, b * f, p, q);
  writeln(' ', a, '/', b, ' + ', e, '/', f, ' = ', p, '/', q);
  Frac1(a * h + b * g, b * h, p, q);
  writeln(' ', a, '/', b, ' + ', g, '/', h, ' = ', p, '/', q);
end.

**type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 A **mod** B - остаток при целочисленном делении А на В **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **function** Abs(x: real): real;: Возвращает модуль числа x. A **div** B - целочисленное деление А на В **function** Abs(x: real): real;: Возвращает модуль числа x. **function** Abs(x: real): real;: Возвращает модуль числа x. **function** Abs(x: real): real;: Возвращает модуль числа x. A **div** B - целочисленное деление А на В **function** Abs(x: real): real;: Возвращает модуль числа x. **function** Abs(x: real): real;: Возвращает модуль числа x. **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 Proc48. Наименьшее общее кратное (least common multiple) двух целых положительных чисел A и B равно A·(B/НОД(A, B)), где НОД(A, B) — наибольший общий делитель A и B. Используя функцию GCD2 (см. Proc46), описать функцию LCM2(A, B) целого типа, находящую наименьшее общее кратное чисел A и B. С помощью LCM2 найти наименьшие общие кратные пар (A, B), (A, C), (A, D), если даны числа A, B, C, D.

{ Функция LCM2(A, B: integer): integer 
 возвращает НОК чисел А и В }
function LCM2(A, B: integer): integer;

  { Функция возвращает НОД чисел А и В }
  function GCD2(A, B: integer): integer;
  var
    a1, b1, gcd: integer;
  begin
    gcd := A; //начальное значение результата функции
    b1 := B; //запоминаем B
   { Если остаток не меньше 1, то выполняем цикл: }
    while b1 >= 1 do
    begin
      a1 := gcd; //Запоминаем a1
      gcd := b1;  //результату присваиваем остаток B
      b1 := a1 mod b1 //находим новый остаток
    end;
    GCD2 := gcd
  end;

{ Тело основной функции LCM2 }
begin
  LCM2 := A * (B div GCD2(A, B)) //НОК(А,В)
end;

var
  A, B, C, D: integer;

begin
  writeln('Введите целые положительные числа A, B, C и D:');
  readln(A, B, C, D);
  writeln;
  writeln('Результат:');
  writeln(' НОК(', A, ', ', B, ') = ', LCM2(A, B));
  writeln(' НОК(', A, ', ', C, ') = ', LCM2(A, C));
  writeln(' НОК(', A, ', ', D, ') = ', LCM2(A, D))
end.

**type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 A **mod** B - остаток при целочисленном делении А на В A **div** B - целочисленное деление А на В **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 Смотрите задачу Наименьшее общее кратное без процедур.

Proc49. Учитывая соотношение НОД(A, B, C) = НОД(НОД(A, B), C) и используя функцию GCD2 (см. Proc46), описать функцию GCD3(A, B, C) целого типа, находящую наибольший общий делитель трех целых положительных чисел A, B, C. С помощью GCD3 найти наибольшие общие делители троек (A, B, C), (A, C, D) и (B, C, D), если даны числа A, B, C, D.

{ Функция GCD3(A, B, C: integer): integer возвращает НОД чисел 
А, В и C, используя соотношение НОД(A, B, C) = НОД(НОД(A, B), C) }
function GCD3(A, B, C: integer): integer;

  { Функция возвращает НОД чисел А и В, используя алгоритм Евклида }
  function GCD2(A, B: integer): integer;
  var
    a1, b1, t: integer;
  begin
    t := A; //начальное значение результата функции
    b1 := B; //запоминаем B
   { Если остаток не меньше 1, то выполняем цикл: }
    while b1 >= 1 do
    begin
      a1 := t; //Запоминаем a1
      t := b1;  //результату присваиваем остаток B
      b1 := a1 mod b1 //находим новый остаток
    end;
    GCD2 := t
  end;

begin
  GCD3 := GCD2(GCD2(A, B), C);//НОД(А,В,С)
end;

var
  A, B, C, D: integer;

begin
  writeln('Введите целые положительные числа A, B, C и D:');
  readln(A, B, C, D);
  writeln;
  writeln('Результат:');
  writeln(' НОД(', A, ', ', B, ', ', C, ') = ', GCD3(A, B, C));
  writeln(' НОД(', A, ', ', C, ', ', D, ') = ', GCD3(A, C, D));
  writeln(' НОД(', B, ', ', C, ', ', D, ') = ', GCD3(B, C, D))
end.

**type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647 A **mod** B - остаток при целочисленном делении А на В **type** integer;: Представляет 32-битовое целое число со знаком.Диапазон значений: -2 147 483 648 .. 2 147 483 647