Методические указания для студентов механикоматематического, физического и экономического факультетов РостовнаДону 2004
 Скачать 0.6 Mb.
|
|
Министерство образования и науки Российской Федерации Государственное образовательное учреждение профессионального образования Российской Федерации «Ростовский государственный университет» М. Э. Абрамян 1000 ЗАДАЧ ПО ПРОГРАММИРОВАНИЮ Часть I Скалярные типы данных, управляющие операторы, процедуры и функции Методические указания для студентов механико-математического, физического и экономического факультетов Ростов-на-Дону 2004 Печатается по решению кафедры алгебры и дискретной математики механико-математического факультета РГУ от 14 июня 2004 г. (протокол № 10) Р е ц е н з е н т ы : к. ф.-м. н., доцент Столяр А. М., к. ф.-м. н., доцент Чечин Г. М., ст. преп. Мачулина Л. А. Аннотация Первая часть сборника учебных заданий по программированию содержит задания начального уровня, посвященные скалярным типам данных, управ- ляющим операторам и разработке процедур и функций с числовыми парамет- рами. Задания формулируются таким образом, что их можно использовать при изучении любого из распространенных языков программирования, в частности, Pascal, C++, Basic. Сборник предназначен для студентов механико-математического, физиче- ского и экономического факультетов. Автор: М. Э. Абрамян. © М. Э. Абрамян, 2004 3 Предисловие Данные методические указания содержат формулировки 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 заданий); 4 • «Составные типы данных в процедурах и функциях» (группа Param, 70 заданий); • «Рекурсия» (группа Recur, 30 заданий); • «Указатели и динамические структуры данных» (группа Pointer, 80 заданий). Из-за большого объема задачник разбит на три части. Первая часть содер- жит задания начального уровня, посвященные скалярным типам данных, управ- ляющим операторам и разработке процедур и функций с числовыми парамет- рами (от группы Begin до группы Proc включительно); вторая и третья части содержат задания второй ступени, связанные, в основном, с изучением состав- ных типов данных (вторая часть содержит задания групп Minmax, Array, Matrix, String, File, а третья — задания оставшихся групп: Text, Param, Recur, Pointer). Для более эффективной организации практикума по программированию автором разработан электронный задачник 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 (без группы Pointer, поскольку в языке Basic нет указателей). Кроме того, задачник может использоваться совместно с учебной системой программирования Pascal ABC, разработанной С. С. Михалковичем (см. [11]). Использование электронного задачника существенно ускоряет процесс выполнения заданий, так как избавляет учащегося от дополнительных усилий по организации ввода-вывода, что особенно удобно при обработке массивов, строк, файлов и динамических структур. Предоставляя учащемуся готовые ис- ходные данные, задачник акцентирует его внимание на разработке и программ- 5 ной реализации алгоритма решения задания, причем разнообразие исходных данных обеспечивает надежное тестирование предложенного алгоритма. Получить электронный задачник Programming Taskbook можно у его ав- тора, обратившись по адресу mabr@math.rsu.ru. Дополнительная инфор- мация о задачнике содержится на веб-сайте http://sunschool.math.rsu.ru Подробное описание порядка выполнения заданий с использованием вари- анта задачника Programming Taskbook для языка Pascal приводится в книгах [11, 12]. Эти книги содержат также указания к выполнению заданий и решения некоторых заданий. В данных методических указаниях формулировки решен- ных заданий помечены символом «º»; решения заданий начального уровня сле- дует искать в книге [11], а заданий второй ступени — в книге [12]. 1 Обзор групп заданий Две первые группы заданий знакомят с числовыми типами данных и опе- рациями над ними. В первой группе (Begin) основное внимание уделяется вво- ду-выводу и работе с переменными; в ней используется только данные вещест- венного типа. Во второй группе (Integer) рассматривается целый тип и особен- ности его использования, в частности, операции деления нацело и взятия остат- ка от деления. Далее следуют группы заданий, посвященные управляющим конструкциям языка: Boolean (логические выражения), If (условный оператор), Case (опера- тор выбора), For (цикл с параметром), While (циклы с условием). Приведенный порядок их изучения не является единственно возможным. Например, в языках Pascal и Basic синтаксис цикла с параметром не требует использования логиче- ских выражений, поэтому группу For можно рассмотреть первой, и только по- сле этого перейти к логическим выражениям и условным операторам (такой подход используется в книге [11]). Следует заметить, что задания группы While подобраны таким образом, что при их выполнении не требуется использовать условные операторы. Поэтому после знакомства с логическими выражениями (группа Boolean) можно сразу перейти к использованию логических выраже- ний в циклах (группа While) и лишь после этого рассмотреть разветвляющиеся конструкции (группы If и Case). Возможен также подход, при котором логиче- ские выражения и условные операторы изучаются совместно в группе If, после чего вводится понятие логического типа данных и рассматриваются задания группы Boolean. Рассмотрение заключительной части заданий группы For, по- священной вложенным циклам, может быть отложено до знакомства с обработ- кой числовых последовательностей (группа Series); в этом случае задания на вложенные циклы из группы For следует рассмотреть непосредственно перед аналогичными заданиями группы Series. 6 Следующие две группы заданий — 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 (рекурсивные алгоритмы) и Pointer (указатели и динамические структуры данных) могут рассматриваться в любом порядке. Ра- зумеется, группа Pointer не может использоваться при изучении языка про- граммирования Basic, так как в нем отсутствуют указатели. Заметим, что выполнение заданий на разработку процедур и функций для работы со стеками, очередями и списками (см. задания группы Pointer с номе- рами 11–13, 26–28, 59–69 и 74–80) естественно подводит к созданию соответст- вующих модулей и классов и рассмотрению различных аспектов модульного и объектно-ориентированного программирования. 7 2 Общие замечания о формулировках заданий Числовые типы данных Если о типе исходных или результирующих числовых данных в задании ничего не сказано, то предполагаются вещественные данные. Исключение со- ставляет группа заданий Pointer, в которой все числовые данные считаются це- лыми, и в формулировках заданий это особо не оговаривается. При обработке наборов вещественных чисел всюду предполагается, что все элементы набора являются различными; в частности, считается, что любой на- бор вещественных чисел содержит единственный минимальный и единствен- ный максимальный элемент. В этом состоит основное отличие наборов вещест- венных чисел от наборов целых чисел, в которых могут присутствовать одина- ковые элементы. Разумеется, при вводе исходных вещественных данных с кла- виатуры можно добиться того, что какие-либо вещественные данные окажутся одинаковыми, однако в этой ситуации многие задания на обработку наборов вещественных данных окажутся некорректно сформулированными. Для того, чтобы элементы наборов вещественных чисел были различными, можно использовать датчик случайных чисел. Именно так организована гене- рация исходных данных в электронном задачнике Programming Taskbook. Процедуры и функции Если в используемом языке программирования отсутствует понятие «про- цедура», то под процедурой в формулировках заданий групп Proc, Param и Pointer надо понимать функцию, не имеющую возвращаемого значения (напри- мер, в C++ под процедурами надо понимать функции, возвращающие значение типа void). Массивы Если в задании не указан максимальный размер исходных массивов, то его можно считать равным 10 для одномерных и 10 × 10 для двумерных массивов. При описании элементов одномерных и двумерных массивов используется понятие порядкового номера элемента, причем начальный элемент массива A размера N всегда имеет порядковый номер 1 и обозначается в формулировках заданий как A 1 , а конечный элемент этого же массива имеет порядковый номер N и обозначается как A N . Аналогично, начальный элемент двумерного массива B обозначается как B 1,1 . Кроме того, понятие порядкового номера применяется к строкам и столбцам двумерных массивов (матриц): начальная строка и на- чальный столбец матрицы размера M × N имеют порядковый номер 1, конечная строка — номер M, а конечный столбец — номер N. Подобный подход не зави- сит от выбора языка программирования и соответствует традиции, принятой в математике для нумерации элементов векторов и матриц. 8 Важно учитывать, что в некоторых языках программирования индексы элементов массивов могут отличаться от их порядковых номеров. В частности, индексация элементов массивов в языке 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. В 9 языке 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 имеется специальный раздел, посвященный строковым фай- лам. Строковые файлы являются частным случаем двоичных файлов; в отли- чие от текстовых файлов, для хранения строк в них выделяются участки памяти |