Готовимся к ЕГЭ по информатике

1. Кортежи

    Кортеж – неизменяемая структура данных, которая состоит минимум из двух полей и похожа на структуру данных «Запись» (Record) из стандартного Паскаля. Кортеж может объединять в одной переменной поля с разными типами данных. Синтаксис описания кортежа следующий:

 var T: (type1, type2, …, typeN);

где T – переменная кортежа, а type1, type2, …, typeN – типы данных всех полей кортежа.

    После этого можно присвоить переменной значения в круглых скобках. Например, запишем кортеж из 3 полей – строка, целое число, вещественное число. В полях кортежа запишем некоторые значения:

 var T: (string, integer, real):= (‘Петров’, 24, 75.91);

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

 var T:= (‘Петров’, 24, 75.91);

    Чтобы обращаться к элементам кортежа, можно использовать квадратные скобки и индекс элемента (индексация с нуля):

 Print(T[1], T[0], T[2]);    // 24 Петров 75.91

    Однако, так как это неизменяемая структура, то по индексу элемента кортежа отдельный элемент нельзя изменить, компилятор выдаст ошибку о неизменяемости кортежа. Изменять кортеж можно только целиком:

 var T:= (‘a’,’b’,’c’)       // (a,b,c)

 T:= (‘bb,’cc’,’aa’)         // (bb,cc,aa)

    На количество полей кортежа наложено ограничение: максимально в одном кортеже может содержаться до 7 полей. Такое ограничение обусловлено тем, что кортежи в PascalABC.NET реализованы на основе кортежей из платформы .NET, где присутствует такое же ограничение.

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

 var f:(integer,integer)->(integer,integer);

    Далее данную переменную связываем с лямбда-выражением, которое получает на вход два целых числа и выводит два значения – сумму и произведение этих чисел:

 f:= (a,b) -> (a+b,a*b);

    Код, представленный ниже, демонстрирует использование кортежей языка PascalABC.NET в сравнении со структурой Record на языке Паскаль.

2. Динамические массивы

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

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

    Для описания одномерных массивов достаточно указать ключевые слова «array of» и тип данных элементов массива, например:

 var F: array of integer;

где F – имя массива, integer – элементы массива являются целыми числами.

    Для описания многомерных массивов, например, двумерных, нужно указывать ключевое слово «array[,] of», например:

 var T: array[,] of real;

где T – имя двумерного массива, [,] – размерность двумерного массива, real – элементы массива являются вещественными числами.

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

Способ 1. Использовать ключевое слово «new» и конструкцию T[k] или T[n,m], где T – тип данных массива, k, n, m – размерности массива, например:

 F:= new integer[10];

 T:= new real[3, 4];

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

Способ 2. Использовать стандартную процедуру SetLength, например:

 SetLength(F,10);

 SetLength(T,3,4);

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

    Как и раньше, описание и инициализацию массивов можно объединить в одну строку:

 var F:=new integer[10];

 var T:=new real[3,4];

    Обращение к элементам массива происходит как через указание индекса элемента в квадратных скобках, например, F[0], F[3], T[1,3], T[4,0], так и через точечный метод ElementAt(i), например, F.ElementAt(0), F.ElementAt(3), однако он подходит только для одномерных массивов.

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

## function SumDiag(a:array [,] of integer):integer; begin   Result:=0;   for var i:=0 to a.ColCount-1 do     Result+=a[i,i]; end;   procedure MatrMaxMin(a:array [,] of integer); begin   var (max,min):=(0,0);   foreach var x in a do   begin     max:= x>max ? x : max;     min:= x<min ? x : min;   end;   print($'Максимальный = {max}, Минимальный ={min}'); end;   var F:=MatrGen(3,3,(i,j)->(i+1)+3*j).print; println($'Сумма диагональных элементов = {SumDiag(F)}'); MatrMaxMin(F);

Вывод:    1   4   7    2   5   8    3   6   9 Сумма диагональных элементов = 15 Максимальный = 9, Минимальный =0

    Для удобства работы с динамическими массивами было разработано большое количество методов, которые нужно вызывать через «точечную нотацию», мы рассмотрим основные из них: Print, PrintLines, Length, Low, High, Sum, Max, Min, Average.

    Методы Print и Printlines выводят элементы массива в виде строки и столбца соответственно. Метод Length возвращает длину массива, методы Low и High возвращают соответственно значения первого и последнего элементов массива, что является очень удобным при работе с массивами. Методы Sum, Max, Min и Average возвращают соответственно сумму элементов массива, максимальный и минимальный элементы, среднее арифметическое элементов.

    В языке реализованы функции, позволяющие формировать одномерные и двумерные массивы с нужным содержанием, рассмотрим главные из них: Arr, ArrFill, ArrGen, Matr, MatrGen.

    Функция Arr(a,b,c,…,z) позволяет сформировать динамический массив, заполненный указанными значениями a,b,c,…,z. Её аналогом является другая конструкция – указание элементов массива между двумя вертикальными чертами ||, например:

 var F:= Arr(2, 3, 5, 7, 11, 13);

 var F:= |2, 3, 5, 7, 11, 13|;

    Функция ArrFill(n: integer, a: T) возвращает динамический массив, состоящий из n-элементов, которым присваивается значение a типа T, где T – произвольный тип данных. С помощью этой функции можно легко формировать массивы одинаковых элементов, например, массив из 10 целых чисел с элементами, равными 1, можно определить следующим образом:

 var F:= ArrFill(10, 1);

Соответственно, если вместо целой единицы указать вещественную, то есть 1.0, то будет создан массив вещественных чисел такого же размера.

    Намного больше возможностей формирования массивов предоставляет функция ArrGen, которая своим названием говорит, что элементы массива могут быть «сгенерированы» определённым образом. Для генерации элементов функция использует лямбда-выражения, рассмотренные в предыдущем пункте.

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

   ArrGen(n: integer, gen: i -> T);

Здесь n – количество элементов массива, Gen: i -> T – лямбда-выражение, определяющее все элементы массива.

    Лямбда-выражение Gen(i) принимает на вход значения от 0 до n-1 и возвращает соответствующее значение лямбда-выражения в виде элемента массива. Это самая простая реализация этой функции, так как позволяет формировать только целочисленный массив.

    Для примера используем функцию ArrGen для формирования массива из 7 элементов, которые являются квадратами чисел 0 … 6, как представлено ниже.

Стандартный Паскаль	PascalABC.NET
var   M: array[1..10] of integer;   i: integer;   begin   for i := 0 to 6 do     M[i+1] := i * i;   for i := 1 to 7 do     Write(M[i], ' '); end.	## var M:=ArrGen(7,i -> i*i).Print;
Вывод: 0 1 4 9 16 25 36	Вывод: 0 1 4 9 16 25 36

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

 ArrGen(n: integer, Gen: i -> T, from: integer);

 ArrGen(n: integer, first: T, next: T -> T);

 ArrGen(n: integer, first: T, second: T, next:(T,T)->T);

    Первая вариация позволяет изменять первый элемент массива, например, если нужно начать массив не с нуля, а с двух:

 ArrGen(5, i -> i*i, 2); // 4 9 16 25 36

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

    Третья вариация функции ArrGen нужна, если необходимо использовать два начальных элемента first и second для формирования последующих элементов, которые формируются на основе двух предыдущих. То есть третий элемент получается из первого и второго элементов, четвёртый – из второго и третьего и так до конца массива. Использование функции также представлено ниже.

## ArrGen(5, 1.0, i -> i*2.3).Println; ArrGen(5, '', i -> i+'s').Println; ArrGen(10, 0, 1, (i,j) -> i+j).Print;
Вывод: 1 2.3 5.29 12.167 27.9841  s ss sss ssss 0 1 1 2 3 5 8 13 21 34

    Для быстрого и удобного формирования двумерных массивов можно использовать функции Matr(), MatrGen(), MatrRandom(), MatrRandomReal().

 Matr(m:integer, n:integer; params data: array of T): array[,] of T;

    Функция Matr работает в двух режимах:

 1) Matr принимает на вход целые числа m и n и массив data, из которого будет сформирован двумерный массив размерности m*n;

 2) Matr возвращает двумерный массив, созданный из одномерных массивов.

 MatrGen(m:integer, n:integer; gen:(integer,integer)->T): array[,] of T;

    Функция MatrGen также принимает два целых числа m и n, однако она использует генератор gen(i,j) для формирования элементов двумерного массива. Параметры i и j индексируют соответственно номер строки и номер столбца и начинаются с нуля. Также не обязательно использовать оба параметра для генерации, что продемонстрировано на рисунке 1.13.

 MatrRandom(n:integer, m:integer, a:integer, b:integer): array[,] of integer;

 MatrRandomReal(n:integer, m:integer, a:real, b:real): array[,] of integer;

    Обе функции возвращают двумерные массивы размерности n*m: первая функция заполняет матрицу целыми числами в диапазоне от a до b, а вторая заполняется матрицу уже вещественными числами в диапазоне от a до b.


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

    Последовательности – тип данных, привнесённый в PascalABC.NET из стандартной библиотеки платформы .NET. Эта структура данных является новой для языка, в традиционном Паскале подобного нет.

    Последовательности обладают большим количеством отличительных свойств, делающих их ещё более эффективными и удобными в использовании, чем, например, массивы. Многие перечислимые структуры, описанные ранее, такие как динамические массивы, кортежи, строки, могут быть преобразованы в последовательности.

    Описание последовательности похоже на описание динамического массива, за исключением того, что вместо ключевого слова «array» используется  «sequence». Например, последовательность вещественных чисел описывают следующим образом:

 var F: sequence of real;

    Какая-либо конструкция для инициализации последовательности не нужна, однако для последовательностей существует большой набор функций-генераторов, как и у массивов, только вместе префикса «Arr» в названии используется «Seq»: SeqFill(), SeqGen(), SeqRandomInteger(), SeqRandomReal().

    Функция Seq(a,b,…,z) позволяет сформировать последовательность из элементов a,b,c,…,z, например:

 var F:= Seq(2,6,4,2,3,5,3);

    Часто в задачах требуется работа с некоторой последовательностью возрастающих чисел, которую можно удобно записать двумя способами:

 1) С помощью конструкции (a..b), которая возвращает возрастающую последовательность целых чисел или символов типа Char от a до b включительно, как представлено на рисунке;

 2) С помощью функции Range(a:T,b:T,step:integer). Эта функция является более продвинутой версией вышеописанной конструкции, так как позволяет формировать последовательности целых чисел Integer, символов Char, а также чисел типа BigInteger. Вместе с этим можно указывать величину шага step, по умолчанию он равен 1.

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

 var F1:= SeqFill(1000000000,1);

 var F2:= ArrFill(1000000000,1);

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

    В случае с функцией SeqFill() никаких ошибок не возникает и последовательность успешно формируется, только в этой последовательности хранятся не миллиард единиц, а лишь информация о том, что при необходимости из этой последовательности можно извлечь миллиард элементов, каждый из которых будет равен единице

    Рассмотрим ещё некоторые отличия последовательностей от массивов.

    Во-первых, чтобы обратиться к элементу последовательности нужно использовать только метод ElementAt(i), в отличие от массивов, где допустимо использовать как квадратные скобки, так и метод ElementAt(i). Например, F.ElementAt(0) – обращение к первому элементу последовательности. Так же в случае подсчёта количества элементов последовательности используется метод Count, тогда как массивы могут использовать еще и метод Length.

    Такие структуры, как динамические массивы, строки, списки, являются производными от последовательностей, поэтому любую последовательность можно преобразовать в любую из этих структур, что позволяет использовать их специальные методы. Для преобразования в динамический массив нужен метод ToArray, в список –ToList, в строку – ToString.

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

Примеры генераций последовательностей

1) SeqFill( N:integer, X:T) - формирует последовательность из N элементов X типа данных T;

 var f:=SeqFill(1000,1); - заполнение последовательности 1000 единиц:
 [1,1,1,1,1,1,1,...]

2) SeqGen(N:integer, f:integer->T) - формирует последовательность из N элементов, которые являются значениями функции f(i) или лямбда-выражения i->g(i);
    По умолчанию нумерация начинается с "0", но можно начать нумерацию с любого номера, дописав после генерирующей функции f(i) через запятую номер k, где k-нужный номер, с которого должна начинаться последовательность;

 var f:=SeqFill(10, e->e**2); - формируется последовательность из 10 чисел, которые являются квадратами чисел от 0 до 9:
 [0,1,4,9,16,25,36,49,64,81]

 var g:=SeqFill(5, x->1/x, 1); - заполнение последовательности пятью обратными числами, начиная с 1, т.к. с 0 начинаться не может (деление на 0):
 [1,0.5,0.333..,0.25,0.2] 

3) SeqRandomInteger(N:integer, a:integer, b:integer) и SeqRandomReal(N:integer, a:real, b:real) формируют последовательности случайными целыми и вещественными числами соответственно. По умолчанию числа формируются из промежутка от 0 до 100, однако его можно поменять.

 var f:=SeqRandomInteger(10); - формирует последовательность из 10 целых чисел на промежутке от 0 до 100:
 [70,32,53,68,34,25,18,46,76,40] 

 var f:=SeqRandomReal(5,0,1); - формирует последовательность из 5 вещественных чисел на отрезке от 0 до 1:
 [0.0722617, 0.56489866, 0.3902090, 0.4512606, 0.7459797] 

Функция Range(a:[integer,BigInteger,char], b:[integer,BigInteger,char]) формирует последовательность элементов, начиная с a и заканчивая b, например:

 var f:=Range(-10,10);
 [-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10]

 var g:=Range('a','z');
 [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]