0 / 0 / 0
Регистрация: 05.02.2018
Сообщений: 20
1

Алгоритм Евклида для вычисления НОД

09.02.2018, 23:20. Показов 57963. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так: нужно заменять большее число на разность большего и меньшего до тех пор, пока одно из них не станет равно нулю; тогда второе и есть НОД. Напишите программу, которая реализует этот алгоритм.

Входные данные
Входная строка содержит два числа, разделённые пробелом – a и b .

Выходные данные
Программа должна вывести в одной строке два числа: сначала наибольший общий делитель двух введённых чисел, а затем – количество шагов цикла, которые были выполнены.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.02.2018, 23:20
Ответы с готовыми решениями:

Найти НОД 2-х многочленов, используя алгоритм Евклида
Алгоритм основан на том факте, что для любых двух многочленов от одного переменного, f(x) и g(x),...

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

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

Даны натуральные числа A и B. Найти их НОК, определив функцию для расчета НОД двух натуральных чисел, используя алгоритм Евклида
Даны натуральные числа A и B. Найти их наименьшее общее кратное, определив функцию для расчета...

1
1755 / 1347 / 1407
Регистрация: 28.10.2016
Сообщений: 4,267
10.02.2018, 01:59 2
Лучший ответ Сообщение было отмечено Pomogitemnepj как решение

Решение

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
var a, b, nod, k: integer;
begin
  readln(a, b);
  k := 0;
  while (a <> 0) and (b <> 0) do begin
    if a > b then a := a mod b
      else b := b mod a;
    k := k + 1;
  end;
  nod := a + b;
  writeln(nod, ' ', k);
end.
1
10.02.2018, 01:59
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.02.2018, 01:59
Помогаю со студенческими работами здесь

Найти НОД с помощью алгоритма Евклида
Написать пpогpаммы, включающие pекуpсивную и неpекуpсивную пpоцедуpы. 1. Даны натуpальные числа...

НОД по алгоритму Евклида, воспользовавшись следующей зависимостью
Найти наибольший общий делитель двух положительных целых чисел n и m по алгоритму Евклида,...

Найти наибольший общий делитель (НОД) двух натуральных чисел M и N по алгоритму Евклида
Найти наибольший общий делитель (НОД) двух натуральных чисел M и N по алгоритму Евклида. Если M &gt;...

Составить программу определения наибольшего общего делителя двух неотрицательных чисел НОД (a, b) по алгоритму Евклида.
Доброго времени суток. Есть такая вот задачка: Составить программу определения наибольшего...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru