Задача по СИ по нахождению НОД(наибольший общий делитель)



Задача: Заданы натуральные числа А и В. Составить программу для определения наибольшего общего делителя.

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

Решение:

Исходный код:

#include<stdio.h>

#include<conio.h>

main()

{

int A, B; /* Объявляем целочисленные переменные*/

scanf(«%d», &A); /* Вводим число с клавиатуры*/

scanf(«%d», &B); /* Вводим число с клавиатуры*/

printf(«A=%d, B=%d», A, B); /*Выводим на монитор введенное число*/

while (A!=0 && B!=0) /*Пока А и В не равняется нулю делать следующее*/

if (A>B) /*Если А больше В*/

A=A-B;

else /*Иначе*/

B=B-A;

if (A!=0)

printf («\nNOD=%d\n», A); /*Выводим на монитор полученную сумму*/

else

printf («\nNOD=%d\n», B); /*Выводим на монитор полученную сумму*/

getch(); /*Функция, чтобы при завершении программы результаты оставались на экране*/

return 0; /*Эта строка говорит о том, что программа завершилась корректна*/

}


Тестирование:

24 36

А=24, В=36

NOD 12

Комментариев нет »

Комментариев нет.

RSS-лента комментариев к этой записи. TrackBack URL

Оставить комментарий