Согласие на обработку персональных данных.

26.05.2018
Новые видео и статья Как изменить дизайн сайта на Wordpress.

21.05.2018
Новый подраздел Wordpress.

20.05.2018
Новые видео и статья Процедура Rewrite.

15.05.2018
Новая задача Как заменить цифру в числе.

13.05.2018
Новые видео и статья Процедура Reset.



Раздел: Задачи / Простейшие /

Наибольший общий делитель двух натуральных чисел

Условие задачи 2.24

Задача 2.24
Даны два натуральных числа X и Y. Найдите наибольший общий делитель этих чисел и выведите на экран значение наибольшего общего делителя.

Эта простая задачка очень часто встречается в учебниках по программированию, поэтому я решил её рассмотреть. Если кто забыл, что такое натуральные числа, то см. здесь.

Также напомню, что такое наибольший общий делитель (сокращённо - НОД).

Наибольшим общим делителем двух чисел X и Y называется наибольшее число Z, на которое делятся без остатка оба числа X и Y.

Понятно, что для решения задачи нам нужен какой-то хитрый способ (алгоритм). Вот с него и начнём.

Алгоритм Евклида для нахождения НОД

Евклид (или Эвклид) - это древнегреческий математик, который жил примерно в 300 году до нашей эры. Сведений об Евклиде дошло до наших дней немного, но кое что всё-таки мы знаем.

Алгоритм Евклида - это один из самых древних и самых известных алгоритмов для вычисления наибольшего общего делителя двух целых чисел (или общей меры двух отрезков - вся математика зародилась из жизненной необходимости).

Этот алгоритм имеет множество практических и теоретических применений. Заключается он в следующем:

  1. Есть пара чисел.
  2. Отнимаем от большего числа меньшее, и получаем новую пару: меньшее число и разность между большим и меньшим.
  3. Повторяем до тех пор, пока числа в паре не будут равны. Это и будет наибольший общий делитель.
  4. Равенство рано или поздно будет в любом случае, так как любое натуральное число делится без остатка на 1.

Теперь попробуем использовать алгоритм нахождения наибольшего общего делителя на каких-то определённых числах. Допустим, у нас есть числа 32 и 12. Тогда:

1) 32 - 12 = 20 (новая пара чисел 12 и 20)
2) 20 - 12 = 8 (новая пара чисел 12 и 8)
3) 12 - 8 = 4 (новая пара чисел 8 и 4)
4) 8 - 4 = 4 (новая пара чисел 4 и 4 - числа равны, следовательно, 4 - это НОД чисел 32 и 12)

Теперь осталось только составить программу нахождения наибольшего общего делителя. Сделаем это, как обычно, на Паскале и С++. Решим эту задачу с помощью цикла.

Решение задачи 2.24 на Паскале
 

program mytask;

//****************************************************************
// ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
//****************************************************************
var
  X   : Integer;
  Y   : Integer;

//****************************************************************
// ПОДПРОГРАММЫ
//****************************************************************
function Evklid(n1, n2 : Integer) : Integer;
begin
  while n1 <> n2 do
    begin
      if n1 > n2 then n1 := n1 - n2
      else n2 := n2 - n1;
    end;
  Result := n1;
end;

//****************************************************************
// ОСНОВНАЯ ПРОГРАММА
//****************************************************************
begin
  Write('X = '); ReadLn(X);
  Write('Y = '); ReadLn(Y);

  //На тот случай, если пользователь ввёл отрицательные числа
  X := Abs(X);
  Y := Abs(Y);

  WriteLn('NOD = ', Evklid(X, Y));

  WriteLn('The end. Press ENTER...');
  ReadLn;
end.     
Решение задачи 2.24 на С++
#include <cstdlib>
#include <iostream>
#include <cmath>      //Для функции fabs

using namespace std;

//****************************************************************
// ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
//****************************************************************
signed int X;
signed int Y;

//****************************************************************
// ПОДПРОГРАММЫ
//****************************************************************
signed int Evklid(signed int n1, signed int n2)
{
  while (n1 != n2)
    {
      if (n1 > n2) n1 = n1 - n2;
      else n2 = n2 - n1;
    }
  return(n1);
}  

//****************************************************************
// ОСНОВНАЯ ПРОГРАММА
//****************************************************************
int main(int argc, char *argv[])
{
  cout << "X = "; cin >> X; 
  cout << "Y = "; cin >> Y; 
  
  //На тот случай, если пользователь ввёл отрицательные числа
  X = abs(X);
  Y = abs(Y); 
  
  cout << "NOD = " << Evklid(X, Y) << endl;   
  
  system("PAUSE");
  return EXIT_SUCCESS;
}

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


Основы C++ Основы C++

C++ - это один из самых популярных языков программирования. Не важно, на каком языке программируете лично вы. Но, если вы хотя бы в общих чертах не знаете С++, то это большой пробел в вашем образовании, который надо восполнить как можно быстрее... Подробнее...
Инфо-МАСТЕР ®
Все права защищены ©
e-mail: mail@info-master.su

Яндекс.Метрика