Общие замечания о формулировках заданий

Предисловие

Данные методические указания содержат формулировки 1000 учебных за- даний, охватывающих все темы базового курса программирования: от скаляр- ных типов и управляющих операторов до составных структур данных, рекур- сивных алгоритмов и указателей.

Задания составлены с учетом опыта проведения практических занятий по программированию на механико-математическом факультете Ростовского го- сударственного университета, а также на открытом факультете РГУ (компью- терные курсы для старшеклассников). При разработке заданий были использо- ваны материалы пособий [1–10] (список литературы приводится в третьей, за- ключительной части указаний).

Задания ориентированы на языки, традиционно используемые при началь- ном обучении программированию: Pascal, С++, Basic. Вместе с тем, для реше- ния большей части заданий можно применять и другие языки, например, For- tran или Java. При формулировке заданий не используются понятия и имена, специфические для конкретного языка программирования.

Имеется 18 групп заданий, каждая из которых снабжена особым именем

(нумерация заданий является независимой в каждой группе):

· «Ввод и вывод данных, оператор присваивания» (группа Begin, 40 заданий);

· «Целые числа» (группа Integer, 30 заданий);

· «Логические выражения» (группа Boolean, 40 заданий);

· «Условный оператор» (группа If, 30 заданий);

· «Оператор выбора» (группа Case, 20 заданий);

· «Цикл с параметром» (группа For, 40 заданий);

· «Цикл с условием» (группа While, 30 заданий);

· «Последовательности» (группа Series, 40 заданий);

· «Процедуры и функции» (группа Proc, 60 заданий);

· «Минимумы и максимумы» (группа Minmax, 30 заданий);

· «Одномерные массивы» (группа Array, 140 заданий);

· «Двумерные массивы (матрицы)» (группа Matrix, 100 заданий);

· «Символы и строки» (группа String, 70 заданий);

· «Двоичные (типизированные) файлы» (группа File, 90 заданий);

· «Текстовые файлы» (группа Text, 60 заданий);

 

 

· «Составные типы данных в процедурах и функциях» (группа Param, 70 заданий);

· «Рекурсия» (группа Recur, 30 заданий);

· «Указатели и динамические структуры данных» (группа Dynamic, 80 заданий).

Из-за большого объема задачник разбит на три части. Первая часть содер- жит задания начального уровня, посвященные скалярным типам данных, управ- ляющим операторам и разработке процедур и функций с числовыми парамет- рами (от группы Begin до группы Proc включительно); вторая и третья части содержат задания второй ступени, связанные, в основном, с изучением состав- ных типов данных (вторая часть содержит задания групп Minmax, Array, Matrix, String, File, а третья — задания оставшихся групп: Text, Param, Recur, Dynamic).

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

Задачник Programming Taskbook предоставляет учащимся следующие возможности:

· отображение на экране текста задания и связанных с ним данных;

· демонстрация правильных результатов для каждого задания;

· предоставление исходных данных программе учащегося;

· дополнительный контроль за операциями ввода-вывода;

· проверка правильности результатов, полученных программой;

· запись в особый файл результатов информации о каждом тестовом ис- пытании программы;

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

Важной особенностью электронного задачника Programming Taskbook является его независимость от конкретного языка и системы программирова- ния. Его версия 4.1 (последняя на момент опубликования данных указаний) по- зволяет выполнять задания в системах Borland Pascal 7.0 (для DOS), Borland Delphi 3.0–7.0, Borland C++Builder 4.0–5.0, Microsoft Visual C++ 6.0, Visual Basic 5.0–6.0 (без группы Dynamic, поскольку в языке Basic нет указателей). Кроме того, задачник может использоваться совместно с учебной системой программирования Pascal ABC, разработанной С. С. Михалковичем (см. [11]).

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

 

 

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

Получить электронный задачник Programming Taskbook можно у его ав- тора, обратившись по адресу [e-mail]. Дополнительная инфор- мация о задачнике содержится на веб-сайте

http://ptaskbook.com

Подробное описание порядка выполнения заданий с использованием вари- анта задачника Programming Taskbook для языка Pascal приводится в книгах [11, 12]. Эти книги содержат также указания к выполнению заданий и решения некоторых заданий. В данных методических указаниях формулировки решен- ных заданий помечены символом «º»; решения заданий начального уровня сле- дует искать в книге [11], а заданий второй ступени — в книге [12].

 

Обзор групп заданий

Две первые группы заданий знакомят с числовыми типами данных и опе- рациями над ними. В первой группе (Begin) основное внимание уделяется вво- ду-выводу и работе с переменными; в ней используется только данные вещест- венного типа. Во второй группе (Integer) рассматривается целый тип и особен- ности его использования, в частности, операции деления нацело и взятия остат- ка от деления.

Далее следуют группы заданий, посвященные управляющим конструкциям языка: Boolean (логические выражения), If (условный оператор), Case (опера- тор выбора), For (цикл с параметром), While (циклы с условием). Приведенный порядок их изучения не является единственно возможным. Например, в языках Pascal и Basic синтаксис цикла с параметром не требует использования логиче- ских выражений, поэтому группу For можно рассмотреть первой, и только по- сле этого перейти к логическим выражениям и условным операторам (такой подход используется в книге [11]). Следует заметить, что задания группы While подобраны таким образом, что при их выполнении не требуется использовать условные операторы. Поэтому после знакомства с логическими выражениями (группа Boolean) можно сразу перейти к использованию логических выраже- ний в циклах (группа While) и лишь после этого рассмотреть разветвляющиеся конструкции (группы If и Case). Возможен также подход, при котором логиче- ские выражения и условные операторы изучаются совместно в группе If, после чего вводится понятие логического типа данных и рассматриваются задания группы Boolean. Рассмотрение заключительной части заданий группы For, по- священной вложенным циклам, может быть отложено до знакомства с обработ- кой числовых последовательностей (группа Series); в этом случае задания на вложенные циклы из группы For следует рассмотреть непосредственно перед аналогичными заданиями группы Series.

 

 

Следующие две группы заданий — Series (последовательности) и Proc (процедуры и функции) — могут рассматриваться в любом порядке. Целью за- даний группы Series является ознакомление с совместным использованием различных управляющих конструкций в алгоритмах обработки числовых по- следовательностей, в то время как цель заданий группы Proc — научить «обер- тывать» различные алгоритмы в «оболочку» процедуры или функции (поэтому многие задания группы Proc являются простой переформулировкой заданий из предыдущих групп на «процедурном» языке).

Группа Minmax является естественным продолжением группы Series: в ней также рассматриваются алгоритмы обработки числовых последовательно- стей, однако в данной группе все эти алгоритмы связаны с нахождением экс- тремальных элементов последовательностей: минимумов и максимумов, в том числе условных. Следует подчеркнуть, что все задания групп Series и Minmax могут быть решены за однократный просмотр исходных данных, поэтому для их решения не требуется использовать массивы. В то же время, применение массивов делает решение некоторых заданий из этих групп существенно более простым, поэтому можно отложить рассмотрение таких заданий до изучения темы «Массивы» и выполнять их совместно с заданиями группы Array.

Группы заданий на составные типы данных — Array (одномерные масси- вы), Matrix (двумерные массивы), String (текстовые строки), File (двоичные файлы), Text (текстовые файлы) — должны выполняться в указанном порядке. Разделы «Серии целых чисел» и «Множества точек на плоскости» являются до- полнительными для группы Array; раздел «Использование файлов для работы с матрицами» является дополнительным для группы File.

Задания группы Param посвящены использованию составных типов дан- ных в процедурах и функциях. К этим заданиям можно перейти после рассмот- рения всех предыдущих групп; можно также включить их в изучение соответ- ствующей темы, рассмотрев раздел «Массивы» группы Param совместно с группами Array и Matrix, раздел «Строки» — с группой String, а раздел «Фай- лы» — с группами File и Text. Задания из раздела «Записи» полезно сравнить с аналогичными заданиями из дополнительного раздела группы Proc; это позво- лит подчеркнуть преимущества использования новых типов данных.

Группы заданий Recur (рекурсивные алгоритмы) и Dynamic (указатели и динамические структуры данных) могут рассматриваться в любом порядке. Ра- зумеется, группа Dynamic не может использоваться при изучении языка про- граммирования Basic, так как в нем отсутствуют указатели.

Заметим, что выполнение заданий на разработку процедур и функций для работы со стеками, очередями и списками (см. задания группы Dynamic с но- мерами 11–13, 26–28, 59–69 и 74–80) естественно подводит к созданию соот- ветствующих модулей и классов и рассмотрению различных аспектов модуль- ного и объектно-ориентированного программирования.

 

 

Целые числа: группа Integer

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

Integer1. Дано расстояние L в сантиметрах. Используя операцию деления наце- ло, найти количество полных метров в нем (1 метр = 100 см).

Integer2. Дана масса M в килограммах. Используя операцию деления нацело, найти количество полных тонн в ней (1 тонна = 1000 кг).

Integer3°. Дан размер файла в байтах. Используя операцию деления нацело, найти количество полных килобайтов, которые занимает данный файл (1 килобайт = 1024 байта).

Integer4. Даны целые положительные числа A и B (A > B). На отрезке длины A размещено максимально возможное количество отрезков длины B (без на- ложений). Используя операцию деления нацело, найти количество отрез- ков B, размещенных на отрезке A.

Integer5. Даны целые положительные числа A и B (A > B). На отрезке длины A размещено максимально возможное количество отрезков длины B (без на- ложений). Используя операцию взятия остатка от деления нацело, найти длину незанятой части отрезка A.

Integer6. Дано двузначное число. Вывести вначале его левую цифру (десятки), а затем — его правую цифру (единицы). Для нахождения десятков исполь- зовать операцию деления нацело, для нахождения единиц — операцию взятия остатка от деления.

Integer7. Дано двузначное число. Найти сумму и произведение его цифр.

Integer8°. Дано двузначное число. Вывести число, полученное при перестанов- ке цифр исходного числа.

Integer9. Дано трехзначное число. Используя одну операцию деления нацело, вывести первую цифру данного числа (сотни).

Integer10. Дано трехзначное число. Вывести вначале его последнюю цифру

(единицы), а затем — его среднюю цифру (десятки).

Integer11°. Дано трехзначное число. Найти сумму и произведение его цифр.

Integer12. Дано трехзначное число. Вывести число, полученное при прочтении исходного числа справа налево.

Integer13. Дано трехзначное число. В нем зачеркнули первую слева цифру и приписали ее справа. Вывести полученное число.

Integer14. Дано трехзначное число. В нем зачеркнули первую справа цифру и приписали ее слева. Вывести полученное число.

 

 

Integer15. Дано трехзначное число. Вывести число, полученное при переста- новке цифр сотен и десятков исходного числа (например, 123 перейдет в 213).

Integer16. Дано трехзначное число. Вывести число, полученное при переста- новке цифр десятков и единиц исходного числа (например, 123 перейдет в 132).

Integer17. Дано целое число, большее 999. Используя одну операцию деления нацело и одну операцию взятия остатка от деления, найти цифру, соответ- ствующую разряду сотен в записи этого числа.

Integer18. Дано целое число, большее 999. Используя одну операцию деления нацело и одну операцию взятия остатка от деления, найти цифру, соответ- ствующую разряду тысяч в записи этого числа.

Integer19. С начала суток прошло N секунд (N — целое). Найти количество полных минут, прошедших с начала суток.

Integer20°. С начала суток прошло N секунд (N — целое). Найти количество полных часов, прошедших с начала суток.

Integer21. С начала суток прошло N секунд (N — целое). Найти количество се- кунд, прошедших с начала последней минуты.

Integer22. С начала суток прошло N секунд (N — целое). Найти количество се- кунд, прошедших с начала последнего часа.

Integer23. С начала суток прошло N секунд (N — целое). Найти количество полных минут, прошедших с начала последнего часа.

Integer24. Дни недели пронумерованы следующим образом: 0 — воскресенье, 1 — понедельник, 2 — вторник, …, 6 — суббота. Дано целое число K, ле- жащее в диапазоне 1–365. Определить номер дня недели для K -го дня года, если известно, что в этом году 1 января было понедельником.

Integer25. Дни недели пронумерованы следующим образом: 0 — воскресенье, 1 — понедельник, 2 — вторник, …, 6 — суббота. Дано целое число K, ле- жащее в диапазоне 1–365. Определить номер дня недели для K -го дня года, если известно, что в этом году 1 января было четвергом.

Integer26. Дни недели пронумерованы следующим образом: 1 — понедельник, 2 — вторник, …, 6 — суббота, 7 — воскресенье. Дано целое число K, ле- жащее в диапазоне 1–365. Определить номер дня недели для K -го дня года, если известно, что в этом году 1 января было вторником.

Integer27. Дни недели пронумерованы следующим образом: 1 — понедельник, 2 — вторник, …, 6 — суббота, 7 — воскресенье. Дано целое число K, ле- жащее в диапазоне 1–365. Определить номер дня недели для K -го дня года, если известно, что в этом году 1 января было субботой.

 

 

Integer28. Дни недели пронумерованы следующим образом: 1 — понедельник, 2 — вторник, …, 6 — суббота, 7 — воскресенье. Дано целое число K, ле- жащее в диапазоне 1–365, и целое число N, лежащее в диапазоне 1–7. Оп- ределить номер дня недели для K -го дня года, если известно, что в этом году 1 января было днем недели с номером N.

Integer29°. Даны целые положительные числа A, B, C. На прямоугольнике раз- мера A ´ B размещено максимально возможное количество квадратов со стороной C (без наложений). Найти количество квадратов, размещенных на прямоугольнике, а также площадь незанятой части прямоугольника.

Integer30. Дан номер некоторого года (целое положительное число). Опреде- лить соответствующий ему номер столетия, учитывая, что, к примеру, на- чалом 20 столетия был 1901 год.

 

Содержание

Предисловие........................................................................................................ 3

1. Обзор групп заданий...................................................................................... 5

2. Общие замечания о формулировках заданий................................................ 7

3. Ввод и вывод данных, оператор присваивания: группа Begin................... 10

4. Целые числа: группа Integer......................................................................... 14

5. Логические выражения: группа Boolean...................................................... 16

6. Условный оператор: группа If...................................................................... 19

7. Оператор выбора: группа Case.................................................................... 21

8. Цикл с параметром: группа For................................................................... 23

9. Цикл с условием: группа While.................................................................... 27

10. Последовательности: группа Series............................................................ 30

11. Процедуры и функции: группа Proc.......................................................... 34

11.1. Процедуры с числовыми параметрами..................................................................... 34

11.2. Функции с числовыми параметрами.......................................................................... 36

11.3. Дополнительные задания на процедуры и функции............................................... 39

 

Предисловие

Данные методические указания содержат формулировки 1000 учебных за- даний, охватывающих все темы базового курса программирования: от скаляр- ных типов и управляющих операторов до составных структур данных, рекур- сивных алгоритмов и указателей.

Задания составлены с учетом опыта проведения практических занятий по программированию на механико-математическом факультете Ростовского го- сударственного университета, а также на открытом факультете РГУ (компью- терные курсы для старшеклассников). При разработке заданий были использо- ваны материалы пособий [1–10] (список литературы приводится в третьей, за- ключительной части указаний).

Задания ориентированы на языки, традиционно используемые при началь- ном обучении программированию: Pascal, С++, Basic. Вместе с тем, для реше- ния большей части заданий можно применять и другие языки, например, For- tran или Java. При формулировке заданий не используются понятия и имена, специфические для конкретного языка программирования.

Имеется 18 групп заданий, каждая из которых снабжена особым именем

(нумерация заданий является независимой в каждой группе):

· «Ввод и вывод данных, оператор присваивания» (группа Begin, 40 заданий);

· «Целые числа» (группа Integer, 30 заданий);

· «Логические выражения» (группа Boolean, 40 заданий);

· «Условный оператор» (группа If, 30 заданий);

· «Оператор выбора» (группа Case, 20 заданий);

· «Цикл с параметром» (группа For, 40 заданий);

· «Цикл с условием» (группа While, 30 заданий);

· «Последовательности» (группа Series, 40 заданий);

· «Процедуры и функции» (группа Proc, 60 заданий);

· «Минимумы и максимумы» (группа Minmax, 30 заданий);

· «Одномерные массивы» (группа Array, 140 заданий);

· «Двумерные массивы (матрицы)» (группа Matrix, 100 заданий);

· «Символы и строки» (группа String, 70 заданий);

· «Двоичные (типизированные) файлы» (группа File, 90 заданий);

· «Текстовые файлы» (группа Text, 60 заданий);

 

 

· «Составные типы данных в процедурах и функциях» (группа Param, 70 заданий);

· «Рекурсия» (группа Recur, 30 заданий);

· «Указатели и динамические структуры данных» (группа Dynamic, 80 заданий).

Из-за большого объема задачник разбит на три части. Первая часть содер- жит задания начального уровня, посвященные скалярным типам данных, управ- ляющим операторам и разработке процедур и функций с числовыми парамет- рами (от группы Begin до группы Proc включительно); вторая и третья части содержат задания второй ступени, связанные, в основном, с изучением состав- ных типов данных (вторая часть содержит задания групп Minmax, Array, Matrix, String, File, а третья — задания оставшихся групп: Text, Param, Recur, Dynamic).

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

Задачник Programming Taskbook предоставляет учащимся следующие возможности:

· отображение на экране текста задания и связанных с ним данных;

· демонстрация правильных результатов для каждого задания;

· предоставление исходных данных программе учащегося;

· дополнительный контроль за операциями ввода-вывода;

· проверка правильности результатов, полученных программой;

· запись в особый файл результатов информации о каждом тестовом ис- пытании программы;

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

Важной особенностью электронного задачника Programming Taskbook является его независимость от конкретного языка и системы программирова- ния. Его версия 4.1 (последняя на момент опубликования данных указаний) по- зволяет выполнять задания в системах Borland Pascal 7.0 (для DOS), Borland Delphi 3.0–7.0, Borland C++Builder 4.0–5.0, Microsoft Visual C++ 6.0, Visual Basic 5.0–6.0 (без группы Dynamic, поскольку в языке Basic нет указателей). Кроме того, задачник может использоваться совместно с учебной системой программирования Pascal ABC, разработанной С. С. Михалковичем (см. [11]).

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

 

 

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

Получить электронный задачник Programming Taskbook можно у его ав- тора, обратившись по адресу [e-mail]. Дополнительная инфор- мация о задачнике содержится на веб-сайте

http://ptaskbook.com

Подробное описание порядка выполнения заданий с использованием вари- анта задачника Programming Taskbook для языка Pascal приводится в книгах [11, 12]. Эти книги содержат также указания к выполнению заданий и решения некоторых заданий. В данных методических указаниях формулировки решен- ных заданий помечены символом «º»; решения заданий начального уровня сле- дует искать в книге [11], а заданий второй ступени — в книге [12].

 

Обзор групп заданий

Две первые группы заданий знакомят с числовыми типами данных и опе- рациями над ними. В первой группе (Begin) основное внимание уделяется вво- ду-выводу и работе с переменными; в ней используется только данные вещест- венного типа. Во второй группе (Integer) рассматривается целый тип и особен- ности его использования, в частности, операции деления нацело и взятия остат- ка от деления.

Далее следуют группы заданий, посвященные управляющим конструкциям языка: Boolean (логические выражения), If (условный оператор), Case (опера- тор выбора), For (цикл с параметром), While (циклы с условием). Приведенный порядок их изучения не является единственно возможным. Например, в языках Pascal и Basic синтаксис цикла с параметром не требует использования логиче- ских выражений, поэтому группу For можно рассмотреть первой, и только по- сле этого перейти к логическим выражениям и условным операторам (такой подход используется в книге [11]). Следует заметить, что задания группы While подобраны таким образом, что при их выполнении не требуется использовать условные операторы. Поэтому после знакомства с логическими выражениями (группа Boolean) можно сразу перейти к использованию логических выраже- ний в циклах (группа While) и лишь после этого рассмотреть разветвляющиеся конструкции (группы If и Case). Возможен также подход, при котором логиче- ские выражения и условные операторы изучаются совместно в группе If, после чего вводится понятие логического типа данных и рассматриваются задания группы Boolean. Рассмотрение заключительной части заданий группы For, по- священной вложенным циклам, может быть отложено до знакомства с обработ- кой числовых последовательностей (группа Series); в этом случае задания на вложенные циклы из группы For следует рассмотреть непосредственно перед аналогичными заданиями группы Series.

 

 

Следующие две группы заданий — Series (последовательности) и Proc (процедуры и функции) — могут рассматриваться в любом порядке. Целью за- даний группы Series является ознакомление с совместным использованием различных управляющих конструкций в алгоритмах обработки числовых по- следовательностей, в то время как цель заданий группы Proc — научить «обер- тывать» различные алгоритмы в «оболочку» процедуры или функции (поэтому многие задания группы Proc являются простой переформулировкой заданий из предыдущих групп на «процедурном» языке).

Группа Minmax является естественным продолжением группы Series: в ней также рассматриваются алгоритмы обработки числовых последовательно- стей, однако в данной группе все эти алгоритмы связаны с нахождением экс- тремальных элементов последовательностей: минимумов и максимумов, в том числе условных. Следует подчеркнуть, что все задания групп Series и Minmax могут быть решены за однократный просмотр исходных данных, поэтому для их решения не требуется использовать массивы. В то же время, применение массивов делает решение некоторых заданий из этих групп существенно более простым, поэтому можно отложить рассмотрение таких заданий до изучения темы «Массивы» и выполнять их совместно с заданиями группы Array.

Группы заданий на составные типы данных — Array (одномерные масси- вы), Matrix (двумерные массивы), String (текстовые строки), File (двоичные файлы), Text (текстовые файлы) — должны выполняться в указанном порядке. Разделы «Серии целых чисел» и «Множества точек на плоскости» являются до- полнительными для группы Array; раздел «Использование файлов для работы с матрицами» является дополнительным для группы File.

Задания группы Param посвящены использованию составных типов дан- ных в процедурах и функциях. К этим заданиям можно перейти после рассмот- рения всех предыдущих групп; можно также включить их в изучение соответ- ствующей темы, рассмотрев раздел «Массивы» группы Param совместно с группами Array и Matrix, раздел «Строки» — с группой String, а раздел «Фай- лы» — с группами File и Text. Задания из раздела «Записи» полезно сравнить с аналогичными заданиями из дополнительного раздела группы Proc; это позво- лит подчеркнуть преимущества использования новых типов данных.

Группы заданий Recur (рекурсивные алгоритмы) и Dynamic (указатели и динамические структуры данных) могут рассматриваться в любом порядке. Ра- зумеется, группа Dynamic не может использоваться при изучении языка про- граммирования Basic, так как в нем отсутствуют указатели.

Заметим, что выполнение заданий на разработку процедур и функций для работы со стеками, очередями и списками (см. задания группы Dynamic с но- мерами 11–13, 26–28, 59–69 и 74–80) естественно подводит к созданию соот- ветствующих модулей и классов и рассмотрению различных аспектов модуль- ного и объектно-ориентированного программирования.

 

 

Общие замечания о формулировках заданий

 

Числовые типы данных

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

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

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

Процедуры и функции

Если в используемом языке программирования отсутствует понятие «про- цедура», то под процедурой в формулировках заданий групп Proc, Param и Dynamic надо понимать функцию, не имеющую возвращаемого значения (на- пример, в C++ под процедурами надо понимать функции, возвращающие зна- чение типа void).

Массивы

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

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

 

 

Важно учитывать, что в некоторых языках программирования индексы элементов массивов могут отличаться от их порядковых номеров. В частности, индексация элементов массивов в языке C++ всегда начинается с нуля, поэтому элемент массива A с порядковым номером 1 (то есть первый элемент массива A, обозначаемый в формулировке заданий как A 1) в языке C++ имеет индекс 0 и обозначается в программе как A[0]. Аналогично, первый элемент мат- рицы B (находящийся в ее первой строке и первом столбце и обозначаемый в формулировке задания как B 1,1) в программе на C++ должен обозначаться как B[0][0].

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

Кроме того, в языке Basic можно использовать оператор задания по умол- чанию нижней границы диапазона индексов, равной 1:

Option Base 1

В тех языках, в которых нижний индекс массива жестко задан и равен ну- лю (например, С++), можно просто «игнорировать» элемент массива с индек- сом 0. Например, массив A размера 10 можно описать как массив, состоящий из 11 элементов, а данные в него вводить, начиная с элемента A[1]. При этом элемент A[0] оказывается «невостребованным» (хотя в некоторых алгоритмах он может пригодится в качестве вспомогательного «барьерного» элемента). Впрочем, для того, чтобы не нарушать стиль программирования, принятый в языках с жестко заданной нижней границей индексов, можно «примириться» с несогласованностью индексов и порядковых номеров элементов массивов и учитывать эту несогласованность при программной реализации алгоритмов.

Символы и строки

В языке Basic отсутствует символьный тип, поэтому для обработки симво- лов надо использовать строковые переменные единичной длины: String*1.

В языке C++ для работы со строками традиционно используется тип

char*, однако предпочтительнее использовать класс string из стандартной библиотеки.

Файлы

При изучении файлов вначале рассматриваются двоичные файлы (группа

File), а затем — текстовые (группа Text).

Под двоичным файлом понимается файл, содержащий элементы одного типа в специальном формате. В языке Pascal такие файлы называются типизи- рованными и описываются как file of < тип элемента >; в языке Basic — это файлы прямого доступа, описываемые с помощью атрибута Random. В

 

 

языке C++ для работы с двоичными файлами надо открывать их в режиме ios_base::binary; для чтения и записи элементов двоичных файлов в этом языке надо использовать методы read и write со списком параметров вида ((char *)&x, sizeof(x)), где x — переменная, тип которой совпадает с типом элементов двоичного файла.

Отдельный раздел в группе File посвящен обработке двоичных нетипизи- рованных файлов, для которых неизвестен тип входящих в них элементов (см. задания File42–File47). Для обработки таких файлов их можно рассматривать как последовательности байтов и побайтно их обрабатывать, считывая и запи- сывая данные по одному байту за одну операцию ввода–вывода (в языке Basic для работы с такими файлами предусмотрен режим Binary). В языке Pascal для обработки нетипизированных файлов эффективнее использовать тип file и специальные процедуры ввода–вывода BlockRead–BlockWrite.

Текстовые файлы представляют собой последовательности строк различ- ной длины, разделенные маркерами конца строки EOLN. В языке Pascal тексто- вые файлы описываются как Text, в языке Basic — как файлы последователь- ного доступа, открываемые в режиме Input, Output или Append. В языке C++ файлы по умолчанию открываются именно как текстовые.

В группе File имеется специальный раздел, посвященный строковым фай- лам. Строковые файлы являются частным случаем двоичных файлов; в отли- чие от текстовых файлов, для хранения строк в них выделяются участки памяти одинакового размера. Это позволяет использовать для обработки строковых файлов методы прямого доступа, однако делает невозможным их просмотр и редактирование в обычных текстовых редакторах. В языке Pascal строковые файлы описываются как file of string (в Borland Delphi необходимо ис- пользовать описание file of ShortString). В языке Basic строковые фай- лы надо описывать как файлы прямого доступа (открытые в режиме Random) с элементами-строками фиксированного размера, например, String*80. В язы- ке C++ строковые файлы, как любые двоичные файлы, должны открываться в режиме ios_base::binary и иметь в качестве элементов строки фиксиро- ванного размера, например, char[80].

Под размером двоичного типизированного файла всегда подразумевается количество содержащихся в нем элементов указанного типа (а не количество байтов, как это принято в операционной системе). Как и для элементов массива, для элементов файла в формулировках заданий применяется «естественная» нумерация: первый элемент файла имеет порядковый номер 1. Это следует учи- тывать при организации перемещения к элементу с требуемым номером; в ча- стности, в языке Pascal для перехода к K -му элементу файла F необходимо вы- звать процедуру Seek(F, K–1).

 

 

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

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

Указатели

В заданиях этой группы используется особые типы данных: записи типа TNode и указатели на них типа PNode. Описание этих типов на языках Pascal и C++ приводится в начале раздела «Указатели». При использовании электронно- го задачника Programming Taskbook эти типы не следует описывать в про- грамме учащегося, так как они уже описаны в модулях задачника, подключае- мых к программе.

Для нулевого указателя в формулировках заданий используется обозначе- ние nil, заимствованное из языка Pascal.

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