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

Министерство образования и науки Российской Федерации 

Федеральное государственное автономное образовательное  
учреждение высшего профессионального образования 
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» 

М. Э. Абрамян 

ПРАКТИКУМ 

ПО ПРОГРАММИРОВАНИЮ 

НА ЯЗЫКЕ ПАСКАЛЬ 

Массивы, строки, файлы, рекурсия,  
линейные динамические структуры,  
бинарные деревья 

Издание седьмое, переработанное и дополненное 

Ростов-на-Дону   2010 

УДК   004.438(076.5) 
ББК  32.973.26-018.1я73 
           А 16 
 
 
Печатается по решению редакционно-издательского совета 
Южного федерального университета 
 
Рецензент: 
к. ф.-м. н., доцент кафедры алгебры и дискретной 
математики факультета математики, механики и компьютерных наук 
Южного федерального университета С. С. Михалкович 
 
 
Учебное пособие подготовлено и издано в рамках национального проекта 
 «Образование» по «Программе развития федерального государственного  
образовательного учреждения высшего профессионального образования  
«Южный федеральный университет» на 2007-2010 гг.» 
 
 
 
 
            Абрамян М. Э. 
А16   Практикум по программированию на языке Паскаль: Массивы, строки, файлы, 
рекурсия, линейные динамические структуры, бинарные деревья. – 7-е изд., 
перераб. и доп.  – Ростов н/Д.: Изд-во ЮФУ, 2010. – 276 с.: ил. 
 
ISBN 978-5-9275-0801-3 
 
 
Учебное пособие содержит 770 заданий по программированию и указания по 
их выполнению в средах Borland Delphi, Free Pascal Lazarus и PascalABC.NET. 
Приводятся решения типовых задач и необходимый справочный материал. 
Для преподавателей программирования, старшеклассников и студентов. 
 
 
 
 
 
 
 
ISBN 978-5-9275-0801-3 
 
 
 
 
       УДК   004.438(076.5) 
ББК  32.973.26-018.1я73 
 
 
 
 
 
 
© М. Э. Абрамян, 2010 
© Оформление. Макет. Издательство 
Южного федерального университета, 2010 

Предисловие 

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

Задания составлены с учетом опыта проведения практических занятий 
по программированию на факультете математики, механики и компьютерных наук Южного федерального университета, а также в Компьютерной 
школе при мехмате ЮФУ. При разработке заданий были использованы материалы пособий [1, 11, 13, 15–18, 20, 22, 25, 26, 28].  

В первой части пособия приводятся формулировки учебных заданий. 
Задания разбиты на десять групп. Первая группа (Minmax) содержит 
30 заданий, связанных с нахождением минимумов и максимумов. Следующие две группы заданий (Array, 140 заданий, и Matrix, 100 заданий) знакомят с приемами обработки одномерных и двумерных числовых массивов, а 
четвертая группа (String) содержит 70 заданий на обработку символов и 
строк. Пятая и шестая группы посвящены обработке файлов: типизированных (File, 90 заданий) и текстовых (Text, 60 заданий). Седьмая и восьмая группы связаны с процедурами и функциями: группа Param 
(70 заданий) посвящена использованию в процедурах и функциях сложных 
типов данных (массивов, строк, файлов и записей), а группа Recur содержит 30 заданий на разработку рекурсивных алгоритмов. Две последние 
группы заданий посвящены динамическим структурам: в девятой группе 
(Dynamic, 80 заданий) рассматриваются линейные динамические структуры (стек, очередь, двусвязный список), а в десятой (Tree, 100 заданий) — 
бинарные деревья. Формулировки всех заданий из настоящего пособия 
(кроме группы Tree) приводятся также в методических указаниях [4, 5].  

Вторая часть пособия содержит указания и примеры решения типовых 
задач. Указания и примеры ориентированы на современные диалекты Паскаля: язык Delphi Pascal, реализованный в системах Borland Delphi 7.0,  
Turbo Delphi 2006 и Free Pascal Lazarus 0.9, и язык PascalABC.NET, реализованный в одноименной программной системе (данная система разрабатывается на мехмате ЮФУ под руководством доц. С. С. Михалковича;  
ее сайт — http://pascalabc.net/). В пособии рассматривается версия 1.5 
системы PascalABC.NET. 

В третьей части пособия содержатся справочные сведения по языкам 
Delphi Pascal и PascalABC.NET, которые могут оказаться полезными при 

Предисловие 

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

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

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

• регистрация задания как выполненного после проведения серии успешных тестовых испытаний. 

Кроме заданий, приведенных в настоящем пособии, задачник Programming Taskbook содержит 330 заданий начального уровня, посвященных скалярным типам данных, управляющим операторам и разработке 
процедур и функций с числовыми параметрами [3, 10].  

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

Подробное описание процесса выполнения заданий с использованием 
задачника Programming Taskbook приводится в п. 13.1; сам задачник описывается в п. 17. Дополнительную информацию о задачнике Programming 
Taskbook можно получить на сайте http://ptaskbook.com/.  

В настоящем, седьмом издании пособия формулировки простых задач 
и задач повышенной сложности снабжены специальными пометками, расширен раздел, посвященный решениям задач, и добавлено описание отладочных возможностей, появившихся в версии 4.9 задачника Programming 
Taskbook. Кроме того, исключена из рассмотрения система Pascal ABC, 
поддержка которой была прекращена в 2007 г., а к набору рассматриваемых реализаций языка Delphi Pascal добавлена система Free Pascal Lazarus. 

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

Часть I 

Учебные задания 
 

1.  Предварительные замечания 

Если о типе исходных или результирующих числовых данных в задании ничего не сказано, то предполагаются вещественные данные. Исключение составляют группы заданий Dynamic и Tree (п. 10–11), в которых все 
числовые данные считаются целыми и в формулировках заданий это особо 
не оговаривается.  

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

Если в задании не указан максимальный размер исходных массивов, 
то его надо считать равным 10 для одномерных и 10 × 10 для двумерных 
массивов. 

При описании элементов одномерных и двумерных массивов используется понятие порядкового номера элемента, причем начальный элемент 
массива A размера N всегда имеет порядковый номер 1 и обозначается  
в формулировках заданий как A1, а конечный элемент этого же массива 
имеет порядковый номер N и обозначается как AN. Аналогично, начальный 
элемент двумерного массива B обозначается как B1,1. Кроме того, понятие 
порядкового номера применяется к строкам и столбцам двумерных массивов (матриц): начальная строка и начальный столбец матрицы размера 
M × N имеют порядковый номер 1, конечная строка — номер M, а конечный столбец — номер N. В языке Паскаль легко добиться того, чтобы порядковый номер элемента массива совпадал с его индексом; для этого достаточно при описании массивов использовать начальное значение индекса, 
равное 1. 

Максимальный размер исходных файлов не указывается, поэтому при 
решении задач на файлы не следует использовать вспомогательные массивы, содержащие все элементы исходных файлов, однако допускается использование вспомогательных файлов (см. решения задач File25 в п. 13.5.2 
и Text21 в п. 13.6.3). Все исходные файлы считаются существующими  
и непустыми, за исключением специально оговоренных случаев (см. File4, 

Часть I. Учебные задания 

File5, File9, Param48–Param50), в которых существование исходных файлов 
требуется проверять в ходе выполнения задания. 

При выполнении заданий с использованием электронного задачника  
Programming Taskbook (см. п. 17) нужно учитывать дополнительные условия: 

• данные целого типа должны описываться как integer, данные вещественного типа — как real, символьные данные — как char, строковые данные — как string; аналогичные типы необходимо использовать при описании типизированных файлов, за исключением  
типизированных строковых файлов, которые в языках Delphi Pascal  
и PascalABC.NET надо описывать как file of ShortString; 

• типы PNode и TNode, используемые при выполнении заданий групп  
Dynamic и Tree, в программе описывать не следует, так как они уже 
описаны в модуле PT4, подключаемом к программе (см. п. 17.2). 

Символом «■», указанным после имени задания, отмечены простые задачи, символом «*» — задачи повышенной сложности. Особо сложные задачи отмечены двумя звездочками. Дополнительный символ «º» означает, 
что решение задачи приведено во второй части пособия (п. 13). 

2.  Минимумы и максимумы: группа Minmax 

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

Во всех задачах данной группы предполагается, что исходный набор 
содержит ненулевое количество элементов (в частности, число N всегда 
больше нуля). 
Minmax1■°. Дано целое число N и набор из N чисел. Найти минимальный  
и максимальный из элементов данного набора и вывести их в указанном порядке. 

Minmax2■. Дано целое число N и набор из N прямоугольников, заданных 
своими сторонами — парами чисел (a, b). Найти минимальную площадь прямоугольника из данного набора. 

Minmax3■. Дано целое число N и набор из N прямоугольников, заданных 
своими сторонами — парами чисел (a, b). Найти максимальный периметр прямоугольника из данного набора. 

Minmax4■. Дано целое число N и набор из N чисел. Найти номер минимального элемента из данного набора. 

Minmax5■. Дано целое число N и набор из N пар чисел (m, v) — данные  
о массе m и объеме v деталей, изготовленных из различных материа

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

P = m/v. 

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

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

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

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

Minmax10. Дано целое число N и набор из N целых чисел. Найти номер 
первого экстремального (т. е. минимального или максимального) элемента из данного набора. 

Minmax11. Дано целое число N и набор из N целых чисел. Найти номер 
последнего экстремального (т. е. минимального или максимального) 
элемента из данного набора. 

Minmax12. Дано целое число N и набор из N чисел. Найти минимальное 
положительное число из данного набора. Если положительные числа в 
наборе отсутствуют, то вывести 0. 

Minmax13. Дано целое число N и набор из N целых чисел. Найти номер 
первого максимального нечетного числа из данного набора. Если нечетные числа в наборе отсутствуют, то вывести 0. 

Minmax14. Дано число B (> 0) и набор из десяти чисел. Вывести минимальный из тех элементов набора, которые больше B, а также его номер. Если чисел, больших B, в наборе нет, то дважды вывести 0. 

Minmax15. Даны числа B, C (0 < B < C) и набор из десяти чисел. Вывести 
максимальный из элементов набора, содержащихся в интервале (B, C), 
и его номер. Если требуемые числа в наборе отсутствуют, то дважды 
вывести 0. 

Minmax16. Дано целое число N и набор из N целых чисел. Найти количество элементов, расположенных перед первым минимальным элементом. 

Minmax17. Дано целое число N и набор из N целых чисел. Найти количество элементов, расположенных после последнего максимального 
элемента. 

Minmax18. Дано целое число N и набор из N целых чисел. Найти количество элементов, содержащихся между первым и последним макси

Часть I. Учебные задания 

мальным элементом. Если в наборе имеется единственный максимальный элемент, то вывести 0. 

Minmax19. Дано целое число N и набор из N целых чисел. Найти количество минимальных элементов из данного набора. 

Minmax20. Дано целое число N и набор из N целых чисел. Найти общее 
количество экстремальных (т. е. минимальных и максимальных) элементов из данного набора. 

Minmax21. Дано целое число N (> 2) и набор из N чисел — значений 
некоторой величины, полученных в N опытах. Найти среднее значение 
этой величины. При вычислении среднего значения не учитывать минимальное и максимальное из имеющихся в наборе значений. 

Minmax22. Дано целое число N (> 2) и набор из N чисел. Найти два наименьших элемента из данного набора и вывести эти элементы в порядке возрастания их значений. 

Minmax23. Дано целое число N (> 3) и набор из N чисел. Найти три наибольших элемента из данного набора и вывести эти элементы в порядке убывания их значений. 

Minmax24. Дано целое число N (> 1) и набор из N чисел. Найти максимальную сумму двух соседних чисел из данного набора. 

Minmax25. Дано целое число N (> 1) и набор из N чисел. Найти номера 
двух соседних чисел из данного набора, произведение которых является минимальным, и вывести вначале меньший, а затем больший номер. 

Minmax26*. Дано целое число N и набор из N целых чисел. Найти максимальное количество четных чисел в наборе, идущих подряд. Если четные числа в наборе отсутствуют, то вывести 0. 

Minmax27*. Дано целое число N и набор из N целых чисел, содержащий 
только нули и единицы. Найти номер элемента, с которого начинается 
самая длинная последовательность одинаковых чисел, и количество 
элементов в этой последовательности. Если таких последовательностей несколько, то вывести номер первой из них. 

Minmax28*. Дано целое число N и набор из N целых чисел, содержащий 
только нули и единицы. Найти номер элемента, с которого начинается 
самая длинная последовательность единиц, и количество элементов в 
этой последовательности. Если таких последовательностей несколько, 
то вывести номер последней из них. Если единицы в исходном наборе 
отсутствуют, то дважды вывести 0. 

Minmax29*. Дано целое число N и набор из N целых чисел. Найти максимальное количество подряд идущих минимальных элементов из данного набора. 

Minmax30*. Дано целое число N и набор из N целых чисел. Найти минимальное количество подряд идущих максимальных элементов из данного набора. 

3.  Одномерные массивы: группа Array 

Условие вида «дан массив размера N» означает, что вначале дается 
фактический размер массива (целое число N), а затем приводятся все его 
элементы. Если в задании явно не указывается, какие значения может принимать размер исходного массива, то предполагается, что размер может 
изменяться в пределах от 2 до 10. Порядковый номер начального элемента 
массива считается равным 1. 

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

3.1.  Формирование массива и вывод его элементов 

В заданиях на формирование массива предполагается, что размер результирующего массива не превосходит 10. 
Array1■. Дано целое число N (> 0). Сформировать и вывести целочисленный массив размера N, содержащий N первых положительных нечетных чисел: 1, 3, 5, … . 

Array2■. Дано целое число N (> 0). Сформировать и вывести целочисленный массив размера N, содержащий степени двойки от первой до N-й: 
2, 4, 8, 16, … . 

Array3. Дано целое число N (> 1), а также первый член A и разность D 
арифметической прогрессии. Сформировать и вывести массив размера N, содержащий N первых членов данной прогрессии:  

A,    A + D,    A + 2D,    A + 3D,    … . 

Array4. Дано целое число N (> 1), а также первый член A и знаменатель D 
геометрической прогрессии. Сформировать и вывести массив размера N, содержащий N первых членов данной прогрессии:  

A,    A·D,    A·D2,    A·D3,    … . 

Array5. Дано целое число N (> 2). Сформировать и вывести целочисленный 
массив размера N, содержащий N первых элементов последовательности чисел Фибоначчи FK:  

F1 = 1,        F2 = 1,        FK = FK–2 + FK–1,    K = 3, 4, … . 

Array6. Даны целые числа N (> 2), A и B. Сформировать и вывести целочисленный массив размера N, первый элемент которого равен A, второй равен B, а каждый последующий элемент равен сумме всех предыдущих. 

Array7■°. Дан массив размера N. Вывести его элементы в обратном порядке. 

Array8. Дан целочисленный массив размера N. Вывести все содержащиеся 
в данном массиве нечетные числа в порядке возрастания их индексов, 
а также их количество K. 

Часть I. Учебные задания 

Array9. Дан целочисленный массив размера N. Вывести все содержащиеся 
в данном массиве четные числа в порядке убывания их индексов,  
а также их количество K. 

Array10. Дан целочисленный массив размера N. Вывести вначале все содержащиеся в данном массиве четные числа в порядке возрастания их 
индексов, а затем — все нечетные числа в порядке убывания их индексов. 

Array11. Дан массив A размера N и целое число K (1 ≤ K ≤ N). Вывести элементы массива с порядковыми номерами, кратными K: AK, A2K, A3K, … . 
Условный оператор не использовать. 

Array12. Дан массив A размера N (N — четное число). Вывести его элементы с четными номерами в порядке возрастания номеров: A2, A4,  
A6, …, AN. Условный оператор не использовать. 

Array13. Дан массив A размера N (N — нечетное число). Вывести его элементы с нечетными номерами в порядке убывания номеров: AN, AN–2, 
AN–4, …, A1. Условный оператор не использовать. 

Array14*. Дан массив A размера N. Вывести вначале его элементы с четными номерами (в порядке возрастания номеров), а затем — элементы 
с нечетными номерами (также в порядке возрастания номеров):  

A2,    A4,    A6,    …,    A1,    A3,    A5,    … . 

Условный оператор не использовать. 

Array15*. Дан массив A размера N. Вывести вначале его элементы  
с нечетными номерами в порядке возрастания номеров, а затем — 
элементы с четными номерами в порядке убывания номеров:  

A1,    A3,    A5,    …,    A6,    A4,    A2. 

Условный оператор не использовать. 

Array16*. Дан массив A размера N. Вывести его элементы в следующем 
порядке:  

A1,    AN,    A2,    AN–1,    A3,    AN–2,    … . 

Array17*. Дан массив A размера N. Вывести его элементы в следующем 
порядке:  

A1,    A2,    AN,    AN–1,    A3,    A4,    AN–2,    AN–3,    … . 

3.2.  Анализ элементов массива 

Для выполнения некоторых заданий из данного раздела не требуется 
одновременно хранить в памяти все исходные данные, поэтому использовать при их выполнении массивы, строго говоря, не нужно. Однако применение массивов позволяет сделать алгоритмы решения этих задач более 
простыми и наглядными. Задачи из данного раздела можно дополнить задачами из группы Minmax, рассматривая их как задания на обработку массивов. С другой стороны, для тех задач данного раздела, которые можно 
выполнить, не используя массивы, полезно реализовать и такие алгоритмы 
решения.