Наименьший общий делитель как найти паскаль

Помогите пожалуйста написать программу которая будет вычислять наименьший общий делитель и наибольшее общее кратное. Использовать алгоритм Евклида.

В помощь:

На множестве целых чисел определены операции сложения, обратная операция вычитания и операция умножения. Операция деления, обратная операции умножения, выполняется не для всех пар чисел, то есть является на множестве целых чисел «частичной операцией».
Число а делится на число b 0, если существует число q такое, что b=qc. , (все числа целые).
В этом случае говорят, что число b делит число a. При этом число b является делителем числа а или множителем в разложении числа a на множители.
Общим делителем двух или нескольких чисел называется число, являющееся делителем каждого из этих чисел.
Если а1,…,аn целые числа и хотя бы одно из них не равно нулю, то множество их общих делителей конечно и среди этих делителей существует наибольшее число.
Наибольшим общий делителем (НОД) чисел а1,…,аn называется наибольший из их общих делителей.
НОД целых чисел а и b называется положительный делитель чисел а и b, делящийся на любой другой общий делитель этих чисел.
Cвойства НОД:
1) НОД(a,b) = НОД(b,a)
2) НОД(a,0) = |a|
3) НОД(a,b,с) = НОД(a, НОД(b,c))
4) НОД(a,b) = НОД(-a,b)
Для вычисления наибольшего общего делителя двух целых чисел можно использовать метод разложения на сомножители.
70 делится на 2, 5, 7, 10, 14, 35.
42 делится на 2, 3, 6, 7, 14, 18, 21.
НОД(70, 42) = 14.
Когда а не делится на b, то говорят о делении а на b с остатком r.
Теорема о делении с остатком. Если а и b целые положительные числа, то существуют единственные целые числа q и r такие, что
a = b*q + r, 0 ≤. r< b
Число q называют неполным частным при делении a на b,
число r называют остатком от деления а на b.
Деление по модулю (в более узком значении) – арифметическая операция, результатом которой является остаток от деления целого числа на другое целое число, то есть операция нахождения остатка от деления, а также сам остаток от деления .
Деление по модулю (в более широком значении) – арифметическая операция, результатом которой является два целых числа: неполное частное и остаток от деления целого числа на другое целое число. То есть имеется в виду операция, которую правильнее называть делением c остатком.
Пример, в котором мы сталкиваемся с Модульной арифметикой в повседневной жизни – “арифметика часов”. Допустим, сейчас 3 часа после полудня, через 14 часов будет 5 часов утра следующего дня:
(3+14) mod 12= 17 mod 12=5. Это арифметика по модулю 12.
А вот тоже самое, но по модулю 24: (15+14) mod 24= 29 mod 24=5.
Также вычисляются минуты, секунды как деление по модулю 60.

Алгоритм вычисления наибольшего общего делителя Евклида (“Начала”, 300 лет до н.э.) – один из древнейших классических нетривиальных алгоритмов.
В основе алгоритма Евклида лежит повторное деление с остатком: вычисляется остаток от деления (a mod b), затем b mod (a mod b) и так далее, пока остаток не будет равен нулю.
Алгоритм Евклида вычисления НОД(a,b) для a, b  0.
1. Если b =0, то результат := а и алгоритм заканчивает работу.
2. Положить r := a mod b, a := b, b := r, и вернуться на шаг 1.
Процесс вычисления наибольшего общего делителя чисел a1, a2 по алгоритму Евклида выглядит так:
a1 = a2 q1 + a3 0 ≤ a3 < a2
a2 = a3 q2 + a4 0 ≤ a4 < a3
a3 = a4 q3 + a5 0 ≤ a5 < a4

am-2 =am-1 qm-2 + am 0 ≤ am < am-1
am-1 =am qm-1
Результат: НОД(a1, a2) = am.
Остановка гарантируется, поскольку остатки от делений образуют строго убывающую последовательность натуральных чисел.
Пример: НОД(70, 42)
70 = 42 * 1 + 28 r := 70 mod 42 = 28, a := 42, b := 28
42 = 28 * 1 + 14 r := 42 mod 28 = 14, a := 28, b := 14
28 = 14 * 2 r := 28 mod 14 = 0
Результат: НОД(70, 42)=3.

Еще пример: НОД(723,288):

Результат: НОД(723,288)=3.
Эта процедура хороша как для вычисления вручную, так и для программной реализации. Соответствующая программа короткая и быстрая.
Некоторые свойства целых чисел позволяют улучшить программную реализацию алгоритма Евклида:
1) если числа а и b четные, то НОД(a, b) = 2 НОД(a/2, b/2),
2) если а четное и b нечетное, то НОД(a, b) = НОД(a/2, b),
3) НОД(a, b) = НОД(a–b, b),
4) если числа а и b нечетные, то (а – b) четное и НОД(a, b) = НОД((a–b)/2, b).

ДОПОЛНЕНИЕ
Алгоритм Евклида для целых чисел
Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

Тогда НОД(a,b), наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности.
Проще сформулировать алгоритм Евклида так: если даны натуральные числа и и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.

Пример
Для иллюстрации, алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала, от 1071 отнимем кратное значение 462, пока не получим разность меньше чем 462. Мы должны дважды отнять 462, (q0 = 2), оставаясь с остатком 147
1071 = 2 × 462 + 147.
Затем от 462 отнимем кратное значение 147, пока не получим знаменатель меньше чем 147. Мы должны трижды отнять 147 (q1 = 3), оставаясь с остатком 21.
462 = 3 × 147 + 21.
Затем от 147 отнимем кратное значение 21, пока не получим знаменатель меньше чем 21. Мы должны семь раз отнять 21 (q2 = 7), оставаясь без остатка.
147 = 7 × 21 + 0.
Таким образом последовательность a>b>R1>R2>R3>R4>…>Rn в данном конкретном случае будет выглядеть так:
1071>462>147>21

Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(1071, 462)=21.
В табличной форме, шаги были следующие
Шаг k Равенство Частное и остаток
0 1071 = q0 462 + r0 q0 = 2 и r0 = 147
1 462 = q1 147 + r1 q1 = 3 и r1 = 21
2 147 = q2 21 + r2 q2 = 7 и r2 = 0; алгоритм заканчивается

var
    f: longint;
    n, i: integer;
Begin
    write('n = '); readln(n);
    f := 1;
    For i:=2 to n do
        f := f * i;
    writeln(n,'! = ', f);
End.

2. Второй алгоритм, который необходимо знать — нахождение НОК двух чисел. НОК — наименьшее общее кратное, то есть минимальное число, которое одновременно делится на оба числа.

В паскаль это реализуется достаточно просто:

var a,b,c:integer; //Описание переменных
begin //Начало программы
	readln(a,b); //Считывание а и б
	c:=a*b; //Перемножение
	repeat //Цикл с постусловием
		if a>b then a:=a-b else b:=b-a;   
	until a=b; //Цикл до тех пор, пока а не равно б
	c:= c div a; //Делим c на a нацело и получаем нок
	writeln('НОК=', c); //Выводим значение
end.//Конец программы

var a,b,c: integer; //Описание переменных
begin //Начало программы
  writeln('Введите a,b: '); //Диалог с пользователем
  read(a,b);  //Чистывание чисел
  while b<>0 do //Вход в цикл while, пока b не равно 0
  begin
    c := a mod b; //Присваивание с остатка деления a/b
    a := b; 
    b := c;
  end;
  writeln('НОД = ',a); //Вывод делителя
end.//Конец программы 

Скачать: nod.pas
На сегодня все, во второй части расскажу про возведение числа в степень, а также про нахождение минимального и максимального в массиве.

Дата: 2013-10-04 13:18:03   Просмотров: 45316

Теги: Паскаль урок уроки Pascal основные алгоритмы

Приведем 3 программы поиска наибольшего общего делителя двух натуральных чисел, основанных на:

• алгоритме Евклида
• перебора возможных делителей числа
• разложения чисел на простые множители

Что такое наибольший общий делитель двух натуральных чисел m и n, или НОД(m, n)

НОД двух натуральных чисел – это такое наибольшее натуральное число, которое одновременно делит без остатка оба этих числа.

Алгоритм Евклида

Евклид – древнегреческий математик, геометр, автор первого из дошедших до нас теоретических трактатов по математике.

Алгоритм Евклида – один из наиболее ранних численных алгоритмов в истории. Евклид впервые дал описание этого алгоритма в книгах «Начала». Изначально этот алгоритм назывался «взаимным вычитанием», так как его принцип заключался в последовательном вычитании из большего числа меньшего, пока в результате не получится ноль.

Сформулируем алгоритм

Пусть даны два натуральных числа m и n. Пока числа m и n не равны (или их разница не равна 0), большее число заменить их разницей. В качестве ответа взять любое из чисел.

Пример:

Пусть m = 12, n = 18

12<>18, n = 18 – 12 = 6

12<>6, m = 12 – 6 = 6

6<>6, НОД(12, 18) = 6

Программа на языке программирования Паскаль (алгоритм Евклида)

var m, n:integer;

begin

  writeln(‘Введите два натуральных числа m и n:’);  

  readln(m,n);

  while m<>n do

  begin

    if m>n then m:=m-n

           else n:=n-m;

  end;

  writeln(‘НОД(m,n): ‘,m);

end.

Результат запуска программы

Перебор возможных делителей числа

Будем использовать алгоритм, разобранный ранее в этом блоге.

Запустим цикл for с счетчиком k от 1 до n, будем проверять условие: если число n делится на значение счетчика k без остатка (n mod k = 0), то значение счетчика k – это делитель числа n, значение k можно вывести на экран или сохранить в отдельной переменной.

Поскольку нам нужен наибольший общий делитель чисел m и n, поэтому запустим цикл до минимального из чисел m и n (другое будет лишним), и будем проверять условие: если число m делится на значение счетчика цикла k без остатка и число n делится на значение счетчика цикла k без остатка одновременно (воспользуемся операцией and), это и будет их общий делитель.

Программа на языке программирования Паскаль (перебор возможных делителей числа)

var m, n, k, p:integer;

begin

  writeln(‘Введите два натуральных числа m и n:’);

  readln(m,n);

  for k:=1 to min(m,n) do 

  begin

    if (m mod k = 0) and (n mod k=0) then p:=k;

  end;

  writeln(‘НОД(m,n): ‘,p);

end.

Функция min будет работать в PascalABC.NET, в случае использования другой среды, нужно до цикла определить наибольшее число из m и n.

Разложение чисел на простые множители

Ранее мы разбирали алгоритм разложения натурального числа на простые множители. 

Как связаны простые множители числа и НОД. Приведем пример.

Пусть m = 18,  n = 12

Выполним разложение на простые множители.

Множители числа m: 2 3 3

Множители числа n: 2 2 3

Выделим их общие простые множители – это числа 2 и 3. В качестве наибольшего общего делителя нужно взять из произведение: 2 * 3 = 6. НОД(12, 18) = 6.

Пусть m = 36,  n = 48

Множители числа m: 2 2 3 3

Множители числа n: 2 2 2 2 3

Общие простые множители – это числа 2 2 3. Произведение этих множителей равно 12. НОД(36, 48) = 12.

Для нахождения НОД двух чисел нужно выполнить их разложение на простые множители и в качестве ответа взять произведение их общих множителей.

Как будем решать задачу

Для хранения множителей числа воспользуемся списком (PascalABC.NET), в него легко добавлять значение командой add.

Описание списка с именем nod в блоке var

var nod:List<integer>;

Создание нового пустого списка в теле программы

nod:=new List<integer>;

Добавление значения в конец списка

nod.add(значение);

Создадим два списка (s1 и s2) для хранения множителей числа m и n соответственно. С помощью конструкции вложенных циклов переберем все элементы списков и сравним на равенство, если множители равны, сохраним их в списке nod, а значения элементов списков сделаем равными -1 и -2 соответственно (чтобы далее их повторное сравнение на равенство было ложным) . В качестве ответа возьмем произведение элементов списка nod командой nod.Product.

Программа на языке программирования Паскаль (разложение чисел на простые множители)

var

  m, n, k1, k2: integer;      

  s1, s2, nod: List<integer>;

begin

  writeln(‘Введите два натуральных числа m и n:’);   

  readln(m, n);  

  s1 := new List<integer>; 

  s2 := new List<integer>; 

  nod := new List<integer>;

  k1 := 2; k2 := 2;  

  while (m > 1) or (n > 1) do   

  begin

    while m mod k1 = 0 do     

    begin

      m := m div k1;      

      s1.Add(k1); //добавить значение в список можно и так: s1+=k1;

    end;     

    k1 += 1;     

    while n mod k2 = 0 do    

    begin

      n := n div k2;       

      s2.Add(k2);     

    end;     

    k2 += 1;   

  end;   

  //writeln(s1, s2); 

  for k1:=0 to s1.Count-1 do //элементы списка нумеруются с 0, длина списка s1.count

    for k2:=0 to s2.Count-1 do

      if s1[k1]=s2[k2] then //s1[k1] – обращение к элементу списка по его номеру

        begin 

        nod.Add(s1[k1]);

        s1[k1]:=-1;

        s2[k2]:=-2;

        end;

  //println(s1,s2,nod);

  println(‘НОД(m,n): ‘,nod.Product);

end.

Это программа состоит из самого большого количества строк. Насколько она эффективна?

Задача на применение НОД

Даны числа: a = 2³ • 3¹⁰ • 5 • 7² , b = 2⁵ • 3 • 11. Чему равен  НОД (a,b)?

Математика и числа

Чётность/нечётность чисел

if Odd (Number) then 
  writeln (Number, ' нечётно')
else
  writeln (Number, ' чётно');

Делимость (кратность) чисел

if Number mod 3 = 0 then
  writeln (Number, ' делится на 3 без остатка');

Наибольший Общий Делитель

{ Евклид (Euclidus) }
function GCD (A: integer;  B: integer): integer;
begin
    while (a <> 0) and (b <> 0) do
       if a >= b then
         a := a mod b
       else 
         b := b mod a;
    GCD := a + b; { один - ноль }
end;

Наименьшее Общее Кратное

function LCM (A: integer;  B: integer): integer; 
begin
     LCM := a * b div GCD (a, b)
end;

Степень

function Power(Base, N: integer): longint;
{ Base - основание , N - степень }
var
   Result: longint;
   i: word;
begin
   Result := 1; { придаём начальное значение }
   for i := 1 to N do
     Result := Result * Base;
 
   Power := Result;
end;

function PowerExp (A, N: real): real;
begin
   if A > 0 then
     PowerExp := Exp ( N * Ln (A) )
   else 
     PowerExp := 0;
end;

Факториал

function Factorial(N: word): longint;
var
   Result: longint;
   i: word;
begin
   Result := 1;
   for i := 1 to N do 
     Result := Result * N;
 
   Power := Result;
end;

function Factorial (N: word): longint;
begin
   if N = 0 then
     Factorial := 1 
   else 
     Factorial := N * Factorial (N - 1);
end;

Вещественный и целый типы

   var
       r : real;
     begin
       r := Round ( 123.456);  {    123 }
       r := Round ( 123.778);  {    124 }
       r := Trunc ( 123.456);  {    123 }
       r := Trunc (-123.778);  {   -123 }
       r := Frac  ( 123.456);  {  0.456 }
       r := Int   ( 123.456);  {  123.0 }
       r := Int   (-123.456);  { -123.0 }
     end.

Случайные числа

  Randomize;
  X := Random (N + 1) - 2 * N;

Как проверить простое ли число?

function isPrime(X: word): boolean;
var
i: integer;
Begin
     isPrime:=false;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     while i <= sqrt(x) do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
 
     isPrime:=true;
End;

Разложение числа на множители

procedure Factorization(x: word);
var i: word;
 
 procedure DivX; { делим на простое число, пока делится без остатка }
 begin
      while (x>1) and (x mod i = 0) do
      begin
           write(i:4);
           x:= x div i;
      end;
 end;
 
begin
     i:=2;
     DivX;
     i:=3;
     while (i < x div 2) do
     begin
           DivX;
           inc(i,2); { <=> i:=i+2; только нечётные числа }
     end;
     if x>1 then writeln(x:4);
end;

Приближённое представление числа в виде дроби

VAR p,q,qmax:integer;
    d, r, min: real;
BEGIN
   write('r, qmax=');
   readln(r, qmax); { r - не целое число, qmax - кол-во итераций (циклов) }
   p:=0; q:=1; min:=r;
   REPEAT
     IF p / q < r
          THEN inc(p)
          ELSE inc(q);
     d:=abs(r-p/q);
     IF d < min THEN
     BEGIN
          min:=d;
          writeln(p:7,'/',q)
     END
   UNTIL (q >= qmax) OR (d = 0);
   readln;
END.

Как работать с отдельными битами?

FUNCTION IsBitOn (n: word; b : BYTE): BOOLEAN; { Проверяем, установлен ли бит }
BEGIN 
     isBitOn:=((n SHR b) AND 1) = 1
END;
 
PROCEDURE SetBitOn (VAR n: Word; b: BYTE); { Устанавливаем бит }
BEGIN
     N:= N OR (1 SHL b)
END;
 
PROCEDURE XORBit (VAR n: Word; b: BYTE); { Переключаем бит }
BEGIN
     N:= N XOR (1 SHL b)
END;

Как узнать из каких цифр состоит целое число?

Var X : Integer;
Begin
 X:=12345;
 Writeln('Число состоит из таких цифр:');
 While X <> 0 Do
  Begin
   Writeln(X Mod 10);
   X:=X Div 10;
  End;
End.

Как быстро делить/умножать числа на степень двойки ?

i:=i shl 1; { i:=i * 2^1}
i:=i shl 2; { i:=i * 2^2}
{и т.д.}
i:=i shr 1; { i:=i div 2^1}
i:=i shr 2; { i:=i div 2^2}
{и т.д.}

Более быстрое разложение числа на множители

{$N+, E+}
 
function FermaFactorization (N : Comp) : Comp;
 
var
  X, Y, R, Z, ZZ : Comp;
 
begin
 Z := Sqrt(N);
 ZZ := Trunc (Z);
 X := 2 * ZZ + 1;
 Y := 1;
 R := Sqr (ZZ) - N;
 while (R <> 0) do
  begin
   R := R + X;
   X := X + 2;
   repeat
    R := R - Y;
    Y := Y + 2;
   until R <= 0;
  end;
 FermaFactorization := (X - Y) / 2;
end;
 
begin
 Writeln (FermaFactorization(917979909) : 0 : 0);
end.