Лабораторная работа n 8.
Подпрограмма-функция.
Цель и задача работы: изучить работу с подпрограммой-функцией. Реализовать программу лабораторной работы номер 2 с подпрограммой-функцией, например, ввод и вывод в соответствующих подпрограммах-процедурах, а обработка в подпрограмме- функции. Обрабатываемые данные передаются подпрограмме-функции через параметры.
Теоретические положения.
Все, что было сказано в предыдущей лабораторной работе о подпрограммах-процедурах, также относится и к подпрограммам-функциям.
Но характерное отличие между ними заключается в том, что само имя подпрограммы-функции может возвращать некоторый результат. В связи с этим отличаются описание подпрограммы-функции от описания подпрограммы-процедуры и способ обращения к ней.
Описание подпрограммы-функции начинается с ключевого слова FUNCTION, за которым идет имя подпрограммы-функции, вслед за именем в круглых скобках формальные параметры, если подпрограмма-функция с параметрами, потом ставится двоеточие и пишется тип возвращаемого значения. В языке программирования Паскаль допустимы подпрограммы- функции, возвращаемые значения которых относятся к простым типам, т.е. значением функции не может быть, например, массив. При описании под- программы-функции в ее теле должен присутствовать хотя бы один оператор присваивания, в левой части которого фигурирует имя описываемой подпрограммы-функции, причем хотя бы один оператор такого вида должен быть выполнен.
Формат описания подпрограммы-функции:
описание-функции = "FUNCTION" идентификатор ":" тип-результата ";" ! "FUNCTION" идентификатор "(" секция-формальных-параметров (* ";" секция-формальных-параметров *) ")" ":" тип-результата ";"
тип-результата = идентификатор-типа.
Так как подпрограмма-функция возвращает некоторое значение, то при обращении к подпрограмме-функции указывается ее имя (в круглых скобках фактические параметры, если они необходимы), например, в правой части оператора присваивания, в условном операторе при записи условия или при передаче в подпрограмму (функция или процедура) в виде фактического параметра, которому соответствует только формальный параметр-значение и т.д.
Формат обращения к подпрограмме-функции:
указатель-функции = идентификатор-функции [список-фактических- параметров]
идентификатор-функции = идентификатор.
Пример описания подпрограммы-функции:
FUNCTION FACT(N: INTEGER): INTEGER;
VAR L, K: INTEGER;
BEGIN
K:=1;
FOR L:=2 TO N DO K:=K*L;
FACT:=K;
END;
Лабораторная работа n 9.
Рекурсивные функции и процедуры.
Цель и задача работы: научиться описывать и использовать рекурсивные функции. Написать программу, обрабатывающую данные рекурсивным способом.
Теоретические положения.
Использование идентификатора функции (процедуры) в теле самой функции (процедуры) называется рекурсивным обращением к функции(процедуре) или рекурсией.
Рекурсия применяется в основном тогда, когда природа самой решаемой задачи рекурсивна. Как правило это различные комбинаторные задачи, решаемые полным или неполным перебором; деревья, уже само их определение через поддеревья (которые, в свою очередь, сами являются деревьями) подчеркивает их рекурсивную природу и многие другие задачи.
Рекурсивные функции можно понять на примере факториала - функция F(N)=N! эту функцию можно определить по размеру, в том числе и рекурсивно:
N!=
1, при N=0
N*(N-1)!, при N>0
Отсюда видно, что N! определяется через N*(N-1)!, т.е. через эту же самую функцию, но для предыдущего значения аргумента.
Язык программирования Паскаль разрешает рекурсивное писание функций. Особенность рекурсивного описания функции состоит в том, что в теле функции содержится обращение к этой же описываемой функции.
Факториал вычисляется только от натуральных чисел, т.е. чисел больше или равных нулю, и обязательно целых.
Пример описания функции:
TYPE NATUR=0..MAXINT;
FUNKTION FACT(N: NATUR): NATUR;
BEGIN
IF (N=0)
THEN FACT:=1
ELSE FACT:=N*FACT(N-1);
END;
Рассмотрим процесс вычисления рекурсивной функции. Пусть, например, вызываем функцию в виде FACT(3). При входе в функцию локальной переменной N присваивается значение равное 3. (N=3)
Т.к. N<>0, то выполняется оператор FACT:=3*FACT(2); в правой части стоит вызов функции FACT(2), то происходит обращение к функции FACT с параметром 2. Теперь вводится уже новая переменная N, чтобы подчеркнуть это, обозначим ее как N1. (N1=2) Т.к. N1<>0, то выполняется оператор FACT:=2*FACT(1); в правой части стоит вызов функции FACT(1), то происходит обращение к функции FACT с параметром 1. Опять вводится новая переменная N2 и ей присваивается значение 1. (N2=1)
Т.к. N2<>0, то выполняется оператор FACT:=1*FACT(0); опять происходит обращение к самой себе (заметим, что каждый раз откладывается завершение вычисления в правой части). Теперь N=0, и происходит присваивание FACT:=1; по получении данного результата завершается выполнение оператора FACT:=1*FACT(1); что дает FACT(1), далее завершается выполнение оператора FACT:=2*FACT(1); что дает FACT(2),далее завершается выполнение оператора FACT:=3*FACT(2); что дает конечный результат FACT(3)=6.
Рекурсивные функции короче и нагляднее, чем нерекурсивные, нона их выполнение затрачивается больше машинного времени (за счет повторных обращений к функции) и памяти (за счет увеличения локализованных в функции переменных (в данном случае N, N1, N2)).
Варианты заданий:
1) Вычислить X в степени Y путем многократного умножения (X, Y: INTEGER)
2) Написать функцию C(M,N), где 0<=M<=N, для вычисления биноминальных коэффициентов: C(M,N)=N!/(M!*(N-M)!)
3) Написать рекурсивную функцию PIN(X,N) от вещественного X (X<>0) и целого N, которая вычисляет величину X^N согласно формуле:
X^N=
1 , при N=0
1/X^N , при N<0
X*X^(N-1) , при N>0
4) Описать рекурсивную функцию ROOT(F,A,B,EPS), которая методом деления отрезка пополам находит с точностью EPS>0 корень уравнения F(X)=0 на отрезке [A,B] (считать, что A<B, F(A)<F(B) и F(X)- непрерывная и монотонная функция на отрезке [A,B]
5) Задана последовательность символов, описать функцию проверяющую, является ли симметричной последовательность символов в этой последовательности, начиная с I-того и кончающегося на J-том элементе
6) Задана последовательность вещественных чисел, описать функцию которая ищет минимальный элемент в этой последовательности
7) Дана последовательность из N целых чисел, N+1 элемент которой равен нулю (последовательность не содержит больше нулей кроме этого). Напечатать сначала все отрицательные числа этой последовательности, а затем - все положительные (в любом порядке) 8) Дано N различных натуральных чисел. Напечатать все перестановки этих чисел.
9) Задача о 8 ферзях: на шахматной доске расставить 8 ферзей так, чтобы они не "били" друг друга
10) "Ханойская башня". Имеются три колышка A,B,C и N дисков разного диаметра на A, пронумерованных от 1 до N в порядке возрастания из размеров. Требуется перенести все диски с колышка A на колышек C, соблюдая при этом следующие условия : диски можно пере- носить только по одному, больший диск нельзя ставить на меньший
11) Вычислить рекурсивно функцию вида
у=COS(X)+COS(X^2)+COS(X^3)+...+COS(X^N)
12) Вычислить N-ое число ряда Фибоначчи
13) Найти количество цифр заданного числа
14) Найти сумму цифр заданного числа
15) Вычислить интеграл от А до В функции F(X)=1/(0.5-E^X), при заданных А и В.
16) Задано целое число N, записать его цифры в обратном порядке и вывести его на экран дисплея, как целые число
17) Определить, является ли заданная строка "правильной записью целого числа" (возможно со знаком). Число вводить посимвольно
18) Написать функцию, заменяющую оператор MOD, т.е. запись в виде "L:=X MOD Y;" заменить на "L:=MD(X,Y);" (оператор MOD не использовать)
19) Написать функцию, заменяющую оператор DIV, т.е. запись в виде "L:=X DIV Y;" заменить на "L:=DV(X,Y);" (оператор DIV не использовать)
20) Перевести целое число из одной системы счисления в другую
21) Задано N чисел, описать функцию, находящую в этой последовательности максимальный элемент.
22) Составить программу сортировки по возрастанию одномерного массива из N элементов. Использовать рекурсию.
23) Обойти шахматную доску конем, побывав в каждой клетке, но не более одного раза.
24) Лабиринт задан двумерным массивом. Из левого верхнего угла лабиринта пройти в правый нижний. Массив задается вводом. Элементы, по которым можно пройти, обозначаются "1", а по которым нельзя проходить - "0". Если проход возможен, то координаты каждого шага вывести на экран. Если пройти нельзя, то выдать соответствующее сообщение. Проход по диагонали невозможен.
25) Вычислить функцию Y=SIN(X), разложенную в степенной ряд, с заданной степенью точности.
26) Из состава участников конференции, на которой присутствует N человек. Надо избрать делегацию, состоящую из M человек. Сколькими способами это можно сделать?
27) Вывести на экран все возможные способы расстановки белых фигур (два коня, два слона, две ладьи, ферзь и король) на первой линии шахматной доски.
28) Найти кол-во чисел меньше числа N (1000<N<100000), составленных из цифр A, B, C.
29) Какое максимальное число коней можно расставить на шахматной доске, при условии, что они не будут бить друг друга ?
30) Вычислить функцию Y=LN(X), разложенную в степенной ряд, с заданной степенью точности.