материал по информатике Задачи по программированию

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

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

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

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

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

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

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

Массивы

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

При описании элементов одномерных и двумерных массивов используется понятие порядкового номера элемента, причем начальный элемент массива A размера N всегда имеет порядковый номер 1 и обозначается в формулировках заданий как A₁, а конечный элемент этого же массива имеет порядковый номер N и обозначается как A_N. Аналогично, начальный элемент двумерного массива B обозначается как B_1,1. Кроме того, понятие порядкового номера применяется

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

8

Важно учитывать, что в некоторых языках программирования индексы элементов массивов могут отличаться от их порядковых номеров. В частности, индексация элементов массивов в языке C++ всегда начинается с нуля, поэтому элемент массива A с порядковым номером 1 ( то есть первый элемент массива A, обозначаемый в формулировке заданий как A₁) в языке 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 имеется специальный раздел, посвященный строковым фай-лам. Строковые файлы являются частным случаем двоичных файлов; в отли-чие от текстовых файлов, для хранения строк в них выделяются участки памяти одинакового размера. Это позволяет использовать для обработки строковых файлов методы прямого доступа, однако делает невозможным их просмотр и редактирование в обычных текстовых редакторах. В языке 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).

10

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

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

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

Указатели

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

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

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