Описание функций
    Функции, как и процедуры, используются для структурирования программ. В некоторых языках вообще нет разделения подпрограмм на процедуры и функции. В Паскале такое разделение есть, но носит оно преимущественно синтаксический характер. Заголовок функции начинается с ключевого слова Function и кончается типом возвращаемого данной функцией значения.

Function <имя функции>
            [(<список параметров>)]:<тип результата>;

    В теле функции обязательно должен быть хотя бы один оператор присваивания, где в левой части стоит имя функции, а в правой — ее значение. Иначе значение функции не будет определено.

Несколько фактов из комбинаторики

Перестановки
    Перестановкой из n элементов назовем упорядоченный набор из n различных натуральных чисел, принадлежащих отрезку от 1 до n. Пусть n равно 3. Перечислим все перестановки из 3 элементов: (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2), (3 2 1). Количество перестановок из n элементов (обозначается как P(n)) равно n! = 1•2•...•n (факториалу числа n). Действительно, есть n способов для выбора элемента на первое место, (n—1) способ для выбора элемента на второе место и т.д. Общее количество способов — это произведение n•(n—1)•(n—2)•...•2•1.
    Перечислите все перестановки из 4 элементов. Количество перестановок — 24. Подсчитайте вручную значения n! для n из диапазона от 5 до 12.

Размещения с повторениями
   Пусть имеется множество элементов, относящихся к n различным видам. Из них составляются всевозможные наборы по m элементов в каждом. При этом в наборы могут входить и элементы одного вида. Два набора считаются различными, если они отличаются друг от друга или входящими в них элементами, или их порядком. Пусть n = 3, m = 2 (как обычно, рассматриваем натуральные числа). Размещения с повторениями: (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3). Число таких наборов R(n, m) = n^m . Это доказывается методом математической индукции.
    Перечислите все размещения с повторениями при n = 4 и m = 2. Подсчитайте вручную значение R(n, m) для нескольких значений n и m.

Размещения без повторений
   Размещением без повторений из n элементов по m называется упорядоченный набор из m различных чисел, принадлежащих отрезку от 1 до n. Два набора считаются различными, если они отличаются составом или порядком элементов. Пусть n = 4, m = 2. Перечислим все размещения без повторений: (1, 2), (2, 1), (1, 3), (3, 1), (1, 4), (4, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3). Количество размещений A(n, m) вычисляется по формуле:
        A(n, m) = n•(n — 1)•…•(n — m + 1) или
        A(n, m) = n! / (n-m)!.

    Перечислите все размещения из 5 элементов по 2. Подсчитайте вручную значения A(n, m) для фиксированного значения m, например 4, и n из интервала от 8 до 13.

Сочетания
   Сочетанием из n элементов по m называется набор из m различных чисел, выбранных из диапазона от 1 до n. Наборы различаются лишь составом элементов, порядок элементов роли не играет. Пусть n = 5, m = 3. Перечислим все сочетания: (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5). Каждому сочетанию соответствует m! размещений. Обозначим число сочетаний C(n, m). Таким образом,
        A(n, m) = C(n, m)•m! или
        C(n, m) = A(n, m) / m! = n! / m!(n - m)!.
    Перечислите все сочетания из 7 элементов по 5. Подсчитайте число сочетаний для различных значений n и m (не очень больших). При подсчете как числа сочетаний, так и числа размещений используется операция деления. Обоснуйте, почему в результате получаются только целые числа.

Экспериментальный раздел занятия

    1. Составить программу подсчета числа сочетаний — C(n, m). Пусть у нас есть функция подсчета факториала числа — Fact(n). Написание основной программы сводится к программированию формулы
        C(n, m) = n! / m!(n - m)!.

Program My12_1;
 Var n,m: Integer;
        c: Longint;
 Function Fact(n:Integer):Longint;
    Begin
    End;
Begin
    WriteLn('Введите n и m :');
    ReadLn(n,m);
    c:=Fact(n) / (Fact(m) * Fact(n-m));
    WriteLn(c);
    Readln
End.

При компиляции этой программы (функцию Fact мы пока не написали, но компилироваться программа должна и без нее) в строке
        c:=Fact(n) / (Fact(m) * Fact(n-m));
возникает ошибка — Error 26: Type mismatch. — несоответствие типов. Вспомним, что типы данных определяют не только диапазон значений переменных, но и допустимые над этим типом операции. Результат операции деления “/” нельзя присваивать переменным целого типа. Необходимо использовать операцию Div, т.е. соответствующая строка должна выглядеть следующим образом:
        c:=Fact(n) Div (Fact(m) * Fact(n-m));

    Дополняем программу.

Function Fact(n:Integer):Longint;
    Var i: Integer;
    rez: Longint;
    Begin
        rez:=1;
        For i:=1 To n Do rez:=rez*i;
        Fact:=rez
    End;

    Запускаем программу для различных значений n и m. При n = 10, m = 5 результат 252 не вызывает сомнений. При n = 13, m = 5 результат 399, что-то не так... должно получиться большее значение. При n = 15, m = 7 результат 9, теперь уже видно, что программа не работает. Объясните причину. Подсказка содержится в материале этого занятия.
    А можно ли упростить программу? Попробуйте убрать переменную c.
    Сколько лишних вычислений (умножений) делает наша программа? Подсчитаем
C(13, 5) = (1•2•3•4•5•6•7•8•9•10•11•12•13) : ((1•2•3•4•5)•(1•2•3•4•5•6•7•8)).
    Вычисляя значение С(13, 5) вручную, мы, конечно, не будем выполнять все эти умножения. Достаточно вычислить 9•11•13 = 1287. Напишите более эффективную функцию вычисления числа сочетаний. Например, даже нижеприведенный вариант программы даст более обнадеживающие результаты. Правильный результат при C(13, 5), а именно 1287, уже шаг вперед, но это не предел улучшений программы.

Program My12_1m;
    Var n,m:Integer;
    Function S(n,m:Integer):LongInt;
        Var i:Integer;
               rez,cht:LongInt;
        Begin
            rez:=1;cht:=1;
            For i:=1 To m Do Begin
                                            rez:=rez*i;
                                            cht:=cht*(n-i+1)
                                        end;
            S:=cht Div rez
        End;
        Begin
            WriteLn('Введите два числа: ');
            ReadLn(n,m);
            WriteLn(S(n,m));
            ReadLn
        End.

    На восьмом занятии мы познакомились с основной теоремой арифметики. Пусть нам не требуется вычислять C(n, m), а необходимо представить это значение в виде p₁^a1 p₂^a2 - p_g^ag, где a_i ³ 0, а p_i — простые числа. Ограничения: 1 < n £ 100, 1 < m < n. Вычислять “в лоб” — безнадежное занятие. Числа получаются огромные. Рассмотрим идею решения на примере. Вычисляем C(8, 5) = 8! / (5!•3!). Представим 8! как единицы в соответствующем массиве, например, с именем Sn, Sn[i] = 1, если число i есть в произведении. Просматриваем массив Sn, выбираем очередной элемент. Если число i составное, то находим его разложение на простые сомножители. К элементам Sn, соответствующим сомножителям, прибавляем количество единиц, равное числу их вхождений в i, а Sn[i] обнуляем. Выполним эти действия для n!, m! и (n—m)!. После этого останется только провести вычитание степеней одного и того же простого числа.

Итак, C(8, 5) = 2³•7¹.

Program My12_2;
    Const Q=100;
    Type MyArray=Array[1..Q] Of Integer;
    Var n,m:Integer;
           P:MyArray;
    Procedure Solve(sn,sm:Integer; Var Sp:MyArray);
    Begin
    End;
    Procedure Print(pn:Integer;Pp:MyArray);
        Var i:Integer;
        Begin
            For i:=2 To pn Do
                If Pp[i]<>0 Then WriteLn(i:5,Pp[i]:5)
        End;
    Begin
        WriteLn('Ввод чисел n и m');
        ReadLn(n,m);
        Solve(n,m,P);
        Print(n,P);
        ReadLn
    End.

    Пока у нас есть только основная программа, содержащая вызовы процедур, и простая процедура Print. Программа компилируется. Уточним процедуру Solve.

Procedure Solve(sn,sm:Integer; Var Sp:MyArray);
    Var i:Integer;
           Sni,Smi,Snmi:MyArray;
Begin
    Calc(sn,Sni);
    {Сформировали массив, соответствующий n!}
    Calc(sm,Smi);
    {Сформировали массив, соответствующий m!}
    Calc(sn-sm,Snmi);
    {Сформировали массив, соответствующий (n-m)!}
    For i:=2 To sn Do Sp[i]:=Sni[i]-Smi[i]-Snmi[i]
End;

    Сделав “заглушку” из процедуры Calc, содержащую только Begin и End, вы получите компилируемую программу. Вариант процедуры Calc, приведенный ниже, хотя и работает, но не очень хорошо читается. Выполните трассировку этой процедуры в режиме отладки, определите назначение каждого оператора. Ваша задача — улучшить процедуру. Вспомните о том, что в материале восьмого занятия перечислены все простые числа до 100.

Procedure Calc (n:Integer; Var X:MyArray);
    Var i,j,t:Integer;
    Begin
        FillChar(X,SizeOf(X),0);
        {SizeOf – вычисляет размер области памяти, выделенной для массива X; FillChar записывает нулевые значения в эту область памяти.}
        For i:=1 To n Do X[i]:=1;
        {Признаки чисел, задействованных в вычислении факториала числа.}
        For i:=4 To n Do Begin
            t:=i;
            j:=2;
        While (j<=(t div 2)) Do
            If t Mod j=0 Then Begin
            {j делит t без остатка.}
                Inc(X[j]); t:=t div j
                If t=j Then Inc(X[j])
            End
            Else Inc(j);
        If t<>i Then Begin
        {Найдены делители числа i.}
            X[i]:=0;If (t<>j) Then Inc(X[t])
        End
    End
End;

    Попробуем запустить эту программу при больших значениях n. Пусть n £ 10 000. Даже если изменить тип Integer на LongInt, появится ошибка Error 202: Stack oferflow error. Нам не хватает оперативной памяти для хранения данных программы. Действительно, массивов введено много. Попробуем обойтись одним глобальным массивом.

{$R+}
Program My12_2m;
    Const Q=10000;
    Type MyArray=Array[1..Q] Of Integer;
    Var n,m:LongInt;
           P:MyArray;
    Procedure Inc_0(n:LongInt);
        Var i,j,t:Integer;
        Begin
        For i:=2 To n Do Begin
            t:=i; j:=2;
            While (j<=(t div 2)) Do
                If t Mod j=0 Then Begin
                                                Inc(P[j]);
                                                t:=t div j;
                                                If t=j Then Inc(P[j])
                                             End
                Else Inc(j);
                If t<>i Then Begin
                                      If (t<>j) Then Inc(P[t])
                                   End
                Else P[i]:=1
        End
    End;
    Procedure Dec_0(n:LongInt);
        Var i,j,t:Integer;
        Begin
            For i:=2 To n Do Begin
                t:=i; j:=2;
                While (j<=(t Div 2)) Do
                If t Mod j=0 Then Begin
                                                Dec(P[j]);
                                                t:=t div j;
                                                If t=j Then Dec(P[j])
                                             End
                    Else Inc(j);
                If t<>i Then Begin
                                      If (t<>j) Then Dec(P[t])
                                   End
                Else Dec(P[i])
        End
    End;
Begin
    WriteLn('Ввод чисел n и m'); ReadLn(n,m);
    Inc_0(n);
    Dec_0(m)
    Dec_0(n-m)
End.

Мы видим, что код процедур Inc_0 и Dec_0 почти повторяется. Это плохо. Попробуйте написать программу изящнее. Кстати, значение константы Q можно увеличить, например, до 30 000. Учтите, что для больших значений n и m программа может работать довольно долго.
    2. В задании № 11 седьмого занятия требовалось определить, является ли введенное число палиндромом.
    Оформим “перевертывание” числа в виде функции.

Function Pal(n:LongInt):LongInt;
    Var x:LongInt;
    Begin
        x:=0;
        While n<>0 Do Begin
            x:=x*10+n Mod 10;
            n:=n Div 10
        End;
        Pal:=x
    End;

    Пусть n = 59. “Перевернем” его, получим 95. Найдем сумму чисел 59 и 95, получим 154. “Перевернем” это число, получим 451. Находим сумму: 605. Еще раз: 605 + 506 = 1111. Получили палиндром. Найдите для всех натуральных чисел из интервала от 50 до 80 количество шагов, необходимых для “сведения” их к палиндромам, с помощью описанной схемы.

Program My12_3;
    Const a=50;b=80;
    Var n,t:LongInt;
           cnt,i:Integer;
    Function Pal(n:LongInt):LongInt;
    Begin
    …
    End;
    Begin
        For i:=a To b Do Begin
            cnt:=0;n:=i;
            While Pal(n)<>n Do Begin
                t:=Pal(n); n:=n+t;
                Write(t,' ',n,' ');
                Inc(cnt)
            End;
        WriteLn(i,' ',cnt)
    End
End.

    Попробуйте получить палиндром из числа 89. На 16-м шаге результат по-прежнему не является палиндромом, а сумма выходит за пределы типа LongInt. Изменим программу, используя четвертый пример из раздела экспериментальной работы десятого занятия. Повторите материал о работе с большими числами. Для решения этой задачи потребуется их складывать и “перевертывать”.

{$R+}
Program My12_3m;
    Uses Crt;
    Const MaxN=1000;
    Type MyArray=Array[0..MaxN+1] Of Integer;
    {Числа храним в массиве, они большие и типа LongInt не хватает.}
    Var A,Z:MyArray;
           cnt,n:Integer;
    Function Eq:Boolean;
    {Является ли число палиндромом?}
     Var i:Integer;
     Begin
        i:=1;
        While (i<=A[0] div 2) And (A[i]=A[A[0]-i+1]) Do Inc(i);
        Eq:=(i>A[0] div 2)
     End;
    Procedure Swap(Var a,b:Integer);
        Var c:Integer;
        Begin c:=a;a:=b;b:=c End;
    Procedure Rev;{ "Перевертываем" число.}
        Var i:Integer;
        Begin
           For i:=1 To A[0] Div 2 Do Swap(A[i],A[A[0]-i+1])
        End;
    Procedure Change(n:Integer);
    {Записываем число в массив.}
        Var i:Integer;
        Begin
            i:=1;
            While n<>0 Do Begin
                A[i]:=n Mod 10; n:=n Div 10;
                Inc(A[0]);Inc(i)
            End
        End;
    Procedure Add;
    {Складываем два больших числа.}
        Var i,r,w:Integer;
        Begin
            i:=1;r:=0;
            While (i<=A[0]) Or (r<>0) Do Begin
                w:=A[i]+Z[i]+r; A[i]:=w Mod 10;
                r:= w Div 10;
                If A[A[0]+1]<>0 Then Inc(A[0]);
                Inc(i)
            End
        End;
    Begin
        ClrScr; n:=100;
        While (n<1000) Do Begin
        {Исследуем диапазон от 100 до 999.}
            FillChar(A,SizeOf(A),0);
            Change(n);{Преобразуем число.}
            cnt:=0;
            {Счетчик количества шагов – преобразований числа.}
            While (Not Eq) And (A[0]<=MaxN) Do Begin
            {Пока не палиндром и нет выхода за пределы массива A, считаем.}
            Z:=A;Inc(cnt);Rev;Add
        End;
        WriteLn(n,' ',cnt);
        {Вывод числа и количества шагов.}
        If cnt>=MaxN Then ReadLn;
        {Фиксируем факт выхода за пределы массива A.}
        Inc(n)
    End
End.

    Для чисел 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986 массива из 1000 элементов недостаточно для хранения результата. А всегда ли конечен описанный процесс, всегда ли можно получить палиндром?
 &nbs sp;   End;

    Рассмотрим следующую задачу. Дано n отрезков, длины которых целые числа. Берем два отрезка и из большего вычитаем меньший. Разность — новый отрезок. Если же длины отрезков совпадают, то один из них исключаем из дальнейшего рассмотрения. Продолжаем процесс. В результате получается одно число, равное длине оставшегося отрезка. Пример: n = 4, длины отрезков: 6, 15, 3, 9.

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

Задания для самостоятельной работы

    1. Дано n целых чисел. Найти среди них число, у которого приведенная ниже характеристика имеет максимальное значение:
    · сумма цифр;
    · первая цифра;
    · количество делителей;
    · сумма всех делителей.
    2. Дано n целых чисел. Найти среди них пару чисел, для которых выполняется приведенное ниже условие:
    · наибольший общий делитель имеет максимальное значение;
    · наименьшее общее кратное имеет наименьшее значение.
    Есть ли среди заданных чисел “близнецы”, т.е. простые числа, разность между которыми равна 2?
    3. Дано n целых чисел. Написать программу подсчета количества чисел, в записи которых нет цифры 8. При этом требуется использовать функцию вида

Function Yes8(x:LongInt):Boolean;

Без использования компьютера решите эту задачу для всех трехзначных чисел. Ответ: 729.
    4. Даны два числа — n и k (k < n). Число n есть основание системы счисления, а k — количество знаков в записи числа. Написать программу подсчета количества натуральных чисел в n-ичной системе счисления, записываемых ровно k знаками. Без использования компьютера решите эту задачу для всех трехзначных десятичных чисел. Ответ: 900.
    5. Объявлен конкурс на получение грантов. В конкурсе принимают участие n человек. Гранты выдаются первым пяти участникам, набравшим наибольшее количество баллов. Один участник не может одновременно получить два и более грантов. Написать программу определения количества способов, которыми могут быть распределены гранты. Исследовать область ее применимости.
    6. Дана шахматная доска размером n x n и n ладей. Определить количество способов расположения ладей на шахматной доске так, чтобы они не могли бить друг друга. Исследовать, для каких значений n можно использовать типы данных Integer, Word, LongInt.
    7. Дано n различных бусин. Сколько различных ожерелий можно составить из них? Исследуйте область применимости вашей программы.
    Примечание. При n = 7 число ожерелий равно (5040 : 7) : 2 = 360. Делением на 2 учитывается не только поворот (деление на 7), но и переворот ожерелий.
    8. Имеются предметы k различных типов. Количество предметов первого типа n₁ , второго — n₂ , …, k-го — n_k . Написать программу подсчета числа перестановок, которые можно сделать из этих предметов, и исследовать область ее применимости. Предварительно попытайтесь обосновать формулу:

P_n = n! / (n₁! • n₂! • … • n_k!).

    Есть текст. Его шифруют (кодируют) с помощью перестановки букв. В результате получается новый текст, называемый анаграммой (слова “лунка” и “кулан” — анаграммы). Для механической расшифровки анаграммы требуется выполнить количество перестановок, вычисляемых по вышеприведенной формуле, где n_i — количество конкретных букв в анаграмме. Предположим, что у вас есть компьютер с миллиардным быстродействием. Он выполняет миллиард умножений в секунду. Задайте значения величинам n, n₁ , n₂ , …, nk и подсчитайте, какое время ваш компьютер будет решать задачу.
    9. Черепашка перемещается по клеточному полю размером n x m. Ей разрешено двигаться вправо и вверх. В начальный момент времени она находится в нижней левой клетке (A), и ей необходимо попасть в верхнюю правую клетку (B). Сколько различных путей есть у Черепашки? Подсчитайте количество путей для различных значений n и m. Выясните, для каких значений n и m можно использовать для хранения результата переменные типов Integer, Word, LongInt. Предположим, что для анализа одного пути Черепашки компьютеру с миллиардным быстродействием (миллиард операций в секунду) требуется 100 операций. За какое время он проанализирует все пути для конкретных значений n и m?

    10. Последовательности длины n составляются из t нулей и k единиц, причем таким образом, что никакие две единицы не находятся рядом. Подсчитать количество таких последовательностей (ответ: C(t + 1, k)). Найти способ перечисления всех таких последовательностей для небольших значений t и k. Например, для t = 3, k = 2 это последовательности 00101, 01001, 01010, 10001, 10010, 10100.

Продолжение следует