Программирование на C | Расчет НОК | Рекурсия

Введение

В этом практическом занятии мы напишем программу на C для нахождения НОК (наименьшее общее кратное) двух чисел с использованием рекурсии. НОК - это наименьшее положительное целое число, которое делится на оба числа без остатка.

Разобраться в концепции НОК

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

НОК = (число1 * число2) / НОД

где число1 и число2 - это два числа, для которых мы должны найти НОК, а НОД - это наибольший общий делитель двух чисел.

Создать новый файл на C

Создадим новый файл на C под названием main.c в директории ~/project/, где напишем нашу программу.

Написать код

Скопируйте и вставьте следующий код в файл main.c.

#include<stdio.h>

int find_lcm(int, int); // объявление прототипа функции

int main()
{
    int a, b, lcm;
    printf("Введите два целых числа, чтобы найти НОК:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // вызов функции
    printf("НОК %d и %d равен %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // определение функции
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

Компилировать и запустить программу

Сохраните файл main.c и скомпилируйте программу с использованием следующей команды в терминале:

gcc main.c -o main

Запустите программу с использованием следующей команды:

./main

Введите два целых числа при запросе, и программа выведет НОК этих двух чисел.

Разобраться в коде

Разберём код, который мы только что написали.

Сначала мы включаем стандартную библиотеку ввода-вывода в нашу программу с использованием #include<stdio.h>.
Мы объявляем прототип функции find_lcm, которую мы определим позже в программе. Это необходимо, потому что мы вызываем функцию find_lcm в нашей основной функции перед её фактическим определением.
В основной функции мы объявляем три целочисленные переменные a, b и lcm.
Мы просим пользователя ввести два целых числа с использованием printf и принимаем ввод с использованием scanf.
Затем мы вызываем функцию find_lcm и передаём a и b в качестве её аргументов.
Функция find_lcm принимает два целочисленных аргумента a и b и возвращает НОК этих двух чисел с использованием рекурсии.
Мы инициализируем статическую переменную temp значением 1, которая будет хранить текущее значение, которое мы проверяем на кратность.
В каждой рекурсии мы проверяем, является ли temp кратным как a, так и b.
Если это кратное, мы возвращаем temp в качестве НОК.
Если это не кратное, мы увеличиваем temp и вызываем функцию find_lcm рекурсивно, пока не найдём НОК.

Тестировать программу

Протестируйте программу с разными значениями ввода и убедитесь, что она выводит правильный результат для НОК.

Полный код

Вот полный код на C для нахождения НОК двух чисел с использованием рекурсии:

#include<stdio.h>

int find_lcm(int, int); // объявление прототипа функции

int main()
{
    int a, b, lcm;
    printf("Введите два целых числа, чтобы найти НОК:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // вызов функции
    printf("НОК %d и %d равен %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // определение функции
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

Резюме

В этом практическом занятии мы научились писать программу на C для нахождения НОК двух чисел с использованием рекурсии. Мы использовали рекурсивную функцию для нахождения НОК и подробно объяснили каждый шаг программы. Мы также узнали, как компилировать и запускать программу на C с использованием терминала.

Рекурсивный расчет НОК на C