Математический факультет

Вид материала

Документы

Содержание Локализация имён. Перегрузка функций. Процедурные типы. 1.5 Динамическая память и указатели Статические массивы

Подобный материал:

• Клименко Алексей Владимирович Образование 2001-2006: Механико-математический факультет, 41.65kb.
• Программа вступительных испытаний по физике москва, 138.12kb.
• Механико-математический факультет магистратура, 328.27kb.
• Цель образовательной программы углубление, систематизация и обобщение знаний по математике,, 5.89kb.
• П. Г. Демидова Математический факультет. Реферат, 227.26kb.
• Н. П. Огарева математический факультет кафедра дифференциальных уравнений рабочая программа, 200.47kb.
• Г. В. Плеханова Экономико-математический факультет, факультет Информатики Дисциплина:, 80.62kb.
• Математический факультет; математическое обеспечение и администрирование информационных, 394.55kb.
• Утверждаю, 123.18kb.
• Математический факультет, 669.04kb.

Локализация имён.

Имена переменных, описанные внутри подпрограммы, локализуются в ней, т.е. они как бы «невидимы» снаружи подпрограммы. Такие переменные называются локальными. Переменные, которые объявлены в основной программе, называются глобальными. Они доступны в любой части программы, в том числе и в любой подпрограмме.

Например, в последнем рассмотренном примере переменные x, y, z – глобальные, переменные a, n, step, i – локальные, они недоступны основной программе. Локальные переменные существуют только тогда, когда работает подпрограмма: появляются при её вызове и исчезают при завершении её работы.

Имена переменных, локализованных в подпрограмме, могут совпадать с ранее объявленными глобальными именами. В этом случае локальное имя «закрывает» глобальное и делает его недоступным в пределах данной подпрограммы. Рассмотрим пример:

var i:integer;

procedure P;

var i:integer;

begin writeln(i) end;

begin i7; P end.

Что напечатает эта программа? Всё, что угодно: значение локальной переменной i при входе в процедуру P не определено, хотя одноимённая глобальная переменная имеет значение 7. Локальная переменная «закроет» глобальную и на экран будет выведено произвольное значение, содержащееся в локальной переменной i. Если убрать описание var i:integer; из процедуры P, то на экран будет выведено значение глобальной переменной i, т.е. 7.


Параметры.

Список формальных параметров необязателен и может отсутствовать. Любой из формальных параметров подпрограммы может быть параметром-значением или параметром-переменной. Кроме того, в Delphi 5 имеются ещё параметры-константы и так называемые выходные параметры. Перед параметром-переменной в списке формальных параметров ставится служебное слово var, а перед параметром-значением служебное слово var не ставится.

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

Например, пусть описана процедура M:

var b,c,res : real;

procedure M(x:real; var r,y:real);

begin y:=3x  r end;

Рассмотрим варианты вызова этой процедуры.

1). M(5, 1, res);

Вызов процедуры осуществлён неправильно. Правильно сделать так:

b1; M(5, b, res);

2). M(5, 2b–1, res);

Вызов процедуры осуществлён неправильно. Правильно сделать так:

c2b–1; M(5, c, res);

3). M(6b–7, c, res);

Вызов процедуры осуществлён правильно.

Если параметр определён как параметр-значение, то перед вызовом подпрограммы это значение вычисляется, полученный результат копируется во временную память и передаётся подпрограмме. Любые возможные изменения параметра-значения в подпрограмме никак не воспринимаются основной программой, так как в этом случае изменяется копия фактического параметра. Сами же фактические параметры, какими были до вызова процедуры, такими же и останутся после завершения её работы.

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

Пример 28.

var a, b : integer;

procedure inc2(var c:integer; d:integer);

begin

ccc; ddd;

writeln( удвоенные :  , с:5, d:5)

end;

begin

read(a, b);

writeln( исходные :  , a:5, b:5);

inc2(a, b);

writeln(результат :  , a:5, b:5);

readln

end.


После введения чисел 5 и 7 на экран будет выведено:

исходные: 5 7

удвоенные: 10 14

результат: 10 7

Параметры-переменные используются как средство связи подпрограммы и вызывающей программы: с их помощью подпрограмма может передавать результаты своей работы вызывающей программе. В распоряжении программиста всегда есть и другой способ передачи результатов подпрограммы – через глобальные переменные. Однако, злоупотребление глобальными переменными делает программу запутанной, трудной в понимании и сложной в отладке. Поэтому рекомендуется там, где это возможно, использовать передачу результатов через параметры-переменные. С другой стороны, описание всех формальных параметров как параметры-переменные нежелательно по двум причинам. Во-первых, это исключает возможность вызова подпрограммы с фактическими параметрами в виде выражений. Во-вторых, в подпрограмме возможно случайное использование формального параметра, т.е. существует опасность испортить непреднамеренно фактическую переменную. Чем меньше параметров объявлено параметрами-переменными и чем меньше в подпрограмме используются глобальные переменные, тем меньше опасность непредусмотренных побочных эффектов, связанных с вызовом подпрограмм.

При использовании параметра-константы перед ним в списке формальных параметров должно стоять слово const. Параметр-константа передаётся по ссылке, однако его нельзя изменять внутри подпрограммы.

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

В Delphi 5 имеются параметры, значения которых можно не указывать при вызове процедуры или функции. Их называют параметрами со значениями по умолчанию. В списке параметров они описываются следующим образом:

<имя параметра>:<тип>=<значение>.

Умалчиваемые параметры должны находиться в конце списка формальных параметров. Если при вызове процедуры или функции фактический параметр, соответствующий умалчиваемому параметру, не указан, то в подпрограмму передаётся заданное для умалчиваемого параметра значение.


Задачи.

96. Описать функцию function nod(x, y : integer) : integer; для подсчёта наибольшего общего делителя натуральных чисел x и y. С помощью этой функции решить задачу. Дано 10 натуральных чисел, введённых с клавиатуры. Найти их наибольший общий делитель, учитывая, что

НОД(a,b,c)=НОД ( НОД(a,b), c).

97. Описать функцию function nod(x, y : integer) : integer; для подсчёта наибольшего общего делителя натуральных чисел x и y. С помощью этой функции решить задачу. Даны натуральные числа n и p. Напечатать все натуральные числа, меньшие n и взаимно простые с p. (Числа называются взаимно простыми, если их НОД равен 1).

98. Описать функцию function nod(x, y : integer) : integer; для подсчёта наибольшего общего делителя натуральных чисел x и y. С помощью этой функции решить задачу. Даны натуральные числа p и q. Напечатать все делители числа q, взаимно простые с p.

99. Описать функцию function snum(n: integer):byte; для вычисления суммы цифр натурального числа n. С помощью этой функции решить задачу. Дано 10 натуральных чисел, введённых с клавиатуры. Найти среди них число с максимальной суммой цифр.

100. Описать функцию function snum(n : integer) : byte; для вычисления суммы цифр натурального числа n. С помощью этой функции решить задачу. Составить программу нахождения цифрового корня числа. Цифровой корень числа вычисляется следующим образом. Если сложить все цифры числа, затем все цифры найденной суммы и повторять этот процесс, то в результате будет получено однозначное число ( цифра ), которое и называется цифровым корнем числа.

101. Описать функцию function kdiv(n : integer):byte; для вычисления количества делителей натурального числа n. С помощью этой функции решить задачу. Дано 10 натуральных чисел, введённых с клавиатуры. Найти среди них число с максимальным количеством делителей.

102. Описать функцию function sdiv(n : integer):byte; для вычисления суммы делителей натурального числа n. С помощью этой функции решить задачу. В интервале от 1 до 10000 найти все совершенные числа, т.е. числа, равные сумме всех своих делителей, кроме самого себя.


Перегрузка функций.

В Object Pascal имеется возможность использовать подпрограммы с одинаковыми именами, но отличающиеся количеством и типом параметров. В заголовках таких подпрограмм должно быть указано слово overload. При вызове таких подпрограмм компилятор анализирует количество и тип фактических параметров и вызывает соответствующую подпрограмму. Например, в программе могут быть описаны две функции с именем min. Первая для определения минимального из двух действительных чисел, а вторая для определения символа с минимальным порядковым номером.

function min(a, b : real) : real; overload;

begin if a>b then result:=b else result:=a end;


function min(a, b : char) : char; overload;

begin if a>b then result:=b else result:=a end;


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


Процедурные типы.

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

type <имя процедурного типа> =

<заголовок процедуры или функции без имени>;

Например:

type funcl = function (a, b : real) : real;

Процедурные типы широко применяются в Object Pascal при использовании классов.


1.5 Динамическая память и указатели

Для переменных, указанных в разделе var программы, место в оперативной памяти выделяется в процессе компиляции программы. Такое размещение данных называется статическим. При этом должно быть заранее известно количество переменных и их тип.

Однако часто приходится обрабатывать данные, количество которых и их тип заранее не известны. В этом случае удобно использовать динамическую память. Динамическая память (куча) ­– эта та оперативная память компьютера, которая выделяется программе в процессе её выполнения. Использование динамической памяти позволяет экономить ресурсы памяти компьютера: в начале там могут быть размещены одни переменные, а затем они могут быть удалены и на их месте размещены другие.

Любая ячейка оперативной памяти – байт – имеет собственный адрес (номер). Адреса переменных можно хранить в переменных специального типа – указателях. Указатели могут быть типизированными и нетипизированными.

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

var <имя указателя> : <тип> ;

Например,

var p1, p2 : integer; p3 : real;

Здесь p1 и p2 – указатели на переменные типа integer, а p3 – указатель на переменную типа real.

Указателю может быть присвоено пустое значение nil , например p1:=nil, означающее, что переменная p1 ни на что не указывает, т.е. не содержит адрес какой-либо ячейки памяти. Как правило, при запуске программы все указатели содержат значение nil.

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

p1:=p2;

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

p1:=p1+2;

Адрес любой переменной можно получить с помощью операции взятия адреса @. Например, если L – переменная типа integer, то допустим следующий оператор:

p1:=@L;

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

 выделение памяти под динамическую переменную;

 присвоение указателю адреса выделенной памяти (инициализация указателя);

 освобождение памяти после использования динамической переменной.

Выделение памяти под динамическую переменную осуществляется с помощью процедуры new(x) – указатель на динамическую переменную. При этом в параметре x, являющемся типизированным указателем, сохраняется адрес выделенной области динамической памяти. Процедура dispose(x) освобождает память, занятую динамической переменной, на которую ссылается указатель x. Эта процедура уничтожает динамическую переменную, ранее созданную посредством процедуры new.

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

var x: pointer;

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

procedure GetMem(var p:pointer; size:integer);

Резервирует фрагмент динамической памяти требуемого размера size, в переменной p сохраняется адрес начала этого фрагмента.

procedure FreeMem(var p:pointer[; size:integer]);

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


1.6 Массивы

В Delphi 5 массивы могут быть статическими, т.е. иметь фиксированное число элементов, либо динамическими, когда количество элементов задаётся в процессе выполнения программы.


Статические массивы

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

type <имя типа>=array[<тип индекса (индексов)>] of <тип компонентов>;

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

Например:

type vector = array[1..3] of real;

table = array[1..4] of array[1..5] of integer;

Здесь vector – одномерный массив, состоящий из трёх вещественных чисел, table – двумерный массив (матрица), состоящий из четырёх строк и пяти столбцов целых чисел. Описание типа table можно также записать следующим образом:

type table = array[1..4, 1..5] of integer;

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

Для описанных выше типов можно задать, например, следующие переменные:

var m1, m2 : vector; matr : table;

Массив можно описать и непосредственно в разделе описания переменных:

var m1, m2 : array[1..3] of real;

matr : array[1..4, 1..5] of integer;

В Object Pascal одним оператором присваивания можно передать все элементы одного массива другому массиву того же типа, например:

m1:=m2;

Однако, объявление

var a : array[1..6] of integer;

b : array[1..6] of integer;

создаст разные типы массивов, поэтому оператор a:=b вызовет ошибку.

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

m1[2] matr[3,4] m2[i+1]

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

procedure S(a : array[1..10] of integer);

Правильно будет сначала описать тип массива в разделе type основной программы. Например:

const n = 10;

type lin = array[1..n] of integer;

procedure S(a : lin);

……………………………….


Одномерный массив. Инициализация. Работа с элементами. Рассмотрим процедуры инициализации и распечатки одномерного массива, считая, что тип массива описан следующим образом:

const n = 10;

type lin = array[1..n] of integer;

Заполнение массива числами, введёнными с клавиатуры:

procedure init1(var x : lin);

var i : integer;

begin

for i:=1 to n do read(x[i]);

end;

Заполнение массива случайными числами с помощью генератора случайных чисел:

procedure init2(var x:lin);

var i:integer;

begin

randomize;

for i:=1 to n do x[i]:=-50 + random(101);

end;

Функция random(t) берёт случайное целое число из отрезка [0, t-1]. Таким образом, массив будет заполнен случайными числами от -50 до 50.

Распечатка массива (вывод элементов массива на экран)

procedure print(x : lin);

var i : integer;

begin

for i:=1 to n do write(x[i]:4);

writeln

end;


Пример 29. Заполнить массив случайными числами от -25 до 25. Распечатать массив. Заменить отрицательные элементы массива на противоположные по знаку. Распечатать преобразованный массив.

const n = 10;

type lin = array[1..n] of integer;

var a : lin;

procedure init2(var x : lin);

var i : integer;

begin

randomize;

for i:=1 to n do x[i]:=-25 + random(51);

end;

procedure print(x : lin);

var i : integer;

begin

for i:=1 to n do write(x[i]:4);

writeln

end;

procedure sign1(var x : lin);

var i : integer;

begin

for i:=1 to n do

if x[i]<0 then x[i]:=-x[i]

end;

begin

init2(a); print(a);

sign1(a); print(a);

readln

end.


Задачи.

103. Заполнить массив случайными числами от -30 до 30. Распечатать массив.

1) Найти сумму положительных элементов.

function sum_pol(x:lin):integer;

2) Подсчитать количество чётных элементов.

function kol_chet(x:lin):integer;

3) Напечатать номера нечётных элементов.

procedure nechet(x:lin);

4) Если элемент является чётным числом, то прибавить к нему первый элемент массива, в противном случае – последний элемент массива. Первый и последний элементы массива не изменять.

procedure solve1(var x:lin);

5) Заменить элементы с k1-ого по k2-ой на противоположные по знаку.

procedure solve2(var x:lin; k1, k2:integer);

6) Сформировать массив b, каждый элемент которого равен

b[i]=a[1] + a[2] + … +a[i].

procedure solve3(x:lin; var y:lin);

7) Все элементы массива, предшествующие последнему отрицательному элементу массива, умножить на 10.

function last_neg(x:lin):integer;

procedure solve4( var x:lin);

104. Заполнить одномерный целочисленный массив размерности 10 элементами геометрической прогрессии, первый элемент которой равен а, знаменатель прогрессии – d.

procedure init_geom(var q:lin; a, d:integer),

105. Заполнить одномерный целочисленный массив размерности 20 числами Фибоначчи.

procedure init_fib(var x:lin);

106. Даны действительные числа a₁, a₂, … , a_n (n=10). Получить числа b₁, b₂, … , b_n (n=10) , где b_i – среднее арифметическое всех элементов последовательности a₁, a₂, … , a_n , кроме a_i (i=1, 2,…,n).

107. Даны действительные числа a₁, a₂, … , a_n, b₁, b₂, … , b_n (n=10). Вычислить (a₁ + b_n)(a₂ + b_n-1) … (a_n + b₁).


Максимум и минимум одномерного массива.

Пример 30. Найти максимальный элемент целочисленного массива размерности n.

const n = 10;

type lin = array[1..n] of integer;

var a : lin; res : integer;

procedure init1(var x : lin);

var i : integer;

begin

for i:=1 to n do read(x[i]);

end;

function max(x : lin) : integer;

var i : integer;

begin

result:=x[1];

for i:=2 to n do

if x[i]>result then result:=x[i]

end;

begin

init1(a);

res:=max(a); writeln(res);

readln; readln

end.


Задачи.

108. Найти номер максимального элемента одномерного целочисленного массива размерности 10.

109. Даны целые числа a₁, a₂, … , a₁₀ . Заменить элемент последовательности нулём, если a_i  max(a₁, a₂, … , a₁₀ ), и единицей в противном случае.

110. Даны целые числа a₁, a₂, … , a₁₀ . Все элементы этой последовательности, предшествующие первому по порядку элементу со значением max(a₁, a₂, … , a₁₀ ) домножить на max(a₁, a₂, … , a₁₀ ).

111. Дана последовательность действительных чисел a₁,…,a₁₀ . Требуется домножить все элементы этой последовательности на квадрат её минимума, если a₁0, и на квадрат её максимума, если a₁0.

112. Дана последовательность из 20 различных целых чисел. Найти сумму чисел этой последовательности, расположенных между максимальным и минимальным числами (включая их).

113*. Дано вещественное число a и вещественный массив из n элементов. Среди элементов массива найти два таких элемента b и c (если они существуют), что числа a, b, c могут быть сторонами прямоугольного треугольника с максимальной площадью. Вывести длины сторон этого треугольника и его площадь.

114*. Даны координаты n точек на плоскости (x₁,y₁), (x₂,y₂),…, (x_n,y_n) . Найти номера двух точек, расстояние между которыми наибольшее. (Считать, что такая пара точек единственная).


Удаление, вставка, перестановка элементов одномерного массива.

Пример 31. В одномерном целочисленном массиве размерности n удалить элемент с номером k.

Решение. Удаление элемента будет осуществлять процедура del(kk:byte; var m:lin). Её работа заключается в том, что все элементы, начиная с номера kk+1, и до номера n сдвигаются на один влево. Например, для удаления 5^ого элемента массива

11 3 -8 6 23 -17 9 31 4 15

нужно осуществить сдвиг:




11 3 -8 6 23 -17 9 31 4 15


const n = 10;

type lin = array[1..n] of integer;

var a : lin; k : byte;

procedure init1(var x : lin);

var i : byte;

begin

for i:=1 to n do read(x[i])

end;

procedure del(kk : byte; var x : lin);

var i : byte;

begin

for i:=kk to n-1 do x[i]:=x[i+1];

x[n]:=0

end;

procedure print1(nn : byte; x : lin);

var i : byte;

begin

for i:=1 to nn do write(x[i]:5);

writeln

end;

begin

init1(a);

readln(k); del(k, a);

print1(n-1, a);

readln

end.

После введения последовательности чисел

11 3 -8 6 23 -17 9 31 4 15

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

11 3 -8 6 -17 9 31 4 15


Пример 32. В одномерном целочисленном массиве размерности n вставить целое число x после элемента с номером k.

Решение. Вставку числа x после элемента с номером k будет осуществлять процедура ins(kk:byte; xx:integer; var x:lin). Её работа заключается в том, что все элементы, начиная с номера kk, и до номера n сдвигаются на один вправо (начиная с конца массива). Например, для вставки числа 100 после 5^ого элемента массива

11 3 -8 6 23 -17 9 31 4 15

нужно осуществить сдвиг:




11 3 -8 6 23 -17 9 31 4 15

Затем поставить число 100 на место элемента с номером kk+1

11 3 -8 6 23 100 -17 9 31 4 15

Полученный массив будет содержать n+1 элемент, поэтому массив сразу должен быть описан, как массив размерности n+1.

const n=10;

type lin=array[1..n+1] of integer;

var a:lin; k:byte; r:integer;

procedure init1(var x:lin);

var i:byte;

begin

for i:=1 to n do read(x[i])

end;

procedure ins(kk:byte; rr:integer; var x:lin);

var i:byte;

begin

for i:=n downto kk+1 do x[i+1]:=x[i];

x[kk+1]:=rr

end;

procedure print1(nn:byte; x:lin);

var i:byte;

begin

for i:=1 to nn do write(x[i]:5);

writeln

end;

begin

init1(a);

readln(k, r); ins(k, r, a);

print1(n+1, a);

readln

end.


Пример 33. В одномерном целочисленном массиве размерности n поменять местами первую и вторую половины массива.

Решение. Алгоритм заключается в том, что 1^ый элемент меняется местами с последним, 2^ой элемент – с предпоследним и так далее. Процедура swap(k1, k2:byte; var m:lin); меняет местами два элемента с номерами k1 и k2.

const n=10;

type lin=array[1..n] of integer;

var a:lin; j:byte;

procedure init1(var x:lin);

var i:byte;

begin

for i:=1 to n do read(x[i])

end;

procedure swap(k1, k2:byte; var x:lin);

var d:integer;

begin d:=x[k1]; x[k1]:=x[k2]; x[k2]:=d end;

procedure print(x:lin);

var i:byte;

begin

for i:=1 to n do write(x[i]:5);

writeln

end;

begin

init1(a);

for j:=1 to n div 2 do swap(j, n – j + 1, a);

print(a);

readln; readln

end.


Сортировка одномерного массива.

Для решения многих задач необходимо упорядочить данные по определённому признаку. Процесс упорядочения заданного множества объектов по определённому признаку называется сортировкой. Элементы массива можно сортировать по возрастанию a[1]a[2]>…>a[n], по невозрастанию a[1]a[2]…a[n]. Научившись выполнять одну сортировку, изменить её, чтобы получить другую, не составляет особого труда.

Пример 34. Сортировка простого обмена (пузырьком).

Рассмотрим идею метода на примере. Отсортируем по возрастанию массив из 5 элементов 5 11 9 4 3. Будем просматривать пары рядом стоящих элементов массива и, если элементы стоят неправильно, то менять их местами.

1^ый просмотр. 5 11 9 4 3 ( 5 < 11 не меняем)

5 11  9 4 3 ( 11 > 9 меняем)

5 9 11  4 3 ( 11 > 4 меняем)

5 9 4 11  3 ( 11 > 3 меняем)

Элемент 11 теперь находится на своём месте.

2^ой просмотр. 5 9 4 3 11 ( 5 < 9 не меняем)

5 9  4 3 11 ( 9 > 4 меняем)

5 4 9  3 11 ( 9 > 3 меняем)

Элемент 9 теперь находится на своём месте.

3^ий просмотр. 5  4 3 9 11 ( 5 > 4 меняем)

4 5  3 9 11 ( 5 > 3 меняем)

Элемент 5 теперь находится на своём месте.

4^ый просмотр. 4  3 5 9 11 ( 4 > 3 меняем)

Элементы 3 и 4 теперь находятся на своих местах.

Процедура сортировки.

procedure sort(var x:lin);

var k, i, w:integer;

begin

for k:=1 to n-1 do

for i:=1 to n-k do

if x[i] > x[i+1] then

begin w:=x[i]; x[i]:=x[i+1]; x[i+1]:=w end;

end;

Таким образом, мы произвели n-1 просмотр массива, на каждом k-ом просмотре выполняется n-k сравнений. Массив отсортирован. Этот метод называют также методом пузырька, так как в процессе сортировки элементы с заданным свойством постепенно всплывают на поверхность.


Пример 35. Сортировка простыми вставками.

На i-ом шаге сортировки считается, что часть массива, содержащая первые i-1 элементов уже упорядочена, то есть a[1]
Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из пяти элементов 13 6 8 11 3 по возрастанию.

1^ый шаг. 13 6 8 11 3

2^ой шаг. 6 13 8 11 3

3^ий шаг. 6 8 13 11 3

4^ый шаг. 6 8 11 13 3

5^ый шаг. 3 6 8 11 13


Процедура сортировки.

procedure sort(var x:lin);

var i, j, w:integer;

begin

for i:=2 to n do

begin

w:=x[i]; j:=i-1;

while (j>0) and (w
begin x[j+1]:=x[j]; dec(j) end;

x[j+1]:=w

end;

end;


Задачи.

115. Удалить из одномерного целочисленного массива размерности n первый отрицательный элемент.

116. Удалить из одномерного целочисленного массива размерности n последний чётный элемент.

117*. Удалить из одномерного целочисленного массива размерности n все отрицательные элементы.

118. Вставить число x после первого отрицательного элемента.

119. Вставить число x перед последним отрицательным элементом.

120. Дана последовательность различных действительных чисел a₁,…,a₁₀ . Поменять местами максимальный элемент и последний элемент последовательности.

121. Дана последовательность различных действительных чисел a₁,…,a₁₀ . Поменять местами минимальный элемент и первый отрицательный элемент последовательности.

122. В одномерном целочисленном массиве размерности n (n=10) поменять местами первую и вторую половины массива.

a₁, a₂, … a₅, a₆, … a₉, a₁₀  a₆, … a₉, a₁₀, a₁, a₂, … a₅

123. Дан одномерный целочисленный массив размерности n (n=10). Переставить его элементы следующим образом: поменять местами первые три и последние три элемента, сохраняя порядок их следования.

124*. Дан одномерный целочисленный массив размерности n (n=10). Переставить в обратном порядке элементы массива, расположенные между минимальным и максимальным элементами.


Двумерные массивы. Инициализация. Работа с элементами.

Пример 36. Заполнить двумерный массив размера nm (n строк, m столбцов) целыми числами, введёнными с клавиатуры. Ко всем отрицательным элементам массива прибавить первый элемент соответствующей строки. Вывести преобразованный массив на экран.

const n=4; m=5;

type lin = array[1..m] of integer;

mas = array[1..n] of lin;

var a:mas;

procedure init1_mas(var x:mas);

var i,j:integer;

begin

for i:=1 to n do for j:=1 to m do read(x[i,j])

end;

procedure print_mas(x:mas);

var i,j:integer;

begin

for i:=1 to n do

begin

for j:=1 to m do write(x[i,j]:6);

writeln

end

end;

procedure solve(var x:mas);

var i,j:integer;

begin

for i:=1 to n do

for j:=1 to m do if x[i,j]<0 then x[i,j]:=x[i,j] + x[i,1]

end;

begin

init1_mas(a);

solve(a); print_mas(a);

readln; readln;

end.


Пример 37. Заполнить двумерный массив размера nm (n строк, m столбцов) случайными действительными числами из интервала [-4, 4]. К элементам k1-ой строки прибавить соответствующие элементы k2-ой строки (k1=2, k2=3).

const n=4; m=5;

type lin = array[1..m] of real;

mas = array[1..n] of lin;

var a,b:mas;

procedure init2_mas(var x:mas);

var i,j:integer;

begin

randomize;

for i:=1 to n do for j:=1 to m do x[i,j]:=(-40 + random(81))/10;

end;

procedure print_mas(x:mas);

var i,j:integer;

begin

for i:=1 to n do

begin for j:=1 to m do write(x[i,j]:6:1); writeln end;

writeln;

end;

procedure sum_str(var x:mas; k1, k2:integer);

var j:integer;

begin

for j:=1 to m do x[k1,j]:=x[k1,j]+x[k2,j];

end;

begin

init2_mas(a); print_mas(a);

b:=a; sum_str(b, 2, 3); print_mas(b);

readln;

end.


Пример 38. Заполнить квадратную матрицу размера nn следующим образом:



const n=8;

type mas = array[1..n,1..n] of integer;

var a:mas;

procedure fill(var x:mas);

var i,j:integer;

begin

for i:=1 to n do for j:=1 to n do

if j=n–i+1 then x[i,j]:=i else x[i,j]:=0

end;

procedure print_mas(x:mas);

var i,j:integer;

begin

for i:=1 to n do

begin for j:=1 to n do write(x[i,j]:6); writeln; writeln end;

end;

begin

fill(a); print_mas(a);

readln;

end.


Пример 39. Дан двумерный целочисленный массив размера nm. Напечатать номера строк, все элементы которых чётны.

const n=4; m=5;

type lin = array[1..m] of integer;

mas = array[1..n] of lin;

var a:mas; k:integer;

procedure init1_mas(var x:mas);

var i,j:integer;

begin

for i:=1 to n do for j:=1 to m do read(x[i,j])

end;

function control(y:lin):boolean;

var j:integer; t:boolean;

begin

t:=true; j:=1;

while (j<=m) and t do

begin t:=not odd(y[j]); inc(j) end;

result:=t

end;

begin

init1_mas(a);

for k:=1 to n do

if control(a[k]) then writeln(k);

readln; readln

end.


Пример 40. Дан двумерный целочисленный массив размера nm. Сформировать одномерный массив, каждый элемент которого равен сумме элементов соответствующей строки исходного массива. Вывести полученный одномерный массив на экран. Найти номер строки с максимальной суммой элементов.

const n=4; m=5;

type lin = array[1..m] of integer;

mas = array[1..n] of lin;

vector = array[1..n] of integer;

var a:mas; rez:vector; nmax:integer;

procedure init1_mas(var x:mas);

var i,j:integer;

begin

for i:=1 to n do for j:=1 to m do read(x[i,j])

end;

procedure print(x:vector);

var k:integer;

begin

for k:=1 to n do write(x[k]:5);

writeln

end;

procedure sum_str(x:mas; var z:vector);

var i,j,s:integer;

begin

for i:=1 to n do

begin

z[i]:=0;

for j:=1 to m do z[i]:=z[i] + x[i,j]

end;

end;

function max_sum(z:vector):integer;

var k, max:integer;

begin

max:=z[1]; result:=1;

for k:=2 to n do

if max
begin max:=z[k]; result:=k end;

end;

begin

init1_mas(a);

sum_str(a, rez); print(rez);

nmax:=max_sum(rez); writeln(nmax);

readln; readln;

end.


Пример 41. Найти произведение двух квадратных матриц размера nn.

const n=4;

type mas = array[1..n, 1..n] of integer;

var a, b, c:mas;

procedure init1_mas(var x:mas);

var i,j:integer;

begin

for i:=1 to n do for j:=1 to n do read(x[i,j])

end;

procedure print_mas(x:mas);

var i,j:integer;

begin

for i:=1 to n do

begin

for j:=1 to n do write(x[i,j]:6); writeln

end

end;

procedure mult(x,y:mas; var z:mas);

var i, j, k:integer;

begin

for i:=1 to n do for j:=1 to n do

begin

z[i,j]:=0;

for k:=1 to n do z[i,j]:=z[i,j] + x[i,k]*y[k,j]

end

end;

begin

init1_mas(a);

init1_mas(b);

mult(a, b, c);

print_mas(c);

readln; readln;

end.


Задачи.

125. Заполнить двумерный массив размера nm (n строк, m столбцов) действительными числами, введёнными с клавиатуры. (Все элементы матрицы различны, среди них есть и положительные, и отрицательные числа).

1) Найти сумму элементов матрицы.

2) Найти количество отрицательных элементов матрицы.

3) Найти максимальный элемент матрицы и его индексы.

4) Найти среднее арифметическое положительных элементов матрицы.

5) Все элементы матрицы, сумма индексов которых кратна 3, заменить нулями.

6) Получить новую матрицу путём деления всех элементов матрицы на её наибольший по модулю элемент.

7) Найти сумму элементов строки, в которой расположен элемент с наименьшим значением.

8*) Найти максимальный среди отрицательных элементов матрицы.

126. Заполнить двумерный массив размера nn (n=5) случайными целыми числами из интервала [-60, 60]. Получить квадратный массив того же порядка, в котором элемент равен единице, если соответствующий элемент исходного массива больше элемента, расположенного в его строке на главной диагонали, и равен нулю в противном случае.

127. Заполнить массив 66 следующим образом:

1 2 3 4 5 6

2 1 2 3 4 5

3 3 1 2 3 4

4 4 4 1 2 3

5 5 5 5 1 2

6 6 6 6 6 1


128*. Заполнить массив 55 следующим образом:

1 -2 3 -4 5

-10 9 -8 7 -6

11 -12 13 -14 15

-20 19 -18 17 -16

21 -22 23 -24 25


129. Дан двумерный целочисленный массив размера nm. Сформировать одномерный массив, каждый элемент которого равен количеству чётных элементов соответствующей строки исходного массива. Вывести полученный одномерный массив на экран. Найти номер строки с максимальным количеством чётных элементов.

130. Дан двумерный целочисленный массив размера nm. Сформировать одномерный массив, каждый элемент которого равен максимальному элементу соответствующей строки исходного массива. Вывести полученный одномерный массив на экран. Найти номер строки с минимальным среди максимальных элементов строк.

131. Дан двумерный целочисленный массив размера nm. Напечатать номера строк

1) все элементы которых одинаковы;

2) элементы которых образуют симметричные последовательности;

3) элементы которых образуют возрастающие последовательности.

132. Дана квадратная матрица A размера nn (n=4). Найти A² + A³.