Вычисление НОД при помощи бинарного алгоритма - C (СИ)

Узнай цену своей работы

Формулировка задачи:

задание такое: необходимо посчитать НОД по бинарному алгоритму. Алгоритм такой: 1.Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2); 2.Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n); 3.Если n чётное, m нечётное, то НОД(m, n) = НОД(m, |m-n|); 4.Если m, n нечётные, то НОД(m, n) = НОД(n, |m - n|). пример (1173,323)=(323,850)=(323,425)=(323,102)=…=(51,17)=(17,34)=(17,17)=17 я попыалась написать код, правда без цикла (так как не понимаю как его сделать), но совсем не уверена в его правильности
#include <stdio.h>
#include <conio.h>
void main ()
{
    printf ("\n\n Laboratornaya rabota 2");
    printf ("\n\n Zadanie 2");
    printf ("\n Vichislit NOD (m,n) po binarnomy algoritmy ");
    int m, n;
    int a,b;
    printf ("\n\n vichislim NOD");
    printf (" dlya dvuh celih chisel m i n. \n");
    printf ("\n vvedite v odnoj stroke dva celih chisla");
    printf (" i nazhmite <enter>");
    printf ("->");
    scanf ("%i%i", &m, &n);
    printf ("\n NOD chisel %i i %i - raven ", m, n);
    
    if ((m%2==0)&&(n%2==0))    
    {
    a=m/2;
    b=n/2;
    }    
    else if ((m%2==0)&&(n%2>0))
    {
    a=m/2;
    b=n;
    }
    else if ((m%2>0)&&(n%2==0))
    {
    a=n;
    if (n>m)
        b=n-m;
        else 
        b=m-n;
    }
    else if ((m%2>0)&&(n%2>0))
    {
        if (n>m)
        a=n-m;
        else 
        a=m-n;
               b=m;
    }
printf ("%i\n", a);
    getch();
}

Решение задачи: «Вычисление НОД при помощи бинарного алгоритма»

textual
Листинг программы
#include<iostream>
#include <stdio.h>
#include <conio.h>
void main ()
{
printf ("\n\n Laboratornaya rabota 2");
printf ("\n\n Zadanie 2");
printf ("\n Vichislit NOD (m,n) po binarnomy algoritmy ");
int m, n, temp;
printf ("\n\n vichislim NOD");
printf (" dlya dvuh celih chisel m i n. \n");
printf ("\n vvedite v odnoj stroke dva celih chisla");
printf (" i nazhmite <enter>");
printf ("->");
scanf ("%i%i", &m, &n);
printf ("\n NOD chisel %i i %i - raven ", m, n);
while(m!=n)
{
if ((m%2==0)&&(n%2==0)) 
{
m=m/2;
n=n/2;
} 
else if ((m%2==0)&&(n%2>0))
{
m=m/2;
}
else if ((m%2>0)&&(n%2==0))
{
if (n>m)
n=n-m;
else 
n=m-n;
}
else if ((m%2>0)&&(n%2>0))
{
temp=n;
if (n>m)
n=n-m;
else 
n=m-n;
m=temp;
}
}
printf ("%i\n", n);
getch();
}

Объяснение кода листинга программы

  1. Включаем необходимые заголовочные файлы
  2. Объявляем функцию main()
  3. Выводим название и номер задачи
  4. Объявляем переменные m, n, temp и инициализируем их значениями 0
  5. Выводим сообщение о том, что будет вычислен НОД при помощи бинарного алгоритма
  6. Запрашиваем у пользователя ввод двух целых чисел, используя функцию scanf()
  7. Выводим сообщение о том, что введенные числа равны
  8. Запускаем цикл while, который будет выполняться до тех пор, пока m не станет равным n
  9. Внутри цикла проверяем, являются ли оба числа четными и если да, то делим их на 2
  10. Если только одно из чисел четное, то необходимо перенести его в переменную temp и затем в переменную m или n в зависимости от того, какое число больше
  11. Если оба числа нечетные, то необходимо перенести большее число в переменную temp, а затем в переменную m или n в зависимости от того, какое число больше
  12. После выхода из цикла while, выводим значение переменной n
  13. Завершаем программу при помощи функции getch()

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 4 из 5
Похожие ответы