Вычисление НОД при помощи бинарного алгоритма - 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(); }
Объяснение кода листинга программы
- Включаем необходимые заголовочные файлы
- Объявляем функцию main()
- Выводим название и номер задачи
- Объявляем переменные m, n, temp и инициализируем их значениями 0
- Выводим сообщение о том, что будет вычислен НОД при помощи бинарного алгоритма
- Запрашиваем у пользователя ввод двух целых чисел, используя функцию scanf()
- Выводим сообщение о том, что введенные числа равны
- Запускаем цикл while, который будет выполняться до тех пор, пока m не станет равным n
- Внутри цикла проверяем, являются ли оба числа четными и если да, то делим их на 2
- Если только одно из чисел четное, то необходимо перенести его в переменную temp и затем в переменную m или n в зависимости от того, какое число больше
- Если оба числа нечетные, то необходимо перенести большее число в переменную temp, а затем в переменную m или n в зависимости от того, какое число больше
- После выхода из цикла while, выводим значение переменной n
- Завершаем программу при помощи функции getch()
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д