4604

Простейшие алгоритмы. Поиск

Контрольная

Информатика, кибернетика и программирование

Простейшие алгоритмы. Поиск Линейный поиск В массиве ТИП найти элемент равный Алгоритм линейного поиска Цикл while завершит свою работу либо при нахождении элемен...

Русский

2012-11-23

81.5 KB

4 чел.

Простейшие алгоритмы. Поиск

Линейный поиск

В массиве A: array[iMin..iMax] of ТИП найти элемент равный B.

Листинг. Алгоритм линейного поиска

i:=iMin;

while (i<iMax) and (A[i]=B) do i:=i+1;

Цикл while завершит свою работу либо при нахождении элемента равного B, либо при переборе всех элементов массива.

На каждом шаге цикла выполняется две проверки. Для упрощения проверок в конец массива A: array[iMin..iMax+1] of ТИП добавляется барьер - элемент равный B.

Листинг. Алгоритм линейного поиска с барьером

i:=iMin; A[iMax+1]:=B;

while A[i]=B do i:=i+1;

Завершение работы цикла гарантировано, т.к. элемент B в массиве всегда есть. Ожидаемое число шагов – N/2.

Поиск делением пополам

В упорядоченном массиве A: array[iMin..iMax] of ТИП найти элемент равный B.

Листинг. Алгоритм поиска деления пополам

A1:=iMin; A2:=iMax; Ok:=false;

while (A1<=A2) and not Ok do

begin

 m:=(A1+A2) div 2;

 if A[m]=B then Ok:=true

 else

   if A[m]<B then A1:=m+1 else A2:=m-1;

end;

Листинг. Упрощенный алгоритм поиска деления пополам

A1:=iMin; A2:=iMax;

while A1<A2 do

begin

 m:=(A1+A2) div 2;

 if A[m]=B then

   if A[m]<B then A1:=m+1 else A2:=m;

end;

Завершение работы цикла гарантировано, т.к. A1<m<A2, A1 – увеличивается, A2 - уменьшается. Ожидаемое число шагов – logN.

Поиск в массиве строк

В массиве упорядоченных строк AStr: array[iMin..iMax] of string найти строку St: string.

Воспользуемся поиском деления пополам:

Листинг. Поиск в массиве строк

A1:=iMin; A2:=iMax;

while A1<A2 do

begin

 m:=(A1+A2) div 2; i:=0;

 while (AStr[m,i]=St[i]) and (St[i]<>#0) do i:=i+1;

 if AStr[m,i]<St[i] then A1:=m+1 else A2:=m;

end;

if A2<iMax then begin

 i:=0;

 while (AStr[A2,i]=St[i]) and (St[i]<>#0) do i:=i+1;

end;    

Прямой поиск строки

В строке s: string[N] найти строку s0: string[M].

Листинг. Прямой поиск строки

i:=0;

repeat

 i:=i+1; j:=1;

 while (j<M) and (s[i+j-1]=s0[j]) do j:=j+1;

until (j=M) or (i=N-M);  

Сортировка

Пузырьковая сортировка

Отсортировать массив A: array[iMin..iMax] of ТИП.

Листинг. Пузурьковая сортировка.

for i:=iMin+1 to iMax do

for j:=iMax downto i do

 if A[j-1]<A[j] then

 begin

   t:=A[j-1]; A[j-1]:=A[j]; A[j]:=t;

 end;

Шейкерная сортировка

Отсортировать массив A: array[1..N] of ТИП.

Листинг. Шейкерная сортировка.

L:=2; R:=N; k:=N;

repeat

 for j:=R downto L do

 if A[j-1]>A[j] then begin

   t:=A[j-1]; A[j-1]:=A[j]; A[j]:=t;

 end;

 L:=k+1;

 for j:=L to R do

 if A[j-1]>A[j] then begin

   T:=A[j-1]; A[j-1]:=A[j]; A[j]:=t;

 end;

 R:=k-1;

until L>R;

Файлы

Существует три традиционных способа доступа к информации в файле: файл может быть открыт как текстовый, как типизированный и как нетипизированный. Текстовые файлы могут содержать признак конца строки (символы с кодами #13#10) и  признак конца файла (символ с кодом #27). Типизированные файлы допускают запись и чтение данных порциями одинаковой длины. Структура этой порции определяется при объявлении файлового указателя. Нетипизированные файлы используются для быстрой записи и копирования данных.

При работе с любым типом данных необходимо обязательно выполнить 5 действий:

  •  описать файловый указатель;
  •  связать файловый указатель с именем файла;
  •  объявить новый файл или существующий;
  •  записывать данные или читать их;
  •  закрыть файл.

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

Таблица 6.1. Основные действия с файлами

Назначе-ние

Текстовые

Типизирован-ные

Нетипизирован-ные

1

Указатель

F: textfile

F: file of ТИП 

X: ТИП

F: file

2

Связать

AssignFile(f,name)

AssignFile(f, name)

AssignFile(f,name)

3

Объявить

Существу-ющий

Reset(f), Append(f)

Reset(f)

Reset(f,1)

3

Объявить новый

Rewrite(f)

Rewrite(f)

Rewrite(f,1)

4

Чтение

Read(f,список)

Readln(f,список)

Read(f,x)

BlockRead (f,buf,SizeOf(buf), NumRead)

4

Запись

Write(f,список)

Writeln(f,список)

Write(f,x)

BlockWrite (f,buf,SizeOf(buf), NumWrite)

5

Закрыть

CloseFile(f)

CloseFile(f)

CloseFile(f)

Файловый указатель f – любая переменная файлового типа: текстового, типизированного и нетипизированного.

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

Если связь с внешним файлом установлена, файловая переменная должна "быть открыта", чтобы подготовить его для чтения или записи. Существующий файл может открываться с помощью процедуры Reset, которая устанавливает файловый указатель в начало файла. Существующий текстовый файл также может открываться с помощью процедуры Append, которая устанавливает файловый указатель в конец файла. Новый файл может создаваться и открываться процедурой Rewrite. Текстовые файлы, открываемые Reset, предназначены только для чтения, а текстовые файлы открытые Rewrite или Append предназначены только для записи. Типизированные файлы и нетипизированные файлы допускают как чтение, так и запись независимо от того, как они открывались  Reset или Rewrite.

Каждый файл – линейная последовательность компонентов, которая имеет тип компонента (или тип записи). Нумерация записей начинается с нуля.

Файлы доступны последовательно. При чтении компонента с помощью процедуры Read и при записи процедурой Write, файловый указатель переходит на следующий компонент. Типизированные файлы и нетипизированные файлы могут быть доступными произвольно с помощью процедуры Seek, которая перемещает файловый указатель на указанный компонент. Функции FilePos и FileSize позволяют определять текущую файловую позицию и размер файла.

Когда программа завершает обработку файла, файл должен быть закрыт процедурой CloseFile. После того, как файл закроется, связанный внешний файл будет скорректирован. Файловая переменная может затем связываться с другим внешним файлом.

Помимо основных процедур, представленных в табл. 6.1, существует достаточно много других процедур и функций, предназначенных для работы с файлами. Некоторые из них представлены в табл. 6.2:

Таблица 6.2. Другие процедуры и функции

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

Описание

Append (var F: Text)

Открывает существующий текстовый файл для добавления

AssignFile(var F; FileName: string)

Назначает имя файла в файловую переменную

BlockRead (var F: File; var Buf; Count:Integer[;var AmtTransferred: Integer])

Читает одну или более записей из нетипизированного файла.

BlockWrite (var f: File; var Buf; Count: Integer[;var AmtTransferred: Integer])

Пишет одну или более записей в нетипизированный файл.

ChDir (S: string)

Изменяет текущий директорий.

CloseFile (var F)

Закрывает открытый файл.

Eof(var F)

Возвращает статус конца файла

Eoln [(var F: Text) ]

Возвращает статус конца строки текстового файла.

Erase (var F)

Удаляет файл.

FilePos(var F)

Возвращает текущую файловую позицию типизированного или нетипизированного файла

FileSize(var F)

Возвращает текущий размер файла; не использовать для текстовых файлов.

Flush (var F: Text)

Сбрасывает буфер выходного текстового файла.

GetDir (D: Byte; var S: string)

Возвращает текущий директорий указанного логического диска.

IOResult: Integer

Возвращает целую величину, которая является статусом последней выполненной функции ввода/вывода.

MkDir (S: string)

Создает поддиректорий.

Read (F , V1 [, V2,...,Vn ] )

Читает одну или более величин из файла в одну или более переменных.

Readln ([ var F: Text; ] V1 [, V2, ...,Vn ])

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

Rename (var F; Newname)

Переименовывает файл.

Reset (var F [: File; RecSize: Word ] )

Открывает существующий файл.

Rewrite (var F [: File; RecSize: Word ] )

Создает и открывает новый файл.

RmDir (S: string)

Удаляет пустую папку.

Seek (var F; N: Longint)

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

SeekEof [ (var F: Text) ]

Возвращает статус конца текстового файла.

SeekEoln [ (var F: Text) ]

Возвращает статус конца строки текстового файла.

SetTextBuf (var F: Text; var Buf [ ; Size: Integer] )

Назначает буфер I/O для текстового файла.

Truncate (var F)

Отсекает типизированный или нетипизированный файл с текущей позиции.

Write (F, V1,...,Vn)

Пишет одну или более величин в файл.

Writeln ([var F: Text;] P1 [,P2, ...,Pn] )

Выполняет Write и затем пишет признак конца строки в текстовый файл.

По умолчанию, все вызовы стандартных процедур и функций ввода/вывода (I/O) автоматически проверяются на ошибки, и если возникает ошибка, то происходит исключение (или программа прекращает свою работу, если не допускается исключительная обработка). Эта автоматически проверка может включаться и выключаться директивами компилятора {$I+} и {$I-}. Если проверка I/O выключена {$I-}, то при возникновении ошибки I/O исключительная обработка не вызывается и необходимо использовать стандартную функцию IOResult.

{$I-}

Reset(f);

{$I+}
if IoResult<>0 then Rewrite(f);

Необходимо вызвать функцию IOResult, для того чтобы очистить ошибку, даже если IOResult не используется. Иначе в состоянии {$I+}  вызов следующей функции I/O потерпит неудачу с предыдущей ошибкой IOResult.

В таблице 6.3  приведены коды ошибок, возникающих при работе с файлами. Эти коды присваиваются  свойству errorcode, если действует директива компилятору {$I+}, или возвращаются функцией IoResult, если действует директива компилятору {$I-}.


 

А также другие работы, которые могут Вас заинтересовать

58575. Сложение вида: к числу прибавить 8, к числу прибавить 9 43.5 KB
  Кто знает что это такое рисунок кляксы А если я не знаю что это слово значит как мне быть толковый словарь Клякса это бесформенное пятно краски или чернил. Иногда с пера падала капелька и на бумаге появлялась клякса.
58576. Формування здорового способу життя школярів 567.5 KB
  Щодня ви пізнаєте життя відкриваєте для себе світ відкриваєте світу себе. Усе життя для вас попереду. Здоровя не можна купити ні за які гроші його можна сформувати шляхом одержання знань і постійною роботою над собою а саме дотриманням правил здорового способу життя.
58577. Разработка технологического процесса изготовления вала-шестерни 651 KB
  В процессе разработки технологии изготовления детали решаются следующие вопросы: выбор способа получения заготовки, металлорежущего оборудования; режущего и измерительного инструментов; назначение припусков на обработку, режимов резания и норм времени; проектирование оригинального и модифицированного станочного или сборочного приспособления.
58578. Классно-урочная система 122.5 KB
  Уроки чередовались с переменами. Выделены несколько типов уроков: комбинированные или смешанные уроки уроки по ознакомлению с новыми фактами конкретными явлениями или имеющие целью осмысление и усвоение обобщений уроки закрепления и повторения знаний уроки имеющие основной целью обобщение и систематизацию изученного уроки выработки и закрепления умений и навыков уроки проверки знаний и разбора проверочных работ. Даже контрольные уроки здесь довольно часто включают в себя другие виды работы: устное сообщение материала...
58579. Що таке скульптура? Види скульптури. Порівняльний аналіз розмірів і пропорцій форм та їх складових частин. Ліплення котика (пластилін) 43 KB
  Що таке скульптура Види скульптури. Не менш цікавий вид образотворчого мистецтва скульптура: памятники видатним людям і скульптурні групи прикрашають вулиці та майдани фонтани парки та сквери окремі громадські будинки також прикрашені скульптурами.
58580. Конституция России 51 KB
  Цель урока: учащиеся продолжают работу по формированию основ правовой культуры закреплению знаний учащихся о государственном устройстве страны о трех ветвях власти. Правила игры: Право ответа игрок получает только от капитана.
58581. Свобода в жизни человека 72 KB
  Воспитательная: подвести учащихся к пониманию что свобода является непреходящей ценностью в любом обществе раскрыть ее значимость в жизни каждого человека; продолжить формирование ценностных ориентаций учащихся путем обсуждения альтернативных моделей поведения человека в ситуациях выбора...
58582. Развитие общества 110.5 KB
  Цель: сформировать у учащихся комплекс знаний о развитии общества. Задачи: Учебная: усвоение учащимися сведений о развитии общества глобальных проблемах человечества понятий прогресс регресс реформа революция глобализация. 2 назовите основные сферы жизни...