7.2. Некоторые сведения о языке программирования Pascal

Блок описания действий начинается со слова begin, а заканчивается словом end и знаком точки. Действия представляются операторами (табл. 2.4). Операторы языка Pascal разделяются точкой с запятой. Операторы бывают простые и составные (заключённые в операторные скобки begin ... end).

Основные операторы языка Pascal

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

Самый простой путь решения этой задачи — проверить, имеет ли данное число n (n >= 2) делители в интервале [2; n - 1].

Если делители есть, число n — составное, если — нет, то — простое.

В программе будем использовать логическую переменную flag:

если flag = true, то n — простое число;
если flag = false, то n — составное число (если у числа n есть делители, то «флаг выключаем» с помощью оператора присваивания flag := false).

В этой программе мы проверяли, нет ли у числа п делителей из интервала [2; n - 1]. Но если n = а • b, то меньшее из чисел а, b не больше √n (в противном случае оба числа были бы больше √n, а следовательно, их произведение было бы больше n). Кроме того, из делимости числа n на а автоматически следует, что n делится и на n/а.

Усовершенствуйте приведённую выше программу с учётом этих соображений.

Проверку, является ли заданное натуральное число n >= 2 простым, мы осуществили методом перебора всех возможных его делителей. Метод перебора используется для решения достаточно широкого круга задач.

Пример 2.

Применим метод перебора для поиска наибольшего общего делителя (НОД) двух натуральных чисел а и b.

Начнём перебор с d — наименьшего из чисел а и b. Это первый, очевидный кандидат на роль их наибольшего общего делителя. И далее, пока не найдём d, на которое оба числа делятся нацело, будем уменьшать его на единицу. Как только такое деление произойдёт, останавливаем уменьшение d. Полученное значение d и будет наибольшим общим делителем чисел а и b.

<<< К началу