Содержание

Вопрос или проблема
Ответ или решение
Программа для нахождения НОД двух чисел с использованием алгоритма Евклида
Алгоритм Евклида
Программный код
Описание программы
Результаты выполнения
Заключение

Вопрос или проблема

#include<stdio.h>
int gcd(int a, int b)
{
if(b==0) {
return a;
}
else {
return gcd(b, a%b) ;
}
}

int main() {
int num1, num2;
printf(“введите 1-е число:”) ;
scanf (“%d”,&num1) ;
printf(“введите 2-е число:”) ;
scanf (“%d”,&num2) ;
printf (“НОД %d и %d равен: %d\n” ,num1, num2, gcd(num1, num2) ) ;
return 0;
}

ваша программа содержит следующие ошибки, которые препятствуют компиляции версии gcc, поставляемой с Ubuntu:

include<stdio.h> не должен содержать вопросительный знак.
в нескольких местах у вас есть символы кавычек юникода вместо символа кавычек ascii. компилятор gcc не принимает символы юникода в исходном коде.

обычно считается “плохим тоном” публиковать исправленный исходный код программы, но в данном случае, поскольку ошибки были только в форматировании символов, кажется, что вреда нет 🙂

вот исправленная версия вашей программы:

#include <stdio.h> 
int gcd(int a, int b) 
{ 
  if(b==0) { return a; } else { return gcd(b, a%b) ; }
}

int main() 
{ 
  int num1, num2; 
  printf("введите 1-е число:") ; 
  scanf ("%d",&num1) ; 
  printf("введите 2-е число:") ; 
  scanf ("%d",&num2) ; 
  printf ("НОД %d и %d равен: %d\n" ,num1, num2, gcd(num1, num2) ) ; 
  return 0; 
}

и вот результат компиляции и выполнения программы:

user@user-DH61BE:~/Documents$ ls
GCD.c
user@user-DH61BE:~/Documents$ gcc GCD.c
user@user-DH61BE:~/Documents$ ls
a.out  GCD.c
user@user-DH61BE:~/Documents$ ./a.out
введите 1-е число:20
введите 2-е число:25
НОД 20 и 25 равен: 5
user@user-DH61BE:~/Documents$

Ответ или решение

Программа для нахождения НОД двух чисел с использованием алгоритма Евклида

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

Алгоритм Евклида

Алгоритм Евклида основан на следующем принципе: НОД двух чисел ( a ) и ( b ) равен НОД остатка от деления ( a ) на ( b ) и ( b ), то есть:

[
\text{gcd}(a, b) = \text{gcd}(b, a \mod b)
]

Когда ( b ) становится равным нулю, значение ( a ) является искомым НОД.

Программный код

Ниже приведен исправленный код программы на языке C, который вычисляет НОД двух целых чисел:

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

int main() {
    int num1, num2;
    printf("Введите 1-е число: ");
    scanf("%d", &num1);
    printf("Введите 2-е число: ");
    scanf("%d", &num2);
    printf("НОД чисел %d и %d составляет: %d\n", num1, num2, gcd(num1, num2));
    return 0;
}

Описание программы

Подключение библиотеки:
- #include <stdio.h> — это стандартная библиотека для ввода и вывода данных.
Функция gcd:
- Эта функция принимает два целых числа ( a ) и ( b ) в качестве параметров.
- Если ( b = 0 ), возвращаем ( a ) (это НОД).
- В противном случае рекурсивно вызываем функцию с параметрами ( b ) и ( a \mod b ).
Функция main:
- Объявляем переменные для хранения вводимых чисел.
- Используем printf и scanf для вывода сообщений и чтения чисел от пользователя.
- Вызов функции gcd для вычисления НОД и вывод результата на экран.

Результаты выполнения

После компиляции и запуска программы, вы сможете ввести два числовых значения. Например:

Введите 1-е число: 20
Введите 2-е число: 25
НОД чисел 20 и 25 составляет: 5

Таким образом, программа успешно вычисляет НОД, демонстрируя эффективность использования алгоритма Евклида в языке C.

Заключение

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