Базовые алгоритмы работы с двухмерными массивами

Перемещение по массиву:

Про матрицу, имеющую m строк и n столбцов, говорят, что она имеет размер m*n

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

Перемещение по строке:

for i:=1 to m do {внешний цикл, изменяется номер строки}

…

for j:=1 to n do {внутренний цикл, изменяется номер столбца}

Перемещение по столбцу:

for j:=1 to n do {внешний цикл, изменяется номер столбца}

…

for i:=1 to m do {внутренний цикл, изменяется номер строки}

Заполнение массива

Случайными числами в заданном промежутке (n,m) с заданным интервалом k

for i:=1 to 10 do

for j:=1 to 10 do

a[i,j]:=random((n-m+1)/k)*k+n; {n,m k должны быть задано заранее}

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

for i:=1 to 10 do

for j:=1 to 10 do

a[i,j]:=j;

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

for j:=1 to 10 do

for i:=1 to 10 do

a[i,j]:=1;

По строкам, змейкой. Например, первая строка - 1 2 3 4 5, вторая -10 9 8 7 6, третья - 11 12 13 14 15 и т.д.

K:=1

for i:=1 to 10 do begin

for j:=1 to 10 do begin

a[i,j]:=k; k:=k+1; end;

i:=i+1;

for j:=10 downto 1 do begin

a[i,j]:=k; k:=k+1; end;

end;

Поиск в массиве

Найти максимальный (минимальный) элемент

max:=a[1];

n:=1;m:=1;

for i:=1 to 10 do

for j:=1 to 10 do

if a[I,j]>max then begin max:=a[I,j]; n:=i;m:=j; end;

Найти максимум главной диагонали

max:=a[1];

n:=1;

for i:=1 to 10 do

if a[i,i]>max then begin max:= a[i,i];n:=i; end;

Найти минимум побочной диагонали (размерность массива 10Х 10)

min:=a[1];

n:=1;

for i:=1 to 10 do

if a[i,11-i]>min then begin min:= a[i,11-i];n:=i; end;

Преобразование массивов

Заменить все элементы, отвечающие данному условию (>a), на заданную величину (c).

for i:=1 to 10 do

for j:=1 to 10 do

if a[i,j]>a then begin a[I,j]:=c; end;

Найти сумму каждой строки матрицы и записать в отдельный одномерный массив.

program mas4;

uses crt;

const n=4; m=4;

type t=array[1..n,1..m] of integer; w=array[1..4] of integer;

var a:t;i,j,b,s,d:integer; c:w;

begin

clrscr;

for i:=1 to n do

begin

writeln ('Введите строку элементов матрицы (4 элемента)');

for j:=1 to m do read(a[i,j]);

writeln;

end;

for i:=1 to n do

begin for j:=1 to m do begin textcolor (14); write(a[i,j]:3); end;

writeln;

end;

writeln; {Расчёт суммы}

for i:=1 to n do

begin s:=0; for j:=1 to m do

begin s:=s+ a[i,j]; end;

c[i]:=s;

textcolor (10);

write(c[i]:6);

end;

repeat until keypressed;

end.

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

program mas2;

uses crt;

const n=8; m=8;

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

var a:t;

i,j:integer;

begin

clrscr;

textcolor (9);

for i:=1 to n do begin

for j:=1 to m do begin a[i,j]:=random (10); write (a[i,j]:3); end;

writeln;

end;

writeln;

textcolor (14);

for i:=1 to n do begin

for j:=1 to m do begin write (a[j,i]:3); end;

writeln;

end;

repeat until keypressed; end.

Рисование многоугольников Двумерные массивы в графике.

· Процедура drawpoly (<число вершин> + 1, <двумерный массив координат вершин>) прямое назначение процедуры – вычерчивание ломаной!!! Поэтому отправную вершину надо ещё раз указать в последней строке массива.

· Процедура fillpolyпозволяет рисовать закрашенные многоугольники.

program graphsb;

uses graph, crt;

const t:array [1..5, 1..2] {Массив с координатами вершин пятиугольника}

of integer = ((50,50),(125,25),(200,50),(150,150),(50,200));

f:array [1..4, 1..2] {Массив с координатами вершин треугольника}

of integer=((250,50),(350,25),(400,150),(250,50));

var gd,gm,c:integer;

begin

gd:=detect;

initgraph (gd,gm,'');

setcolor (14); setbkcolor (1);

setfillstyle (8,10); {Тип заливки}

fillpoly (5,t); {Закрашенный пятиугольник}

drawpoly (4,f); {Контурный треугольник}

repeat until keypressed;

end.

Примеры программ:

Дана матрица b, состоящая из целых. Получить матрицу r, значения которой равны удвоенным значениям матрицы b

program mas5;

uses crt;

const n=4; m=4;

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

var r,b:t;i,j:integer;

begin

clrscr;

textcolor (15);

for i:=1 to n do

begin

writeln ('Введите строку матрицы (4 элемента)');

for j:=1 to m do

begin

read (b[i,j]);

end; writeln;

end;

for i:=1 to n do

for j:=1 to m do

r[i,j]:=b[i,j]*2;

writeln;

for i:=1 to n do

begin

for j:=1 to m do

begin

textcolor (10);

write (r[i,j]:3);

end;

writeln;

end;

repeat until keypressed;

end.

Одномерный массив из 10 элементов заполнить произвольными числами от 0 до 9 и выдать его на экран.

program pt1;

uses crt;

type t=array[1..10] of integer;

var a:t;i:integer;

begin

clrscr;

randomize;

for i:=1 to 10 do

begin

a[i]:=trunc(random(10));

write(a[i]:4);

end;

readln;

end._

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

Двумерный массив размерностью 4 х 5 заполнить целыми числами в интервале от –10 до 20 с шагом 5 и выдать его на экран.

Двумерный массив размерностью 4 х 5 заполнить целыми числами в интервале от –10 до 20 с шагом 5 и выдать его на экран. Найти максимальный элемент массива и его координаты.

Заполнить одномерный массив размерностью М (М ввести с клавиатуры) целыми числами от –30 до 39 и выдать на экран. Все отрицательные элементы массива заменить на 0 и выдать массив на экран. Поменять местами 2-й и предпоследний элемент массива, выдать массив на экран.

Заполнить одномерный массив размерностью М (М ввести с клавиатуры) целыми числами от –30 до 39 и выдать на экран. Отсортировать массив по убыванию и выдать на экран.

ТЕМА №6 ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PASCAL. ПРОЦЕДУРЫ. ФУНКЦИИ. СОСТАВЛЕНИЕ ПРОГРАММ С ИСПОЛЬЗОВАНИЕ ПРОЦЕДУР И ФУНКЦИЙ. РЕКУРСИЯ (4 часа)

Подпрограммы.

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

Процедуры.

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

Преимущества использования процедур - уменьшение объем программы, сокращение времени на отладку.

Принцип работы процедуры:

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

Затем продолжается выполнение основной части программы.

Процедура оформляется подобно основной программе:

Procedure имя (формальные параметры);

Раздел описаний

Begin

Раздел операторов

End;

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

Параметры (переменные), определяемые при описании процедуры называются формальными.

Параметры (переменные), задаваемые при вызове процедуры называются фактическими.

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

Параметры-значения – передают информацию только в процедуру (входные), описываются как переменные с указанием типа (без зарезервированного слова Var).

Параметры-переменные – передают информацию, как в процедуру, так и обратно (выходные), их описание начинается со слова Var, затем следует список переменных с указанием типа.

Пример:

Procedure sterline (len: integer); - параметры-значения.

Procedure stl (l: integer, Var n integer); - параметры-значения и параметры – переменные.

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

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

stl (а, n);

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

Пример использования процедур:

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

Uses crt;

Var n: integer;

Procedure sterline (var len: integer);

Var i:integer;

Begin

For i:=1 to len do

Write (‘*’);

End;

Begin

Write(‘Введите количество звездочек’); Readln(n);

Sterline (n);

Readln; End.

Функции.

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

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

Function имя (формальные параметры):тип;

Раздел описаний

Begin

Операторы

Имя:= …

End;

Поскольку результат обозначается именем функции, то после формальных параметров указывается тип функции, который должен совпадать с типом результата вычислений. В конце описания функции имени функции обязательно присваивается какое-то значение. Вызывается функция по ее имени с указанием фактических параметров. Функция может использоваться в операторах присваивания, условных операторах и т.п. Например, Res:=Compare(x1,x2);

Пример использования функций:

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

Uses crt;

Var x1,x2:real; res:char;

Function Compare (a,b: real):char;

Begin

If a>b then Compare:=’>’ else if a<b then Compare:=’<’ else Compare:=’=’;

End;

Begin

Writeln (‘Введите числа’);

Readln(x1,x2);

Res:=Compare(x1,x2);

Writeln(x1:6:2, res,x2:6:2);

Readln; end.

Рекурсия.

Рекурсия – это вывоз подпрограммой

(процедурой или функцией) самой себя.

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

PROGRAM DEMO1;

USES CRT;

VAR M:BYTE;

FUNCTION FAKT(N:BYTE):LONGINT;

BEGIN

IF N=1 THEN FAKT:=1

ELSE FAKT:=FAKT(N-1)*N;

END;

BEGIN

CLRSCR;

WRITE('N-');READLN(M);

WRITELN('N!=',FAKT(M));

READKEY;

END.

В нашем примере происходит так: в операторе печати вызывается функция FAKT с параметрам N, которая в свою очередь вызывает функцию FAKT с параметрам N-1, и так далее, пока не вызывается FAKT(1). Тогда это процесс останавливается, затем происходить извлечение результата в обратном порядке.

Это хорошо видно на следующем примере программы:

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

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

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

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

Пример:

PROCEDURE B( J:BYTE);FORWARD; {тело процедуры заменено директивой FORWARD }

PROCUDURE A( I:BYTE);

BEGIN

…

B(I);

…

END;

PROCEDURE B;

BEGIN

…

A(J);

…

END;

Примеры программ с процедурами и функциями:

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

Найти разность двух факториалов F=m! – k!, используя функцию.

Примеры программ с использованием рекурсий:

Написать рекурсивную функцию вычисления суммы 1+2+3+4+5+…+N:

PROGRAM DEMO5;

USES CRT;

VAR M:WORD;

FUNNCTION SUM(N:WORD):LONGINT;

BEGIN

IF N=1 THEN SUM:=1 ELSE SUM:=SUM(N-1)+N;

END;

BEGIN

WRITE(‘N-‘);READLN(M);

WRITELN(‘СУММА -’,SUM(M));

READKEY;END.

ЛИТЕРАТУРА

1. Попов В.В. Паскаль и Дельфи. Самоучитель. Питер, - 2003, - 544 с.

2. Фаронов В.В. Turbo Pascal 7.0 Начальный курс. Издательство "ОМД Групп" – 2003, - 577 с.

3. Шпак Ю.А. Turbo Pascal 7.0 на примерах. Издательство "Юниор", - 2003, - 498 с.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ. 4

ТЕМА №1 ЭТАПЫ РЕШЕНИЯ ЗАДАЧ НА ЭВМ. АЛГОРИТМИЗАЦИЯ. ОСНОВНЫЕ ПОНЯТИЯ. (2 часа) 5

ТЕМА№2 ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PASCAL. ОСНОВНЫЕ ПОНЯТИЯ. СТРУКТУРА ПРОГРАММЫ. ОПЕРАТОРЫ ВВОДА-ВЫВОДА (2часа) 9

ТЕМА №3 ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PASCAL. ПРОРЯДКОВЫЕ ТИПЫ ДАННЫХ. ВЕТВЛЕНИЕ. ОПЕРАТОРЫ УСЛОВНОГО И БЕЗУСЛОВНОГО ПЕРЕХОДА. СОСТАВЛЕНИЕ ПРОГРАММ С ИСПОЛЬЗОВАНИЕ ВЕТВЛЕНИЯ И ПЕРЕХОДОВ.(2 часа) 17

ТЕМА №4 ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PASCAL. ОРГАНИЗАЦИЯ ЦИКЛОВ. ОПЕРАТОРЫ ЦИКЛОВ. СОСТАВЛЕНИЕ ПРОГРАММ С ИСПОЛЬЗОВАНИЕ ОПЕРАТОРОВ ЦИКЛА.(2 часа) 24

ТЕМА №5 ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PASCAL. МАССИВЫ, ОДНОМЕРНЫЕ И ВДУХМЕРНЫЕ. СОСТАВЛЕНИЕ ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ МАССИВОВ (4 часа) 28

ТЕМА №6 ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PASCAL. ПРОЦЕДУРЫ. ФУНКЦИИ. СОСТАВЛЕНИЕ ПРОГРАММ С ИСПОЛЬЗОВАНИЕ ПРОЦЕДУР И ФУНКЦИЙ. РЕКУРСИЯ (4 часа) 37

ЛИТЕРАТУРА.. 42

Маринин Иван Валерьевич

Прусс Борис Наумович

Хандыго Валентина Геннадьевна

ИНФОРМАТИКА