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


 

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

26674. ЗОЛОТОЕ КОЛЬЦО РОССИИ 98.88 KB
  МОСКВА Бывают городатруженики городакоммерсанты городаханжи городамузеи городавенценосцы . Так писал о городах К. В этих городах сочетаются уникальные памятники архитектуры скромная красота природы и гений человека его мастерство видение жизни и стремление украсить свой быт народные промыслы. Так что же входит в понятие Золотое Кольцо Это сама Москва и окружающие ее областные города: Ярославль Кострома Владимир Иваново и множество районных городов: Ростов Великий Суздаль ПереславльЗалесский Нерехта Плесс Палех...
26675. Концепция развития туризма в Архангельской области на 2011-2014 годы 25.12 KB
  Концепция разработана в рамках реализации Стратегии социальноэкономического развития Архангельской области до 2030 года.1999 № 14923ОЗ О туризме в Архангельской области; Стратегия социальноэкономического развития Архангельской области до 2030 года. Характеристика современной туристской индустрии Архангельской области 1.
26676. КОНЦЕПЦИЯ РАЗВИТИЯ МОЛОДЕЖНОГО ТУРИЗМА 34.24 KB
  Другой аспект туризма туристский бизнес. Настоящий бум развития туризма в нашей стране был в 30е и 60е годы прошлого века. В настоящее время отсутствует комплексный подход к развитию туризма в стране в 90е годы руководство туризмом было разведено по 14 ведомствам и частному капиталу.
26677. Наследование при моно- и дигибридном скрещивании 14.38 KB
  Закон доминирования первый закон Менделя − это закон единообразия гибридов первого поколения. Это соотношение выражает второй закон Менделя или закон расщепления признаков у гибридов второго поколения в соотношении 3:1 по фенотипу. Закон чистоты гамет гамета содержит 1 и только 1 аллель от каждого гена. 3й закон Менделя: закон независимого наследования.
26678. Полиплоидия. Автополиплоидия, её фенотипические эффекты и генетика. Амфидиплоидия как механизм получения плодовитых аллополиплоидов. Значение полиплоидии в эволюции и селекции растений 13.47 KB
  Геномные мутации это мутации затрагивающие число хромосом изменяющие геномгаплоидный набор хромосом с локализми в них генами. Полиплоидия это изменение числа хромосом кратное гаплоидному. Умножение одного и того же гаплоидного числа хромосом генома назся автополиплоидией. Различают полиплоидию сбалансую с чётным числом наборов хромосом и несбалансую с нечётным.
26679. Строение митотической хромосомы 11.76 KB
  Она связана с тонкими фибриллами и телом хромосомы в области перетяжки. Обычно хромосома имеет только 1 центромеру но может встречаться дицентрические и полицентрические. Те ке хромосомы имеют вторичную перетяжку кя обычно располагается вблизи дистального конца хромосомы и отделяет маленький участок спутник.
26680. Сцепление генов. Группы сцепления. Генетический анализ сцепления генов. Сцепление и перекрест в экспериментах Моргана с дрозофилой 12.78 KB
  Генетический анализ сцепления генов. Число хромосом у разных видов невелико по сравнению с числом генов. У дрозофилы более тысячи генов на 4 пары хромосом.
26681. Транскрипция – синтез РНК 14.63 KB
  Транскрипция синтез всех типов РНК 1 этап экспрессии генов. РНКполимеразы: Транскрипцию осуществлт фермент РНКполимераза особть фия: не требует праймера начинает работать с 1 нуклда работает в направлении 5→3 У прокариот РНКполимза E δ70 имеет большое колво субц 2α взаимодт с промотором; 2β актив. РНКполимза сочетт в себе полимеразную и хеликазю активть.
26682. Трансляция 16.84 KB
  Трансляция - реализация ген.программы клеток,происходит перевод ген.информации,закодированной в структуре НК,в аминокислотную последовательность белков. Это перевод четырехбуквенного(по числу постоянно встречающихся в ДНК и РНК нуклеотидов)