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-}.


 

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

11101. Вредные привычки и их влияние на здоровье (алкоголизм, табакокурение, наркомания и токсикомания). Профилактика злоупотребления психоактивными веществами 23.11 KB
  Вредные привычки и их влияние на здоровье алкоголизм табакокурение наркомания и токсикомания. Профилактика злоупотребления психоактивными веществами Влияние вредных привычек на здоровье человека. Курение. Вот несколько факторов которые свидетельствуют о то...
11102. Учение о повязках. Виды повязок и правила их наложения. Методы остановки кровотечения. ПМП при травмах, ранениях 122.7 KB
  Учение о повязках. Виды повязок и правила их наложения. Методы остановки кровотечения. ПМП при травмах ранениях Десмургия греч. desmos связь повязка ergon дело учение о повязках их правильном применении и наложении при различных повреждениях и заболеваниях. В связи с э
11103. ПМП при отравлениях. ПМП при отморожении тепловом и солнечных ударах, при поражении электрическим током и при ожогах 41.25 KB
  ПМП при отравлениях. ПМП при отморожении тепловом и солнечных ударах при поражении электрическим током и при ожогах ПЕРВАЯ ПОМОЩЬ ПРИ ОТРАВЛЕНИЯХ. Отравление это патологическое состояние которое возникает при воздействии ядов и токсинов на организм. Среди причин о...
11104. ПМП при ушибах и переломах. ПМП при острой сердечной недостаточности и инсульте. ПМП при массовых поражениях 114.11 KB
  ПМП при ушибах и переломах. ПМП при острой сердечной недостаточности и инсульте. ПМП при массовых поражениях Первая помощь при ушибах растяжениях и переломах. Ушиб закрытое повреждение тканей и органов без существенного нарушения их структуры. Обычно возникает в ре...
11105. Единая государственная система предупреждения и ликвидации ЧС (РС ЧС), ее основные задачи и структура 91.65 KB
  Единая государственная система предупреждения и ликвидации ЧС РС ЧС ее основные задачи и структура. 1.ЦЕЛЬ И ПРИНЦИПЫ СОЗДАНИЯ РСЧС ЕЕ ОСНОВНЫЕ ЗАДАЧИ Необходимость образования государственных систем защиты населения и территорий как в России так и за рубежом была...
11106. Гражданская оборона, история создания, ее задачи, структура 25.18 KB
  Гражданская оборона история создания ее задачи структура Предназначение и задачи ГО РФ Структура ГО РФ Руководство ГО РФ Органы управления ГО РФ Организация задачи ГО в общеобразовательном учреждении Содержание плана ГО общеобразовательного уч
11107. Повышение устойчивости работы объектов на ЧС 42.56 KB
  Повышение устойчивости работы объектов на ЧС ПРЕДУПРЕЖДЕНИЕ ЧРЕЗВЫЧАЙНЫХ СИТУАЦИЙ И ПОВЫШЕНИЕ УСТОЙЧИВОСТИ ФУНКЦИОНИРОВАНИЯ ОРГАНИЗАЦИЙ Введение Как гласит Федеральный закон О защите населения и территорий от чрезвычайных ситуаций природного и техног...
11108. Локализация и ликвидация последствий ЧС 22.07 KB
  Локализация и ликвидация последствий ЧС Ликвидация последствий ЧС. Ликвидация ЧС ситуации осуществляется силами и средствами предприятий учреждений и организаций независимо от их организационно правовой формы органов местного самоуправления органов исполнител...
11109. Дознание в уголовном процессе 44.5 KB
  РЕФЕРАТ по уголовному процессу на тему: Дознание в уголовном процессе Дознание один из видов предварительного расследования о...