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

@Pomogitemnepj · Регистрация: 05.02.2018

Author24 — интернет-сервис помощи студентам

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

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

Выходные данные
Программа должна вывести в одной строке два числа: сначала наибольший общий делитель двух введённых чисел, а затем – количество шагов цикла, которые были выполнены.

@Hitoku · 10.02.2018, 01:59

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.

Новые блоги и статьи Все статьи Все блоги /
Чем асинхронная логика (схемотехника) лучше тактируемой, как я думаю, что помимо энергоэффективности - ещё и безопасность. Hrethgir 14.05.2025 Помимо огромного плюса в энергоэффективности, асинхронная логика - тотальный контроль над каждым совершённым тактом, а значит - безусловная безопасность, где безконтрольно не совершится ни одного. . .	Многопоточные приложения на C++ bytestream 14.05.2025 C++ всегда был языком, тесно работающим с железом, и потому особеннно эффективным для многопоточного программирования. Стандарт C++11 произвёл революцию, добавив в язык нативную поддержку потоков,. . .	Stack, Queue и Hashtable в C# UnmanagedCoder 14.05.2025 Каждый опытный разработчик наверняка сталкивался с ситуацией, когда невинный на первый взгляд List<T> превращался в узкое горлышко всего приложения. Причина проста: универсальность – это прекрасно,. . .	Как использовать OAuth2 со Spring Security в Java Javaican 14.05.2025 Протокол OAuth2 часто путают с механизмами аутентификации, хотя по сути это протокол авторизации. Представьте, что вместо передачи ключей от всего дома вашему другу, который пришёл полить цветы, вы. . .	Анализ текста на Python с NLTK и Spacy AI_Generated 14.05.2025 NLTK, старожил в мире обработки естественного языка на Python, содержит богатейшую коллекцию алгоритмов и готовых моделей. Эта библиотека отлично подходит для образовательных целей и. . .
Реализация DI в PHP Jason-Webb 13.05.2025 Когда я начинал писать свой первый крупный PHP-проект, моя архитектура напоминала запутаный клубок спагетти. Классы создавали другие классы внутри себя, зависимости жостко прописывались в коде, а о. . .	Обработка изображений в реальном времени на C# с OpenCV stackOverflow 13.05.2025 Объединение библиотеки компьютерного зрения OpenCV с современным языком программирования C# создаёт симбиоз, который открывает доступ к впечатляющему набору возможностей. Ключевое преимущество этого. . .	POCO, ACE, Loki и другие продвинутые C++ библиотеки NullReferenced 13.05.2025 В C++ разработки существует такое обилие библиотек, что порой кажется, будто ты заблудился в дремучем лесу. И среди этого многообразия POCO (Portable Components) – как маяк для тех, кто ищет. . .	Паттерны проектирования GoF на C# UnmanagedCoder 13.05.2025 Вы наверняка сталкивались с ситуациями, когда код разрастается до неприличных размеров, а его поддержка становится настоящим испытанием. Именно в такие моменты на помощь приходят паттерны Gang of. . .	Создаем CLI приложение на Python с Prompt Toolkit py-thonny 13.05.2025 Современные командные интерфейсы давно перестали быть черно-белыми текстовыми программами, которые многие помнят по старым операционным системам. CLI сегодня – это мощные, интуитивные и даже. . .

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

	Алгоритм Евклида для вычисления НОД 09.02.2018, 23:20. Показов 60506. Ответов 1 Метки нет (Все метки) Алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так: нужно заменять большее число на разность большего и меньшего до тех пор, пока одно из них не станет равно нулю; тогда второе и есть НОД. Напишите программу, которая реализует этот алгоритм. Входные данные Входная строка содержит два числа, разделённые пробелом – a и b . Выходные данные Программа должна вывести в одной строке два числа: сначала наибольший общий делитель двух введённых чисел, а затем – количество шагов цикла, которые были выполнены. 0

Опции темы

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

Решение