Основы программирования (947332), страница 32

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 32)

lOOJ of integer;Varpole:p;km: integer;{функция проверки перспективности комбинации}Function new_r(n:integer;poIe:p):boolean;Varj:integer;Beginnewjr:-false;for j:-l to n-1 doif (pole lj]'='pole[n])or(abs(pole[j]-pole[n])=n-j) then exit;newJ*:-true;End;{рекурсивная функция генерации комбинации}Procedure ferz(n,m:integer; varpole:p);Var i: integer;185Часть 1. Основы алгоритмизации и процедурное программированиеC(/Начало jВводnewr "\(n,pole) JV(n,m,pole)ynew r=trueУL—JZ—Jferz(l,m,poIe)Г КонецjРис.

5.21. Алгоритмы основной программы {а),функции проверки перспективности полученной комбинации (б)и рекурсивной процедуры добавления ферзя {в)Beginifn=m+I then {если установлено m ферзей, то вывести решение}beginfor i:=J to m do Write (pole[ij: 2);WriteLn;endelse{иначе - пытаемся установить следующего ферзя}for i:=I to m do {m способами}beginpole[nJ:=i; {установка п-го ферзя}if new_r(n,pole){проверка перспективности комбинации}thenferz(n'^l,m,pole); {рекурсивный вызов установкиследующего ферзя}end;End;{основная программа}BeginWriteLn('Beedume размер доски: *);ReadLn(m);1865. Модульное программированиеТ а б л и ц а 5.1Размер доскиКоличество вариантов, Количество вариантов,которое проверяетсярассмотренных припри полном переборе ограниченном перебореКоличествополученныхрешений4x444 = 2561725x555 = 312554106x666 = 4665615347x7V = 823543552408x888=16777216205792к:=0;ferz(hmypole);End,Процедуру new_r используют для проверки уже сгенерированной ком­бинации (уровень п соответствует попытке установить п-го ферзя).

Процеду­ра ferz рекурсивна. На каждом уровне она может породить до m рекурсивныхвызовов (в соответствии с деревом генерации вариантов). Однако общее ко­личество рассматриваемых вариантов резко уменьшается, так как неперспек­тивные комбинации отсекаются, что наглядно представлено в табл. 5.1.Задания для самопроверкиЗадание I. Разработайте рекурсивную подпрофамму, осуществляющую поисккомбинации для отпирания кодового замка по методу перебора с отсечением непер­спективных комбинаций. Замок представляет собой набор из п переключателей, каж­дый из которых может находиться в положении «включено» или «выключено».

За­мок открывается при одном положении переключателей, причем в положении«включено» может находиться не более половины переключателей.Задание 2. Разработайте рекурсивную подпрограмму, которая формирует из за­данного списка предметов определенной стоимости и веса набор, вес которого непревышает заданного, а стоимость максимальна.1876. ФАЙЛОВАЯ СИСТЕМА, ФАЙЛЫФайлам называют именованную последовательность элементов данных (компо­нент файла), расположенных, как правило, во внешней памяти: на дискетах, винчестере,CD или других устройствах хранения информации, также устройствах ввода-вывода. Вфайле может храниться текст, программа, числовые данные, фафическое изображение ит.д. Для организации работы с файлами профамма на Borland Pascal взаимодействует соперационной системой MS DOS.6.1. Файловая система MS DOSКак сказано выше, каждый файл обязательно имеет имя.

Имена файловв MS DOS подчиняются определенным правилам:• имя файла должно содержать не менее одного и не более восьми сим­волов;• имя файла может иметь расширение, которое отделяется от имени точ­кой и содержит не более трех символов;• для записи имен и расширений могут использоваться строчные и про­писные буквы латинского алфавита a-z, A-Z, арабские цифры и некоторыеспециальные символы, например, символ подчеркивания «_» или знак дол­лара «$»;• в качестве имен запрещается использовать некоторые буквенные соче­тания, которые зарезервированы операционной системой для обозначенияустройств, например: PRN, CON, NUL, COMI, COM2, AUX, LPT1, LPT2,LPT3.В операционных системах типа Windows некоторые из этих правил от­меняются, например, имя файла может содержать больше восьми символови включать символы русского алфавита.

Однако при работе с файлами изBorland Pascal лучше придерживаться правил MS DOS.Независимо от используемой операционной системы имена обычно со­ставляют так, чтобы они указывали на содержимое файла. Расширение обыч­но определяет тип хранящихся данных.1886. Файловая система. ФайлыСуществуют стандартные расширения, используемые операционной си­стемой, например:СОМ, ЕХЕ ~ исполняемые файлы (загрузочные файлы программ);PAS, BAS, СРР - файлы исходных текстов программ на алгоритмичес­ких языках ПАСКАЛЬ, БЭЙСИК и C++ соответственно.Для удобства работы с группами файлов применяют групповые именафайлов с использованием символов «*» и «?», где «*» соответствует любойпоследовательности символов, а «?» - одному любому символу, например:*• ЕХЕ - все файлы с расширением ЕХЕ;А*. СОМ - все файлы типа СОМ с именами на букву «А»;??В. PAS - все файлы типа PAS, имена которых содержат три символа,последний из которых «В»;PRG1.* - файлы любых типов с именем PRG1;*.* - все файлы.Для того чтобы MS DOS могла размещать файлы на дисках, последниедолжны быть специальным образом размечены (форматированы).

Разметкаосуществляется средствами используемой операционной системы. Еслиформатируется диск, бывший в употреблении, то вся хранившаяся на нем ин­формация уничтожается и восстановлению не подлежит.Как правило, диски хранят большое количество файлов (количество ихна жестких дисках обычно исчисляется тысячами). Для удобства и ускоренияработы с таким количеством файлов применяется древовидная структура ка­талогов, аналогичная библиотечной.Главным является корневой каталог, не имеющий имени и создаваемыйв процессе форматизации диска системой.

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

Таким образом, чтобы сослаться на файл, нужно указать нетолько его имя, но и перечислить все предшествующие каталоги. Переченьимен каталогов на пути к файлу называется маршрутом или путем.Перечисляемые в маршруте каталоги разделяются символом «\», причемперечень начинается с символа «\», так как корневой каталог не имеет име­ни.

Например:189Часть L Основы алгоритмизации и процедурное программированиеРис. 6.1. Пример дерева каталогов\katl\kat3\Полное имя файла содержит также имя диска, на котором расположенфайл. Например:c:\katl\ kat3\file5.datТакая организация позволяет в разных подкаталогах создавать файлы содинаковыми именами. Подкаталоги тоже могут иметь одинаковые имена,если они подчинены разным подкаталогам более высокого уровня.6.2.

Файлы Borland PascalВ Borland Pascal файл определяется как последовательность компонен­тов, относящихся к одному типу: файл записей, файл целых чисел, файлстрок и т. п. Особенностью файлов по сравнению с другими структурнымитипами данных является то, что в любой момент доступен только один ком­понент. Количество компонентов файла заранее не определяется. Макси­мальный размер файла, размещенного во внешней памяти, ограничиваетсялишь техническими возможностями вычислительной системы.Различают дисковые файлы и логические устройства.Дисковый файл представляет собой поименованную область внешнейпамяти на устройстве хранения информации, например, дискете или винчес­тере.

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

Для дисковых файлов принципи­ально возможен не только последовательный, но и произвольный доступ,при котором чтение информации осуществляется из указанного места.Логические устройства используют для организации обмена информа­цией с основными устройствами ввода-вывода, такими как дисплей, клавиа­тура и т. п. Логические устройства имеют стандартные имена, например:CON - консоль: при выводе данных соответствует экрану, при вводе клавиатуре;Р1Ш - принтер;NUL - «пустое устройство», обычно заменяет устройство вывода отла­дочной информации после завершения отладки программы.В отличие от дисковых файлов с логическими устройствами операцииввода-вывода осуществляют только последовательно, так как при выполне­нии операций вывода данные передаются на устройство покомпонентно, апри выполнении операций ввода - покомпонентно запрашиваются с него.Доступ к компоненту файла осуществляется через указатель файла.При выполнении операции чтения или записи указатель автоматически пере­мещается на следующий компонент (рис.

6.2).Для идентификации файлов в Borland Pascal используют фашовые пере­менные, В зависимости от способа представления информации различаюттри типа файлов, соответственно различаются и способы описания файло­вых переменных (рис. 6.3).Типизированные файлы. Файловая переменная типизированного файлаописывается какТуре <идентификатор файловой переменной> =Jile о/<тип компонента>;...где <тип компонента> - любой тип данных, кроме файлового.Указатель файлаМаркер конца [тйлаРис. 6.2. Организация файла191Часть I.

Основы алгоритмизации и процедурное программированиеr&iТипкомпонента~р*/^Г|1еЛtextРис. 6.3. Синтаксическая диаграмма<Файловый тип>Типизированные файлы используют, когда обрабатывают хранящуюся вфайле или передаваемую с устройства/на устройство последовательностькомпонентов одинаковой длины (чисел, записей и т.п.).Текстовые файлм - тип файловой переменной описывается так:Туре <идентификатор файловой переменной> = text;...Текстовые файлы используют для работы с текстами, представленнымив виде строк переменной длины.Нетипшироваииые файлы:Туре <идентификатор файловой переменной>=/ile;...Нетипизированные файлы применяют для организации скоростного об­мена между внешней и оперативной памятью физическими записями указан­ной длины без преобразования и обработки.Как и любая переменная языка Borland Pascal, файловая переменная мо­жет быть описана в инструкции объявления переменных, например:VarF1: file of real;F2:file:F3: text;...или с предварительным объявлением типа:Туре FF =file of integer;VarFLFF;.,.При необходимости файловую переменную допускается передавать вподпрограмму через параметры.

Характеристики

Список файлов книги