Для составления блок-схемы и математической модели алгоритма нахождения наибольшего общего делителя (НОД) двух чисел можно использовать алгоритм Евклида. 14

Блок-схема алгоритма: 4

1. Определиться со значением первого числа X. 4
2. Определиться со значением второго числа Y. 4
3. Если X≠Y, то выполнять пункт 4, иначе перейти к пункту 5. 4
4. Если X>Y, то заменить X на X-Y и перейти к пункту 3, иначе заменить Y на Y- X и перейти к пункту 3. 4
5. Считать Х наименьшим общим делителем. 4

Математическая модель алгоритма Евклида «с вычитанием» может быть представлена в виде цепочки утверждений: 3

• Все общие делители пары a и b являются также общими делителями пары a — b, b. 3
• И наоборот, все общие делители пары a — b и b являются также общими делителями пары a и b. 3
• НОД(A, B) = НОД(A — B, B), если A > B. 3
• НОД(A, 0) = A. 3

Также для записи алгоритма Евклида на языке программирования, например Паскаль, необходимо строго придерживаться структуры программы. 4