Основы программирования

         

вычисление наибольшего общего делителя


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

int gcd(int x, int y);

(gcd - от слов greatest common divizor). Основная функция main лишь вводит исходные данные, вызывает функцию gcd и печатает ответ. Описание прототипа функции gcd располагается в начале текста программы, затем следует функция main и конце - реализация функции gcd. Приведем полный текст программы:

#include <stdio.h> // Описания стандартного ввода-вывода

int gcd(int x, int y); // Описание прототипа функции

int main() { int x, y, d; printf("Введите два числа:\n"); scanf("%d%d", &x, &y); d = gcd(x, y); printf("НОД = %d\n", d); return 0; }

int gcd(int x, int y) { // Реализация функции gcd while (y != 0) { // Инвариант: НОД(x, y) не меняется int r = x % y; // Заменяем пару (x, y) на x = y; // пару (y, r), где r -- y = r; // остаток от деления x на y } // Утверждение: y == 0 return x; // НОД(x, 0) = x }

Стоит отметить, что реализация функции gcd располагается в конце текста программы. Можно было бы расположить реализацию функции в начале текста и при этом сэкономить на описании прототипа. Это, однако, дурной стиль! Лучше всегда, не задумываясь, описывать прототипы всех функций в начале текста, ведь функции могут вызывать друг друга, и правильно упорядочить их (чтобы вызываемая функция была реализована раньше вызывающей) во многих случаях невозможно. К тому же предпочтительнее, чтобы основная функция main, с которой начинается выполнение программы, была бы реализована раньше функций, которые из нее вызываются. Это соответствует технологии "сверху вниз" разработки программы: основная задача решается сразу на первом шаге путем сведения ее к одной или нескольким вспомогательным задачам, которые решаются на следующих шагах.



Содержание раздела