67457
Диапазон. Переменные типа «Диапазон»
Лекция
Информатика, кибернетика и программирование
Все типы переменных, изученные до сих пор – скалярные (простые) типы. Массив – вектор, матрица, Массив – упорядоченная совокупность данных одного типа. Массив – переменная с индексом (со списком индексов). Объявление одномерного массива...
Русский
2014-09-23
130.5 KB
0 чел.
Лекция 5
Диапазон
<Диапазон> : : =
<Целое число 1> . . <Целое число 2>
Естественное требование:
<Целое число 1> не более, чем <Целое число 2>
Примеры.
1 . . 5
First . . Third
// Если выше по тексту было что-то наподобие:
// const First = 0; Third = 2;
Тип «Диапазон»
type <Имя типа> = <Диапазон> ;
Пример.
type MyType01 = –3 . . 72 ;
Переменные типа «Диапазон»
Примеры:
var
v1: 22 . . 44 ;
v2: MyType01 ;
const
v3: MyType01 = 6 ;
const
MyConst11 = 1; MyConst12 = 7;
type
MyType02 = MyConst11 .. MyConst12;
var
MyVar02: MyType02;
Замечание. Тип–Диапазон – порядковый тип.
Массивы
Все типы переменных, изученные до сих пор – скалярные (простые) типы.
Массив – вектор, матрица, ...
Массив – упорядоченная совокупность данных одного типа.
Массив – переменная с индексом (со списком индексов).
<Объявление одномерного массива> : : =
<Имя переменной> : array[<Диапазон>] of <Тип элемента> ;
<Объявление нескольких многомерных массивов> : : =
<Список имён > : array[<Список диапазонов>] of <Тип элемента> ;
или
<Список имён > : <Тип-массив> ;
<Тип-массив> : : =
array[<Список диапазонов>] of <Тип элемента > ;
<Обращение к элементу массива> : : =
<имя массива> [ <Список значений индексов> ]
Пример
const
MyConst21 = 1; MyConst22 = 8;
type
MyRange1 = 1 . . 7;
MyRange2 = MyConst21 . . MyConst22;
var
A: array[1 . . 4] of integer;
A1, A2, A3: array[1 . . 4, -1 . . 7] of double;
A4: array[MyRange1] of double;
A5: array[MyRange1, MyRange2] of double;
begin
A[3] := 99;
A1[2, 6] := 5.3;
A2[1][7] := 4.1e-10;
A3[5, 0] := 2;
end.
Пример. Заполнить матрицу числами, составляющими треугольник Паскаля.
, . , .
const
n=16;
type
MyArrayType = array[0 . . n , 0 . . n] of integer;
. . .
procedure PT(var mG: MyArrayType);
// procedure PT(var mG: array[0 . . n , 0 . . n] of integer);
var
m, k: integer;
begin
for m := 0 to n do for k := 0 to n do mG[m, k] := 0;
mG[0, 0] := 1;
for m := 1 to n do
begin
mG[m, 0] := 1; mG[m, m] := 1;
for k := 1 to m-1 do mG[m, k] := mG[m-1, k] + mG[m-1, k-1];
end;
end;
. . .
Тип «Запись»
<Тип «Запись»> : : =
record
<Список имён полей 1>: <Тип 1>;
<Список имён полей 2>: <Тип 2>;
. . .
end;
<Обращение к полю переменой типа «Запись»> : : =
<Имя переменной>.<Имя поля>
или
with <Имя переменной> do <Оператор, содержащий Имя поля>
Пример
{ TP7 }
program P0701;
type
DateTime = record // Delphi: TDateTime
Year, Month, Day, Hour, Min, Sec: word ;
end ;
MyRec = record
N: longint ;
FIO: string[40] ;
BirthDate: DateTime ;
end;
var
N: longint ;
v1: MyRec;
v2: record
N: longint ;
FIO: string[40] ;
BirthDate: DateTime ;
end;
procedure Proc1(v: MyRec) ;
begin
Writeln(v.FIO) ;
with v do
begin
Writeln(N) ;
Writeln(BirthDate.Day:2,’.’, BirthDate.Month:2,’.’, BirthDate.Year:4) ;
end;
end;
procedure Proc2(v: MyRec) ;
begin
Writeln(v.FIO) ;
with v do
begin
Writeln(N) ;
with v.BirthDate do
Writeln(Day,’.’, Month,’.’, Year) ;
end;
end;
begin
N := 2 ;
v1.N := 1;
v1.FIO := ‘Ivanov I.I.’;
v1.BirthDate.Year := 1950;
v1.BirthDate.Month := 10;
v1.BirthDate.Day := 2;
Proc1(v1) ; // Нормально
// Proc1(v2) ; // Ошибка
Proc2(v1) ; // Нормально
readln ;
end.
Пример рекурсивной процедуры. Вычисление определителя матрицы методом Крамера.
{$J+}
const
n = 5;
type
MyArray = array[1 . . n, 1 . . n] of double;
MyAuxArray = array[1 . . n] of byte;
var
D: double;
const
mA: MyArray =
(
(22, 19, 37, 62, 12),
(-20, 71, 46, 31, 47),
(32, 42, 59, 16, 77),
(-27, 29, 44, 72, 18),
(15, 47, -39, 23, -13)
);
mR: MyAuxArray = (0, 0, 0, 0, 0);
mC: MyAuxArray = (0, 0, 0, 0, 0);
procedure Det(m: integer; var D: double);
var
i, j, k: integer;
D0: double;
begin
k := n – m + 1;
if (k < 1) or (k > n) then begin D := 0; exit; end;
mR[k] := 1;
i := -1;
D := 0;
for j := 1 to n do
begin
if mC[j] = 0 then
begin
i := -i;
mC[j] := 1;
if k < n then Det(m-1, D0) else D0 := 1;
D := D + mA[k,j] * i * D0;
mC[j] := 0;
end;
end;
mR[k] := 0;
end;
begin
Det(n, D);
writeln(D);
end.
Рекурсивные алгоритмы
Пример. Найти все способы расстановки восьми ферзей на шахматной доске 8×8, при которых ферзи не бьют друг друга.
Разности индексов у элементов матрицы размера :
Суммы индексов у элементов матрицы размера :
uses CRT;
var
c: char;
n: integer;
mG: array [1..8] of boolean; // Вертикали
mDP: array [2..16] of boolean; // Диагонали, параллельные побочной
mDM: array [-7..7] of boolean; // Диагонали, параллельные главной
x: array [1..8] of integer;
procedure PutNextQueen(i: integer);
var
j, k: integer;
begin
for j := 1 to 8 do
begin
if mG[j] and mDP[i + j] and mDM[i - j] then
begin
x[i] := j;
if i < 8 then
begin
mG[j] := false; mDP[i + j] := false; mDM[i - j] := false;
PutNextQueen(i + 1);
mG[j] := true; mDP[i + j] := true; mDM[i - j] := true;
end
else
begin
for k:=1 to 8 do write(x[k]:5);
writeln;
Inc(n);
if n mod 20 = 0 then
// Останавливать вывод после показа очередной порции из 20 вариантов
begin
c := ReadKey;
if c = #27 then halt;
if c = #0 then c := ReadKey;
// Код «0» означает, что клавиша отправила в буфер клавиатуры
// два кода, второй из которых также должен быть извлечен
end;
end;
end;
end;
end;
begin
for n := 1 to 8 do x[n]:=0;
for n := 1 to 8 do mG[n] := true;
for n := 2 to 16 do mDP[n] := true;
for n := -7 to 7 do mDM[n] := true;
n := 0;
PutNextQueen(1);
writeln(‘n=’, n);
end.
Рекурсивные алгоритмы (продолжение)
Пример. Дана матрица A, состоящая из m строк и n столбцов. Элементы матрицы – неотрицательные числа. Пошаговое движение по элементам матрицы начинается от левого верхнего элемента и завершается правым нижним элементом . Каждый шаг движения должен быть сделан либо вправо (если текущий столбец – не последний), либо вниз (если текущая строка – не последняя). Постановка на очередной элемент матрицы оплачивается числом рублей, равным значению этого элемента.
Найти «самый дешёвый» из путей. Назвать его цену.
Решение будет построено двумя способами. Первый из них (Project3A) основан на рекурсии. Во втором (Project3B) применяется т.н. метод динамического программирования.
program Project3A;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
mMax = 20;
nMax = 20;
type
MyRecord = record
CellPrice, Frequency: integer;
Dyrection: char;
end;
MyArray = array[1 .. mMax, 1 .. nMax] of MyRecord;
var
m, n, p, q: integer;
A: MyArray;
procedure InitArray(var C: MyArray);
var
i, j: integer;
begin
Randomize;
m := 3 + Random(mMax - 2);
n := 3 + Random(nMax - 2);
Writeln('m=', m , ' n=', n);
for i := 1 to m do
for j := 1 to n do
begin
C[i][j].CellPrice := Random(mMax + nMax);
C[i][j].Frequency := 0;
C[i][j].Dyrection := '?';
end;
end;
procedure ShowPrices(var C: MyArray);
var
i, j: integer;
begin
Writeln('ShowPrices');
for i := 1 to m do
begin
for j := 1 to n do
Write(C[i][j].CellPrice : 5);
Writeln;
end;
end;
procedure ShowFrequencies(var C: MyArray);
var
i, j: integer;
begin
Writeln('ShowFrequencies');
for i := 1 to m do
begin
for j := 1 to n do
Write(C[i][j].Frequency : 5);
Writeln;
end;
end;
procedure ShowDyrections(var C: MyArray);
var
i, j: integer;
begin
Writeln('ShowDyrections');
for i := 1 to m do
begin
for j := 1 to n do
Write(C[i][j].Dyrection : 3);
Writeln;
end;
end;
function Right(i, j: integer): boolean;
begin
if j < n then Right := true else Right := false;
end;
function Down(i, j: integer): boolean;
begin
if i < m then Down := true else Down := false;
end;
function BestPathRecoursive(i, j: integer; var C: MyArray): integer;
var
id, ir: integer;
begin
Inc(C[i][j].Frequency);
if (i = m) and (j = n) then
BestPathRecoursive := 0
else
begin
if Right(i, j) then
ir := C[i][j + 1].CellPrice + BestPathRecoursive(i, j + 1, C)
else
ir := -1;
if Down(i, j) then
id := C[i + 1][j].CellPrice + BestPathRecoursive(i + 1, j, C)
else
id := -1;
if (ir >= 0) and (id >= 0) then
begin
if ir < id then
begin
C[i][j].Dyrection := 'r';
BestPathRecoursive := ir;
end
else
begin
C[i][j].Dyrection := 'd';
BestPathRecoursive := id;
end;
end
else
if ir >=0 then
begin
C[i][j].Dyrection := 'r';
BestPathRecoursive := ir;
end
else
if id >= 0 then
begin
C[i][j].Dyrection := 'd';
BestPathRecoursive := id;
end;
// Ничего другого не может быть!
end;
end;
procedure ShowPath(var C: MyArray);
var
k, i, j: integer;
begin
i := 1;
j := 1;
p := 0;
for k := 1 to m + n - 2 do
begin
Write(' ', C[i][j].Dyrection);
if C[i][j].Dyrection = 'r' then
Inc(j)
else
if C[i][j].Dyrection = 'd' then
Inc(i);
// Ничего другого не может быть!
p := p + C[i][j].CellPrice;
end;
Writeln;
end;
begin
InitArray(A);
ShowPrices(A);
q := BestPathRecoursive(1, 1, A);
Writeln('Price of best path = ', q);
ShowPath(A);
Writeln('Price of best path = ', p);
ShowDyrections(A);
ShowFrequencies(A);
Readln;
end.
