Семакин И.Г., Шестаков А.П. Основы программирования

Подождите немного. Документ загружается.

F:=l;

For I:=l To N Do

F:=F*I;

Очевидно, что такой вариант программы будет работать быст-

рее,

чем рекурсивный. И

том случае, когда важнейшим является

сокращение времени выполнения программы, следует отдать пред-

почтение последнему варианту.

В каждой конкретной реализации Паскаля имеется ограниче-

ние на количество рекурсивных обращений к подпрограмме (глу-

бина рекурсии). Это связано с ограничением на размер стека. По

этой причине можно попасть в ситуацию, когда рекурсивной под-

программой вообще не удастся воспользоваться.

Рекурсивно определена может быть не только функция, но и

процедура. Примеры использования рекурсивно-определенных

процедур рассматриваются в пятой главе.

Упражнения

Составить программу вычисления площади кольца по зна-

чениям внутреннего и внешнего радиусов, используя подпрог-

рамму вычисления площади круга (2 варианта: с процедурой и

с функцией).

По координатам вершин треугольника вычислить его пери-

метр,

используя подпрограмму вычисления длины отрезка, со-

единяющего две точки.

Даны три целых числа. Определить, сумма цифр которого

из них больше. Подсчет суммы цифр организовать через под-

программу.

Определить площадь выпуклого четырехугольника по задан-

ным координатам вершин. Использовать подпрограмму-функцию

вычисления длины отрезка и подпрограмму-процедуру вычисле-

ния площади треугольника по формуле Герона.

Описать рекурсивную функцию

pow(x,

n) от вещественного х

(х

0) и целого я, которая вычисляет величину х" по формуле

при п

х "

х -х

пЛ

при п

6. Даны натуральные числа пит; найти НОД (я, т). Исполь-

зовать программу, включающую в себя рекурсивную процедуру

вычисления НОД, и основанную на соотношении НОД

(п,

т)

= НОД

(т,

г), где г

—

остаток от деления п на т.

3.14.

Вычисление рекуррентных последовательностей

Рекуррентная последовательность. Из курса математики извест-

но понятие рекуррентной

последовательности.

Это понятие вво-

дится так: пусть известно к чисел а

..., а

. Эти числа являются

первыми числами числовой последовательности. Следующие эле-

менты данной последовательности вычисляются так:

к+

\ = F{a

..., а

);

к+2

= F(a

, ...,

к+х

);

k+i

F(a

, ...,

к+2

);

...

Здесь F— функция от к аргументов. Формула вида

4= F(a,.

a,_

..., а;_

)

называется рекуррентной

формулой.

Величина к называется глуби-

ной

рекурсии.

Другими словами, можно сказать, что рекуррентная последова-

тельность — это бесконечный ряд чисел, каждое из которых, за

исключением

начальных,

выражается

через

предыдущие.

Примерами рекуррентных последовательностей являются ариф-

метическая (1) и геометрическая (2) прогрессии:

а, = 1, а

=Ъ, а

=5,

=7,

= 9, ... (1)

а, = 1, а

= 2, о

= 4, а

= 8, а

= 16, ... (2)

Рекуррентная формула для указанной арифметической про-

грессии:

а, = о,_, + 2.

Рекуррентная формула для данной геометрической прогрессии:

с,= 2-о,_,.

Глубина рекурсии в обоих случаях равна единице (такую за-

висимость еще называют одношаговой рекурсией). В целом ре-

куррентная последовательность описывается совокупностью на-

чальных значений и рекуррентной формулы. Все это можно объ-

единить в одну ветвящуюся формулу. Для арифметической

прогрессии:

Г1,

если / = 1,

\ -> -1

[я,-_,

+2, если / > 1.

Для геометрической прогрессии:

Г1,

если / = 1,

[2-а,_,, если / > 1.

Следующая числовая последовательность известна в математи-

ке под названием чисел Фибоначчи:

1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Начиная с третьего элемента каждое число равно сумме значе-

ний двух предыдущих, т.е. это рекуррентная последовательность с

глубиной равной 2 (двухшаговая рекурсия). Опишем ее в ветвя-

щейся форме:

а-

[fi-i+fi-г, '">2.

Введение представления о рекуррентных последовательностях

позволяет по-новому взглянуть на некоторые уже известные нам

задачи. Например, факториал целого числа п\ можно рассматри-

вать как значение «-го элемента следующего ряда чисел:

= 1, а, = 1!,

= 2\, я

3!,

= 4\, ...

Рекуррентное описание такой последовательности выглядит

следующим образом:

а.

°'

[о,_,

•

/, / > 0.

Программирование вычислений рекуррентных последовательнос-

тей.

С рекуррентными последовательностями связаны задачи та-

кого рода:

1) вычислить заданный (я-й) элемент последовательности;

2) математически обработать определенную часть последова-

тельности (например, вычислить сумму или произведение пер-

вых п членов);

3) подсчитать количество элементов на заданном отрезке пос-

ледовательности, удовлетворяющих определенным свойствам;

4) определить номер первого элемента, удовлетворяющего

определенному условию;

5) вычислить и сохранить в памяти заданное количество эле-

ментов последовательности.

Данный перечень задач не претендует на полноту, но наиболее

часто встречающиеся типы он охватывает. В четырех первых зада-

чах не требуется одновременно хранить в памяти множество эле-

ментов числового ряда. В таком случае его элементы могут полу-

чаться

последовательно

в одной

переменной,

сменяя друг друга.

Пример 1. Вычислить л-й элемент арифметической профессии (1).

Var N,I: 0..Maxlnt;

A: Real;

Begin

Write('N=');

ReadLn(N);

A:=l;

For I:=2 To N Do

А:=А+2;

WriteLn('A(',N:1,')=',A:6:0)

End.

Рекуррентная формула я,=

О,-.,

+ 2 перешла в оператор А :=

А +

Пример 2. Просуммировать первые п элементов геометричес-

кой прогрессии (2) (не пользуясь формулой для суммы первых п

членов прогрессии).

Var N,I:

0..Maxlnt;

A,S:

Real;

Begin

Write('N='); ReadLn(N);

A:=l;

S:=A;

For I:=2 To N Do

Begin

A:=2*A;

S:=S+A

End;

WriteLn

('Сумма

равна',S:б:0)

End.

При вычислении рекуррентной последовательности с глуби-

ной

уже нельзя обойтись одной переменной. Это видно из следу-

ющего примера.

Пример

Вывести на печать первые п

(п >

3) чисел Фибоначчи.

Подсчитать, сколько среди них четных чисел.

Var N,I,K,F,F1,F2:

0..Maxlnt;

Begin

Fl:=l; F2:=l;

K:=0;

WriteLn ('F(1)=',F1, 'F(2) = \F2) ;

For I:=3 To N Do

Begin

F:=F1+F2;

WriteLn('F(',1:1,')=',F);

If Not Odd(F) Then K:=K+1;

F1:=F2;

F2:=F

End;

WriteLn('Количество четных чисел в

последовательности равно',К)

End.

Понадобились

три

переменные для последовательного вычисле-

ния двухшаговои рекурсии, поскольку для нахождения очередного

элемента необходимо помнить значения двух предыдущих.

Пример 4. Для заданного вещественного х и малой величины е

(например, е = 0,000001) вычислить сумму ряда

. х

+ х

—

...,

включив в нее только слагаемые, превышающие е. Известно, что

сумма такого бесконечного ряда имеет конечное значение, рав-

ное е", где е = 2,71828... — основание натурального логарифма.

Поскольку элементы этого ряда представляют собой убывающую

последовательность чисел, стремящуюся к нулю, то суммирова-

ние нужно производить до первого слагаемого, по абсолютной

величине не превышающего е.

Если слагаемые в этом выражении обозначить следующим об-

разом:

X X

1, о, = х, а

—-, а

—, ...,

то обобщенная формула для /-го элемента будет следующей:

Нетрудно увидеть, что между элементами данной последова-

тельности имеется рекуррентная зависимость. Ее можно найти

интуитивно, но можно и вывести формально. Правда, для этого

нужно догадаться, что рекурсия — одношаговая, и что каждый

следующий элемент получается путем умножения предыдущего

на некоторый множитель, т.е.

а,:

= К

•

а,_,.

Используя обобщенную формулу, имеем:

= К

Xi TS Х,-1

(i-l)!

Отсюда:

Действительно:

К-

/И

W(/-l)!

X X

= \, а

•

-, а

= а

•

- и т.д.

Следовательно, данная рекуррентная последовательность мо-

жет быть описана следующим образом:

а, =

если/

х . „

а,_,—,

если/>0.

И наконец, приведем программу, решающую поставленную

задачу.

Var A,X,S,Eps: Real;

I: Integer;

Begin

Write('X='); ReadLn(X);

Write('Epsilon

=');

ReadLn(Eps);

A:=l;

S:=0; I:=0;

While Abs(A)>Eps Do

Begin

S:=S+A;

I:=1+1;

A:=A*X/I

End;

WriteLn('Сумма ряда равна

S:10:4)

End.

Как и прежде, значения одношаговой рекуррентной последо-

вательности вычисляются в одной переменной.

Каждое повторное выполнение цикла в этой программе при-

ближает значение s к искомому (уточняет значащие цифры в его

записи). Такой вычислительный процесс в математике называется

итерационным процессом. Соответственно, циклы, реализующие

итерационный вычислительный процесс, называются итерацион-

ными

циклами. Для их организации используются операторы while

или Repeat.

Пример 5. Для заданного натурального ./V и вещественного х

(х >0) вычислить значение выражения:

ух

ух +...

л/х.

В этом случае рекуррентность не столь очевидна. Попробуем

найти ее методом индукции. Будем считать, что искомое выраже-

ние есть yV-й элемент последовательности следующего вида:

я,

= л/х, а

yjx

yfx, а

\х

+ у]х +

vx,...

Отсюда видна связь:

= yjx

ч, а

= Jx

, ..., а,- = Jx

a,.,.

Теперь поставленная задача решается очень просто:

Var A,X: Real; I,N: Integer;

Begin

Write('X='); ReadLn(X);

Write('N='); ReadLn(N);

A:=

Sqrt(X);

For I:= 2 To N Do

A:=Sqrt(X+A);

WriteLn('Ответ:',A)

End.

К решению всех перечисленных выше задач можно подойти

иначе.

Вспомним о рекурсивно определенных подпрограммах. По-

смотрите на описание арифметической прогрессии в форме ре-

куррентной последовательности. Из него непосредственно вы-

текает способ определения функции для вычисления заданного

элемента прогрессии.

Сделаем это для общего случая, определив арифметическую

прогрессию с первым членом а

и разностью d:

\а

если

/ = 1,

\ А -1

[а,_, + а, если f > 1.

Соответствующая подпрограмма-функция выглядит так:

Function Progres(АО,D: Real;I:

Integer): Real;

Begin

If 1=1

Then Progres:=A0

Else Progres:=Progres(АО,D,1-1)+D

End;

Следующая программа выводит на экран первые 20 чисел

Фибоначчи, значения которых вычисляет рекурсивная функ-

ция Fibon.

Var К: Byte;

Function Fibon(N:

Integer):

Integer;

Begin

If (N=1) Or (N=2)

Then Fibon:=1

Else Fibon:=Fibon(N-l)+Fibon(N-2)

End;

Begin

For K:=l To 20 Do WriteLn(Fibon(K))

End.

Необходимо отметить, что использование рекурсивных функ-

ций ведет к замедлению счета. Кроме того, можно столкнуться с

проблемой нехватки длины стека, в котором запоминается «мар-

шрут» рекурсивных обращений.

Рекуррентные последовательности часто используются для ре-

тения разного рода эволюционных задач, т.е. задач, в которых

прослеживается какой-то процесс, развивающийся во времени,

рассмотрим такую задачу.

Пример 6. В ходе лечебного голодания масса пациента за

дней

снизилась с 96 до 70 кг. Было установлено, что ежедневные поте-

ри массы пропорциональны массе тела. Вычислить, чему была равна

масса пациента через к дней после начала голодания для

*=1,2,...,29.

Обозначим массу пациента в /-Й день через р

{

(/ = 0,1,2,..., 30).

Из условия задачи известно, что р

- 96 кг, р

ъо

= 70 кг.

Пусть К— коэффициент пропорциональности убывания мас-

сы за один день.

Тогда

=р

-Кр

={\ -К)р

;

=(1-К)р

;

Л =(1 - К)рг, ... ;

Р;

=(1 - A)/>,-i-

Получаем последовательность, описываемую следующей рекур-

рентной формулой:

f96,

если

/ =

Р> =

\<У-К)'р,_

если1</<30.

Однако нам неизвестен коэффициент К. Его можно найти, ис-

пользуя условие /?зо

70.

Для этого будем делать обратные подстановки:

Л0=(1-^)-Л9=(1-^)

-Л8=О-^)

-Р27=...=

= (\-КУ

-р

=(1-КУ°-96.

Из равенства (1

—

А)

-96 = 70 находим:

- К = —

Далее программирование становится тривиальным.

Var I: Byte;

P,Q:

Real;

Begin

P:=96;

Q:=Exp(l/30*Ln(70/96)

)

;

For I:=l To 29 Do

Begin

P:=Q*P;

WriteLn(I,'-й день-',Р:5:3,'кг')

End

End.

Упражнения

Рекуррентная последовательность определена следующим

образом:

а, =

если/

.1 .

Для данного натурального п получить значение

а„.

Дана последовательность:

если / = 0, / = 1,

i-\

• 1

+—LS.

если

; > J.

/ - Г

Вычислить произведение элементов с 1-го по 20-й.

Используя рекуррентный подход, вычислить сумму много-

члена 10-й степени по формуле Горнера, где х — данное веще-

ственное число:

10х

+ 9х

+ 8х

+... + 2х

х = ((...((10х+ 9)х+ 8)х +... + 2)х+ 1)х.

Для данного вещественного х и натурального N вычислить

цепную дробь: х/(1 + х/(2 + х/(3 + x/(.../(N

х))...).

Вычислить и вывести все члены числового ряда

ill J_

' 2!' 3!' '"' N\'

превышающие значение 10"

6. Функцию у

можно вычислить как предельное значение

последовательности, определяемой рекуррентной формулой:

Ук

Ук-\+-

Ук-\

l, 2,...

Начальное значение

задается произвольно (желательно бли-

же к vx ). За приближенное значение корня с точностью е берется

первое у

, для которого выполняется условие: \у

г. Соста-

вить программу.

3.15. Основные понятия и средства компьютерной

графики в Турбо Паскале

До сих пор мы использовали экран компьютера только для

вывода символьной информации

—

чисел, текстов. Однако Турбо

Паскаль позволяет выводить на экран рисунки, чертежи, графики

функций, диаграммы и т.п., все то, что принято называть компь-

ютерной графикой.

стандарте Паскаля графический вывод не предусмотрен. Од-

нако на разных типах компьютеров, в разных реализациях Паска-

ля существуют различные программные средства графического

вывода

—

специальные наборы данных, функций, процедур. Не-

смотря на такое разнообразие, имеются общие понятия и сред-

ства, свойственные любому варианту реализации графики в лю-

бом

языке программирования.

данном разделе лекций мы затро-

нем только такие базовые средства.

Начиная с четвертой версии Турбо Паскаля для IBM PC по-

явилась мощная графическая библиотека, организованная в мо-

дуль Graph.

приложении 2 в справочной форме дано описание

основных компонент этого модуля.

рассмотренных ниже при-

мерах программ используется модуль Graph. Для его подключения

в начале программы необходимо написать строку:

Uses Graph;

Графические режимы экрана. Для вывода графических изобра-

жений необходимо перевести экран в один из графических режи-

мов.

графическом режиме можно из программы управлять состо-

янием каждого пиксела (точечного элемента) экрана.

Графические режимы отличаются:

• размером графической сетки (Мх N, где М

—

число точек по

горизонтали, N

—

число точек по вертикали);

• цветностью (число воспроизводимых на экране цветов).

Допустимые режимы зависят от типа монитора и соответствую-

щего графического драйвера, используемого на компьютере.

Для установки графического режима экрана существуют соот-

ветствующие процедуры.

модуле Graph процедура установки гра-

фического режима экрана имеет следующий заголовок:

Procedure InitGraph(Var Driver,Mode: Integer;

Path: String) ;

Здесь целая переменная Driver определяет тип графического

драйвера; целая переменная Mode задает режим работы графичес-

кого драйвера; Path

—

выражение типа String, содержащее мар-

шрут поиска файла графического драйвера.

Список констант модуля Graph, определяющих типы драйве-

ров и режимы, приведен в табл. П2.1 приложения 2.

Вот пример программы, инициализирующей графический ре-

жим VGAHi для работы с драйвером VGA (монитор типа VGA).

Uses Graph;

Var Driver,Mode: Integer;

Begin