Рабочая тетрадь Паскаль

Рабочая тетрадь по программированию. Паскаль

writeln('введите размерность матрицы:');

;

;

;

end;

;

end; еnd.

Турнир по программированию - http://compilers.infoznaika.ru/

31

Рабочая тетрадь по программированию. Паскаль

Задача нахождения максимума и минимума в массиве

Решим задачу поиска наибольшего элемента в таблице А из N вещественных чисел. Найдем максимум и индекс этого элемента.

var

a:array[1..30] of real; max: real;

j,i,n: integer;

begin

write('размерность массива ='); readln(n);

for i:=1 to n do read(a[i]); for i:=1 to n do write(a[i], ' ');

max:=a[1]; //максимальным элементом считаем первый j:=1; //запоминаем значение индекса первого

элемента //сравниваем максимальный с очередным элементом массива

for i:=2 to n do if max<a[i] then begin

//найдя элемент с большим значением запоминаем его и индекс max:=a[i];

j:=i;

end; writeln('Максимум=', max );

writeln('Индекс максимума =', j );

end.

Алгоритм поиска максимума:

1. .

.

2. .

.

Турнир по программированию - http://compilers.infoznaika.ru/

32

Рабочая тетрадь по программированию. Паскаль

3. .

.

4. .

.

Пример 1. Найти минимум главной диагонали квадратной матрицы.

;

;

end; writeln('Минимум главной диагонали=', min );

end.

Турнир по программированию - http://compilers.infoznaika.ru/

33

Рабочая тетрадь по программированию. Паскаль

Рекурсия.

Введем понятие рекуррентной последовательности: пусть известно k чисел а1 ..., ак. Эти числа являются первыми числами числовой последовательности. Следующие элементы данной последовательности вычисляются так:

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

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

— это

.

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

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

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

аi = ai-1 + 2.

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

Глубина рекурсии в обоих случаях равна единице (такую зависимость еще называют одношаговой рекурсией). В целом рекуррентная последовательность описывается совокупностью начальных значений и рекуррентной формулы. Все

Турнир по программированию - http://compilers.infoznaika.ru/

34

Рабочая тетрадь по программированию. Паскаль

это можно объединить в одну ветвящуюся формулу. Для арифметической прогрессии:

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

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

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

Начиная с третьего элемента каждое число равно сумме значений двух предыдущих, т.е. это рекуррентная последовательность с глубиной равной 2 (двухшаговая рекурсия). Опишем ее в ветвящейся форме:

Введение представления о рекуррентных последовательностях позволяет по-новому взглянуть на некоторые уже известные нам задачи. Например, факториал целого числа n! можно рассматривать как значение n-го элемента следующего ряда чисел:

a0 = 1, а1 = 1!, а2 = 2!, a3 = 3!, а4 = 4!, ...

Рекуррентное описание такой последовательности выглядит следующим образом:

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

Var N, I: 0 ... Maxint;

A: Real;

Begin

Write('N = ');

Readln (N) ;

Турнир по программированию - http://compilers.infoznaika.ru/

35

Рабочая тетрадь по программированию. Паскаль

A: = 1;

For I: = 2 to N do А:=А+2;

Writeln ('A(', N:1, ') = ', A)

End.

Рекуррентная формула ai= ai-1 + 2 перешла в оператор А:= А + 2.

Посмотрите на описание арифметической прогрессии в форме рекуррентной последовательности. Из него непосредственно вытекает способ определения функции для вычисления заданного элемента прогрессии.

Сделаем это для общего случая, определив арифметическую прогрессию с первым членом а0 и разностью d:

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

Function Progres(А0, D: Real; i: Integer): Real;

Begin

If i=1 Then Progres:=A0

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

End;

Пример 2. Вывести на экран первые 20 чисел Фибоначчи.

Var К: integer;

Function Fibon(N: Integer): Integer;

Begin

If (N=1) Or (N=2) Then Fibon:=1

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

End;

Begin

For K:=1 To 20 do WriteLn(Fibon(K))

End.

Турнир по программированию - http://compilers.infoznaika.ru/

36

Рабочая тетрадь по программированию. Паскаль

Требования к оформлению программ на языке PASCAL.

1. Соглашения по идентификаторам

1.1 Подбор идентификаторов

1.1.1 Все идентификаторы должны выбираться из соображений читаемости и максимальной семантической нагрузки.

Например:

const

Eps = 0.0001; { точность } var

Sum : Integer;{ сумма } Message: String; { сообщение }

Неудачными можно считать идентификаторы:

const

UU = 0.0001; { точность } var

Kk : Integer;{ сумма }

Zz : String; { сообщение }

1.1.2. Идентификаторы рекомендуется подбирать из слов английского языка. Например:

1)procedure Beep(Hertz, MSec: Word);

{выдает звуковой сигнал заданной частоты и длительности }

2)function ExistFile(FName: String): Boolean;

{выдает True, если файл с именем FName существует }

3)var

Done: Boolean; { признак окончания работы с программой } Width, Height: Real; { размеры изделия (ширина, высота) }

Не очень удачными можно считать идентификаторы:

1)procedure Zvuk(Chast, Dlit: Word);

{выдает звуковой сигнал заданной частоты и длительности }

2)function EstFile(Im: String): Boolean;

{выдает True, если файл с именем Im существует }

3)var

Konec: Boolean; { признак окончания работы с программой } Shirina, Vysota: Real; { размеры изделия (ширина, высота) }

Турнир по программированию - http://compilers.infoznaika.ru/

37

Рабочая тетрадь по программированию. Паскаль

1.2 Написание идентификаторов

1.2.1 Зарезервированные слова языка Turbo Pascal писать только маленькими буквами.

Например:

type, var, const; procedure, function; begin, end; if, then, else;

repeat, until; case; while; and, not, or; unit, uses, interface, implementation.

1.2.2 В любых идентификаторах каждое слово, входящее в идентификатор, писать, начиная с большой буквы, остальные буквы -- маленькие. В этом смысле символ подчеркивания "_" между словами

идентификатора можно считать излишним. Например:

1) var

NextX, LastX: Real; { следующая и предыдущая итерация } BeepOnError: Boolean; { подавать ли звуковой сигнал при

неправильном вводе пользователя? }

2)function GraphErrorMsg(ErrCode: Word): String;

{стандартная функция модуля Graph; выдает описание ошибки использования графики по ее коду }

3)begin

Write('Введите целое число, большее 10 ==>_ ');

ReadLn(Num);

if Num > 10 then WriteLn('OK'); end.

4) var

FileName: String;{ а не File_Name }

type

ByteArray = array [0..65534] of Byte; { а не Array_Of_Byte }

1.2.3 Рекомендуется идентификаторы, состоящие из одной буквы, писать большой буквой, если они не являются счетчиками циклов.

Например:

1)A := A + B; B := A - B; A := A - B;

2)procedure DeleteNode(var L: List; I: Word);

{удалить звено c номером I из списка L }

3)for i := 1 to N do

Турнир по программированию - http://compilers.infoznaika.ru/

38

Рабочая тетрадь по программированию. Паскаль

for j := 1 to N do

A[i, j] := (i + j) / 2;

2. Соглашения по самодокументируемости программ

2.1 Комментарии

2.1.1Комментарии в теле программы следует писать на русском языке и по существу так, чтобы программист, не участвовавший в разработке программы (но имеющий опыт работы на языке

Turbo Pascal), мог без

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

2.1.2Рекомендуется комментарии программы писать внутри символов { и }, а (* и *) использовать при отладке программы как "заглушки" участков программного кода.

2.2 Спецификация пользовательской процедуры или функции

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

а) назначение процедуры или функции; б) описание семантики параметров-значений (параметров, передаваемых по значению), если она неочевидна;

в) описание семантики параметров-переменных (параметров, передаваемых по ссылке), если она неочевидна.

г) для функции: описание семантики возвращаемого значения, если она неочевидна.

Например:

1)семантика параметров и возвращаемого значения очевидна function IsLeapYear(Y: Word): Boolean;

{возвращает True, если год Y -- високосный }

2)семантика параметров очевидна, семантика возвращаемого значения неочевидна

function DayOfWeek(D, M, Y: Word): Byte;

{Возвращает день недели даты D/M/Y;

год Y должен быть в отрезке 1582..4902; результат: ВСК = 0, ПНД = 1, ВТР = 2, ... СБТ = 6 }

3) семантика параметров и возвращаемого значения неочевидна const

MaxN = 10;

Турнир по программированию - http://compilers.infoznaika.ru/

39

Рабочая тетрадь по программированию. Паскаль

type

Matrix = array [1..MaxN, 1..MaxN] of Real; Vector = array [1..MaxN] of Real;

procedure Gauss(A: Matrix; B: Vector; Eps: Real; var X: Vector;

var HasSolution: Boolean; var NumOfRoots: Integer; var Det: Real;

var AForReverse: Matrix; var BForReverse: Vector); { Решение системы линейных алгебраических уравнений

методом Гаусса. Входные данные:

A-- матрица коэффициентов системы;

B-- столбец свободных членов системы; Eps -- точность вычислений.

Выходные данные:

X -- вектор решения;

HasSolution -- флаг, устанавливаемый в True, если решение системы существует, и в False во всех

остальных случаях;

NumOfRoots -- число корней в решении системы, может

AForReverse -- нижняя треугольная матрица, полученная из A в в результате выполнения прямого хода алгоритма Гаусса;

BForReverse -- столбец свободных членов, полученный из B в в результате выполнения прямого хода алгоритма Гаусса. }

Замечание:

Если процедура (функция) реализует какой-либо вычислительный метод (например: нахождение площади фигуры методом трапеций, поиск минимума функции методом Ньютона и т.п.), рекомендуется в теле

процедуры (функции) поместить комментарий с кратким описанием метода, либо ссылку на источник, где описан метод.

Турнир по программированию - http://compilers.infoznaika.ru/

40