Программа которая ищет нод

Постановка задачи. Дано два целых положительных числа x и y. Наибольшее число, на которое делятся оба числа без остатка, называют наибольшим общим делителем (НОД). Наверно, это вам известно из школьного курса математики. Зачем он нужен? Например, для упрощения дробей: 26/39=2/3, т.к. НОД(x,y)=13.

Или для нахождения простых чисел, которые используются в алгоритмах защиты информации.

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

Реализация. Придерживаясь принципа проектирования «сверху-вниз», объявим в классе Program метод static int НОД(int x, int y), а ввод и вывод результата выполним в Main(). Тогда:

#37. Алгоритм Евклида для нахождения НОД | Python для начинающих

// Нахождение наибольшего общего делителя (НОД) двух целых чисел // Алгоритм Евклида, 300 год до н. э. — Функция НОД(x,y) using System; namespace НаибольшийОбщийДелитель < class Program < static void Main(string[] args) < int x, y; Console.Write(«x= «); x = Convert.ToInt32(Console.ReadLine()); Console.Write(«y= «); y = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(«НОД = «,НОД(x,y)); Console.ReadKey(); > // Функция НОД(x,y) static int НОД(int x, int y) < while (x != y) < if (x >y) x = x — y; else y = y — x; > return x; > > >

Замечание. При разработке алгоритмов решения массовых (часто выполняющихся при различных исходных данных) задач имеет значение их эффективность. Под этим понимаются время выполнения и объем требуемой памяти. С этой точки зрения алгоритм Евклида является образцом для программиста.

Далее планируется дополнять этот раздел новыми примерами, в том числе предложенными вами

Вам предлагаются задачи для самостоятельного решения с использованием навыков, приобретаемых при творческом освоении основ языка C#.

NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.

Источник: c-sharp.pro

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

Ал­го­ритм Ев­кли­да — эф­фек­тив­ный ме­тод вы­чис­ле­ния наи­боль­ше­го об­ще­го де­ли­те­ля (НОД). На­зван в честь гре­че­ско­го ма­те­ма­ти­ка Ев­кли­да. Из­ло­жим схе­му ал­го­рит­ма в тек­сто­вом ви­де:

Пишем программу: нахождения НОД и НОК двух чисел | Алгоритм Евклида

1. Боль­шее чис­ло де­лим на мень­шее;
2. Ес­ли де­лит­ся без остат­ка, то мень­шее чис­ло и есть НОД. За­вер­ша­ем про­грам­му и вы­во­дим ре­зуль­тат;
3. Ес­ли есть оста­ток, то боль­шее за­ме­ня­ем на оста­ток от де­ле­ния;
4. Пе­ре­хо­дим к пунк­ту 1;

Код про­грам­мы мож­но ре­дак­ти­ро­вать. Вы мо­же­те впи­сать свои чис­ла а и b .

a = 50 b = 130 while a!=0 and b!=0: if a > b: a = a % b else: b = b % a print (a+b)

Ал­го­ритм от­но­сит­ся к чис­лу клас­си­че­ских.

Источник: qaweb.dev

Программа НОК и НОД — Паскаль

Здесь приведен код программы на языке Паскаль. Программа вычисляет НОД и НОК с использованием алгоритма Евклида. Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. Приведем пример: для чисел 70 и 105 наибольший общий делитель будет равен 35. НОД существует и однозначно определён, если хотя бы одно из чисел m или n не ноль. Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n. Например, для 3 и 5, НОК равен 15, а для 2 и 4 НОК равен 4.

program nodnok; var a,b:longint; function NOD(x,y:longint):longint; begin if x<>0 then NOD:= NOD(y mod x,x) else NOD:= y; end; function NOK(x,y:longint):longint; begin NOK:= (x div NOD(x,y)) * y; end; Begin Write(‘Введите a и b: ‘); Readln(a,b); Writeln(‘НОД ‘,a,’ и ‘,b,’ = ‘, NOD(a,b)); Writeln(‘НОК ‘,a,’ и ‘,b,’ = ‘, NOK(a,b)); Readln; End.

Источник: upbyte.net