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


 

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

8001. Экологическое воспитание в школе 27.5 KB
  Экологическое воспитание в школе Экологическое воспитание - это формирование у детей экологического сознания как совокупности знаний, мышления, чувств, воли и готовности к активной природоохранительной деятельности, помогающего понимать...
8002. Эстетическое воспитание в школе 25 KB
  Эстетическое воспитание в школе Формирование эстетической культуры - процесс целенаправленного развития способностей личности к полноценному восприятию и правильному пониманию прекрасного в искусстве и действительности. Задачи: Выработка...
8003. Нестандартні уроки 14.38 KB
  Нестандартні уроки На небезпечну тенденцію зниження інтересу учнів до занять, яка появилась у нашій школі ще в середині 70-х років, масова практика відреагувала нестандартними уроками, головною метою яких є пробудження й утримання інтересу школярів...
8004. Урок - основна форма організації навчання 21.6 KB
  Урок - основна форма організації навчання У сучасній школі класно-урочна форма є головною (основною), її ключовим компонентом є урок. Урок - це відрізок навчального процесу, який є викінченим у смисловому, часовому й організаційному відношенні. Не...
8005. Типи і структура уроків 24.1 KB
  Урок є складним відрізком навчального процесу. Як усі складні обєкти, уроки можуть бути поділені на типи за різними ознаками. За якими ж ознаками групуються уроки? Проблема ця дуже складна і не вирішена остаточно ні у світовій, ні у вітчизняній дидактиці Кількість класифікацій сьогодні вираховується десятками...
8006. Диагностика обучения 32 KB
  Диагностика обучения Диагностика - выявление всех обстоятельств, условий протекания учебного процесса. Целью является своевременно выявить, оценить и проанализировать не только ход учебного процесса, но и его результат. Диагностика включает в с...
8007. Дидактические принципы обучения 57.5 KB
  Дидактические принципы обучения Дидактические принципы - содержание, организационные формы и методы процесса обучения. Дидактические правила - конкретные указания учителю, как нужно поступить в типичной педагогической ситуации. Принципы...
8008. Процесс обучения 27 KB
  Процесс обучения Учебный процесс - двусторонний управляемый процесс совместной деятельности учителя и учащихся, направленный на интеллектуальное развитие, формирование знаний и способов деятельности и развитие их способностей и наклонностей. Со...
8009. Основні принципи реформування змісту сучасної шкільної освіти 18.43 KB
  Основні принципи реформування змісту сучасної шкільної освіти Зміст шкільної освіти не може бути вузьким через те, що особистість, засвоюючи його, готується до збереження і розвитку культури. Тому зміст освіти повинен мати джерела наука, виробничі ...