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


 

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

78241. Костная ткань, ткани зуба, слюна 58 KB
  В ней преобладает межклеточное вещество содержащее большое количество минеральных компонентов главным образом солей кальция. В компактном веществе кости большая часть минеральных веществ представлена гидроксилапатитом смотрите рисунок и аморфным фосфатом кальция. Это позволяет кости легко связывать или отдавать ионы фосфата поэтому кость это депо для минералов особенно для кальция. ФАКТОРЫ ВЛИЯЮЩИЕ НА ОБМЕН КАЛЬЦИЯ И ФОСФОРА На обменкальция и фосфора влияют гормоны ПАРАТГОРМОН СЕРОТОНИН и активная форма витамина D3.
78243. ОСОБЕННОСТИ И ЗНАЧЕНИЕ ГЛИКОЛИЗА В ЭРИТРОЦИТАХ 132.5 KB
  В связи с этим в эритроцитах отмечается большой расход глюкозы. Установлено что в эритроцитах утилизируется лишь 005 кислорода. В эритроцитах по пути гликолиза расходуется 90 глюкозы по пентозофосфатному пути 10.
78244. Острые пневмонии 137 KB
  Пневмоцистные пневмонии. Возбудителем пневмоцистной пневмонии является паразит Pneumocystis crinii. Вот эта способность пневмоцист настолько характерна что при выявлении пневмоцистной пневмонии у ребенка не получающего иммуносупрессивных препаратов это уже позволяет диагностировать у него дефект клеточного иммунитета.
78245. Бронхиальная астма 140 KB
  Диагностика Диагноз ставится на основании данных анамнеза наличие наследственной отягощенности аллергическими заболеваниями зависимости возникновения симптомов болезни от воздействия тех или иных аллергенов по улучшении состояния после применения бронходилататоров а также выявления у больного ребенка сопутствующих заболеваний аллергического генеза атопического дерматита...
78246. Врожденные и наследственные заболевания с поражением органов дыхания 118 KB
  Бронхоэктатическая болезнь представляет собой заболевание, основным патоморфологическим субстратом которого является регионарное расширение бронхов, преимущественно в нижних сегментах легких, сопровождающееся хроническим нагноительным процессом
78247. Анемии у детей 149.5 KB
  Это анемии в основе которых лежит дефицит железа витаминов и белка т. имеется дефицит железа. В современных условиях наиболее частой причиной возникновения анемий у детей является именно недостаток железа. Новорожденный доношенный ребенок рождается с содержанием железа в количестве 025 г причем большая его часть 02 г содержится в эритроцитах.
78248. Лейкозы у детей 164 KB
  Острый нелимфобластный лейкоз программа включает индукцию ремиссии цитозар внутривенно в дозе 100 мг м2 1 раз в сутки 12 процедур даунорубомицин внутривенно в дозе 30 мг м2 в дни с 3го по 5й вепезид внутривенно в дозе 150 мг м2 вводится с 6го по 8й день эндолюмбально вводят цитозар в первый день доза зависит от возраста детям до года вводится 20 мг с года до двух 26 мг с двух до трех 34 мг старше трех лет 40 мг. На 15 день выполняется стернальная пункция и при резком угнетении гемопоэза когда количество бластов менее 5...
78249. Геморрагические заболевания у детей 139.5 KB
  Процесс свертывание крови это весьма сложный ферментативный процесс в котором принимают участие многочисленные компоненты плазмы тромбоцитов и тканей которые называют факторами свертывания крови. Их называют тромбоцитарными факторами и нумеруют арабскими цифрами их одиннадцать. Все ткани и органы содержат очень активный тромбопластин антигепариновый фактор естественные антикоагулянты соединения подобные плазменным факторам V VII X и XIII вещества вызывающие адгезию и агрегацию тромбоцитов активаторы и ингибиторы фибринолиза....