Запись вспомогательных алгоритмов на языках Си, Паскаль и Python

Хорошая программа собирается как конструктор: не из одной огромной детали, а из маленьких, которые можно использовать снова и снова. Такие детали — вспомогательные алгоритмы, в языках программирования их называют подпрограммами.

Урок разобран сразу для трёх языков. Над каждым примером кода есть вкладки: выбери свой язык, и сайт запомнит выбор.

Зачем нужны подпрограммы

Программа растёт, и через какое-то время в ней становится трудно разобраться. Если одно и то же действие нужно в нескольких местах, его хочется написать один раз и вызывать по имени. Для этого программу делят на части — подпрограммы.

Подпрограммы бывают двух видов:

• процедура выполняет действия — например, выводит что-то на экран;
• функция вычисляет и возвращает результат — число, строку и т. п., — который можно использовать в выражении.

	Си	Паскаль	Python
процедура	void имя(параметры) { … }	procedure имя(параметры); begin … end;	def имя(параметры): без return
функция	тип имя(параметры) { … return x; }	function имя(параметры): тип; begin … имя := x; end;	def имя(параметры): … return x
где описывается	до main (или прототип до main)	до begin основной программы	до первого вызова

Процедуры

Пример 1. Строки из одинаковых символов

Нужно вывести строки из семи единиц, из трёх пятёрок и из десяти звёздочек. Вместо трёх похожих циклов напишем одну процедуру с двумя параметрами: какой символ выводить и сколько раз.

#include <stdio.h>

void digit(char d, int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%c", d);
    printf("\n");
}

int main(void) {
    digit('1', 7);    // 1111111
    digit('5', 3);    // 555
    digit('*', 10);   // **********
    return 0;
}

program Lines;

procedure digit(d: char; n: integer);
var
  i: integer;
begin
  for i := 1 to n do
    write(d);
  writeln;
end;

begin
  digit('1', 7);    { 1111111 }
  digit('5', 3);    { 555 }
  digit('*', 10);   { ********** }
end.

def digit(d, n):
    print(d * n)

digit('1', 7)    # 1111111
digit('5', 3)    # 555
digit('*', 10)   # **********

Параметры d и n в описании процедуры — формальные: это места, куда при вызове подставятся значения. Значения в вызове ('1', 7) — фактические параметры. Захотели восемь единиц вместо семи — меняем одно число в вызове, а не код процедуры.

Локальные и глобальные переменные

Переменные, описанные внутри подпрограммы, — локальные: они существуют только пока подпрограмма работает, и снаружи их не видно. Переменные основной программы, доступные и подпрограмме, — глобальные.

• Си — глобальная переменная описывается вне всех функций, до них.
• Паскаль — глобальные переменные описываются в разделе var программы до описания процедуры.
• Python — чтобы подпрограмма могла изменить переменную основной программы, её объявляют словом global.

Пример 2. НОД нескольких чисел

Наибольший общий делитель двух чисел находит алгоритм Евклида: пока числа не равны, из большего вычитаем меньшее — оставшееся число и есть НОД. Процедура nod записывает результат в глобальную переменную x. Программа читает количество чисел k, потом сами числа и находит их общий НОД: НОД(a, b, c) = НОД(НОД(a, b), c).

#include <stdio.h>

int x;   // глобальная: её видит и процедура, и main

void nod(int a, int b) {
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
    x = a;
}

int main(void) {
    int k, i, y;
    printf("k=");
    scanf("%d", &k);
    scanf("%d", &x);
    for (i = 1; i < k; i++) {
        scanf("%d", &y);
        nod(x, y);
    }
    printf("НОД= %d\n", x);
    return 0;
}

program GCD;
var
  x, k, i, y: integer;   { x — глобальная }

procedure nod(a, b: integer);
begin
  while a <> b do
    if a > b then
      a := a - b
    else
      b := b - a;
  x := a;
end;

begin
  write('k=');
  readln(k);
  readln(x);
  for i := 1 to k - 1 do
  begin
    readln(y);
    nod(x, y);
  end;
  writeln('НОД= ', x);
end.

def nod(a, b):
    global x
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    x = a

k = int(input('k='))
x = int(input())
for i in range(1, k):
    y = int(input())
    nod(x, y)
print('НОД=', x)

Для чисел 12, 18 и 30: НОД(12, 18) = 6, затем НОД(6, 30) = 6. Ответ — 6.

Пример 3. Простые множители числа

Программа выводит все простые множители натурального числа a > 1. Процедура ppd находит наименьший делитель числа, больший 1 (он всегда простой), и выводит его. Основная программа делит число на этот делитель, пока не останется 1.

#include <stdio.h>

int d;   // глобальная: найденный делитель

void ppd(int n) {
    d = 2;
    while (n % d > 0)
        d = d + 1;
    printf("%d\n", d);
}

int main(void) {
    int a;
    printf("a=");
    scanf("%d", &a);
    while (a > 1) {
        ppd(a);
        a = a / d;
    }
    return 0;
}

program Factors;
var
  a, d: integer;   { d — глобальная }

procedure ppd(n: integer);
begin
  d := 2;
  while n mod d > 0 do
    d := d + 1;
  writeln(d);
end;

begin
  write('a=');
  readln(a);
  while a > 1 do
  begin
    ppd(a);
    a := a div d;
  end;
end.

def ppd(n):
    global d
    d = 2
    while n % d > 0:
        d = d + 1
    print(d)

a = int(input('a='))
while a > 1:
    ppd(a)
    a = a // d

Проверь на числах: 121 → 11, 11; 135 → 3, 3, 3, 5; 847 → 7, 11, 11.

Функции

Функция — подпрограмма, у которой есть результат. Его возвращают:

• в Си и Python — командой return: она сразу завершает функцию;
• в Паскале — присваиванием имени функции: имя := значение.

Вызов функции можно поставить в любое выражение: вывести, присвоить переменной, передать в другую функцию.

Пример 4. Наибольшее из четырёх чисел

Напишем функцию max2 — большее из двух чисел. Наибольшее из четырёх найдём как турнир: сначала пары, потом финал — max2(max2(a, b), max2(c, d)).

#include <stdio.h>

int max2(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

int main(void) {
    int a, b, c, d, f;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    f = max2(max2(a, b), max2(c, d));
    printf("f= %d\n", f);
    return 0;
}

program Max4;
var
  a, b, c, d, f: integer;

function max2(a, b: integer): integer;
begin
  if a > b then
    max2 := a
  else
    max2 := b;
end;

begin
  readln(a, b, c, d);
  f := max2(max2(a, b), max2(c, d));
  writeln('f= ', f);
end.

def max2(a, b):
    if a > b:
        return a
    else:
        return b

a, b, c, d = map(int, input().split())
f = max2(max2(a, b), max2(c, d))
print('f=', f)

Функцию назвали max2, а не max: в Python max — встроенная функция, и своя с тем же именем её бы перекрыла.

Попробуй изменить программу, чтобы найти: а) наибольшее из трёх чисел; б) наименьшее из четырёх; в) разность наибольшего и наименьшего из четырёх.

Рекурсия

Пример 5. Задача о кроликах

В январе подарили пару новорождённых кроликов. Через два месяца они дают первый приплод — новую пару, а дальше по паре каждый месяц. Каждая новая пара так же через два месяца начинает давать по паре в месяц. Сколько пар будет в декабре?

Обозначим через f(n) число пар в месяце с номером n. Тогда f(1) = 1, f(2) = 1, а дальше в каждом месяце к прошлым парам добавляется приплод от пар, которым уже два месяца: f(n) = f(n − 1) + f(n − 2). Получаются числа 1, 1, 2, 3, 5, 8, 13… — последовательность Фибоначчи, по имени итальянского математика, который разобрал эту задачу в начале XIII века.

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

#include <stdio.h>

int f(int n) {
    if (n == 1 || n == 2)
        return 1;
    return f(n - 1) + f(n - 2);
}

int main(void) {
    int i;
    for (i = 1; i <= 12; i++)
        printf("%d\n", f(i));
    return 0;
}

program Rabbits;
var
  i: integer;

function f(n: integer): integer;
begin
  if (n = 1) or (n = 2) then
    f := 1
  else
    f := f(n - 1) + f(n - 2);
end;

begin
  for i := 1 to 12 do
    writeln(f(i));
end.

def f(n):
    if n == 1 or n == 2:
        return 1
    return f(n - 1) + f(n - 2)

for i in range(1, 13):
    print(f(i))

Последнее число — 144: столько пар будет в декабре. У рекурсии обязательно должен быть выход — случай, когда функция отвечает сразу, без нового вызова (здесь n = 1 или n = 2). Без него функция вызывала бы себя бесконечно.

🎯 Самое главное

• Подпрограмма — вспомогательный алгоритм с именем, который вызывают из основной программы.
• Процедура выполняет действия, функция возвращает результат.
• Параметры передают подпрограмме данные: формальные — в описании, фактические — в вызове.
• Локальные переменные живут только внутри подпрограммы, глобальные — во всей программе; в Python для изменения глобальной переменной нужно global.
• Рекурсивная функция вызывает сама себя, и у неё должен быть случай выхода.

🤔 Проверь себя

1. Чем функция отличается от процедуры?

Функция возвращает результат, и её вызов можно подставить в выражение. Процедура только выполняет действия.

2. Что выведет вызов digit('#', 4)?

#### — четыре символа «#» в строку.

3. Как функция возвращает результат в Паскале? А в Си и Python?

В Паскале — присваиванием имени функции: max2 := a. В Си и Python — командой return.

4. Что будет, если у рекурсивной функции убрать случай выхода?

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

Дальше — массивы: как хранить и обрабатывать много однотипных значений.