Киберфак – бесплатно скачать презентации PowerPoint, лекции, рефераты, шпоры, курсовые cyberfac logo
cyberfac.ru
На главную | Регистрация | Вход
  Статьи  
Главная » Статьи » Информатика » Алгоритмизация и программирование

Поиск в массиве (Метод простого перебора, Бинарный поиск)

Полезная статья? Пожалуйста, поставьте "+"
Алгоритмизация и программирование - Содержание
Поиск в массиве заданного элемента

При решении многих задач возникает необходимость определить, содержит ли массив определенную информацию или нет. Например, проверить, есть ли в списке студентов фамилия Петров. Задачи такого типа называются поиском в массиве.

Для организации поиска в массиве могут быть использованы различные алгоритмы. Наиболее простой — это алгоритм простого перебора. Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Алгоритм простого перебора применяется, если элементы массива не упорядочены.

Алгоритм простого перебора

Ниже приведен текст программы поиска в массиве целых чисел. Перебор элементов массива осуществляется инструкцией repeat, в теле которой инструкция if сравнивает текущий элемент массива с образцом и присваивает переменной found значение true, если текущий элемент и образец равны.

Цикл завершается, если в массиве обнаружен элемент, равный образцу (в этом случае значение переменной found равно true), или если проверены все элементы массива. По завершении цикла по значению переменной found можно определить, успешен поиск или нет.

Щелчок на командной кнопке Поиск (Buttoni) запускает процедуру TForm1.Button1Click (ее текст приведен в листинге 5.7), которая из компонента stringGridi вводит массив, а из поля редактирования Edit2 — число (образец). Затем выполняется проверка, содержит ли массив введенное число. После завершения проверки процедура showMessage выводит сообщение о результате поиска.

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

unit s_found_; interface

uses

Windows, Messages, SysUtils, Classes,

Graphics, Controls, Forms, Dialogs,

StdCtrls, Grids;

type

TForm1 = class(TForm)

Label1: TLabel;

Label2: TLabel;

Button1: TButton;

Edit2: TEdit;

StringGridi: TStringGrid;

procedure ButtonlClick(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations )

end;

var

Form1: TForm1 ;

implementation

{$R *.DFM}

{ поиск в массиве перебором }

procedure TForml.ButtonlClick(Sender: TObject);

const

SIZE=5; var

a: array[1..SIZE] of integer; //массив

obr: integer; // образец для поиска

found: boolean; // TRUE — совпадение образца с элементом

// массива

i: integer; // индекс элемента массива

begin

// ввод массива for i:=l to SIZE do

a[i] := StrToInt(StringGridl.Cells[i-1,0]);

// ввод образца для поиска

obr := StrToInt(edit2.text);

// поиск

found := FALSE; // пусть нужного элемента в массиве нет

i:= 1;

repeat

if a[i] = obr

then found := TRUE else i := i+1;

until (i > SIZE) or (found = TRUE);

if found

then ShowMessage('Совпадение с элементом номер '

+IntToStr(i)+#13+'Поиск успешен.')

else ShowMessage('Совпадений с образцом нет.');

end;

end.

Очевидно, что чем больше элементов в массиве и чем дальше расположен нужный элемент от начала массива, тем дольше программа будет искать необходимый элемент.

Поскольку операции сравнения применимы как к числам, так и к строкам, данный алгоритм может использоваться для поиска как в числовых, так и в строковых массивах.

Метод бинарного поиска

На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). Например, массив фамилий, как правило, упорядочен по алфавиту, массив данных о погоде — по датам наблюдений. В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых — метод бинарного поиска.

Пусть есть упорядоченный по возрастанию массив целых чисел. Нужно определить, содержит ли этот массив некоторое число (образец).

Метод (алгоритм) бинарного поиска реализуется следующим образом:

1. Сначала образец сравнивается со средним (по номеру) элементом массива.

  • Если образец равен среднему элементу, то задача решена.
  • Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz), и за новое значение verb принимается sred+i, а значение niz не меняется.
  • Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1), и за новое значение niz принимается sred-1, а значение verh не меняется.

 

2. После того как определена часть массива, в которой может находиться искомый элемент, по формуле (niz-verh) /2+verh вычисляется новое значение sred и поиск продолжается.

Поле метки Label3 используется для вывода результатов поиска и протокола поиска. Протокол поиска выводится, если установлен флажок выводить протокол. Протокол содержит значения переменных verh, niz, sred. Эта информация, выводимая во время поиска, полезна для понимания сути алгоритма.

 

В форме приложения появился новый компонент, который до этого момента в программах не использовался, — флажок (компонент CheckBox). Значок компонента checkBox находится на вкладке Standard. Добавляется к форме он точно так же, как и другие компоненты. Свойства компонента CheckBox перечислены в табл. 5.5.

Таблица 5.5. Свойства компонента CheckBox






Свойство

Определяет



Name

Имя компонента. Используется в программе для доступа к свойствам компонента



Caption

Текст, поясняющий назначение флажка



Checked

Состояние, внешний вид флажка: если флажок установлен (в квадратике есть "галочка"), то checked = TRUE; если флажок сброшен (нет "галочки"), то Checked=FALSE



State

Состояние флажка. В отличие от свойства Checked, позволяет различать установленное, сброшенное и промежуточное состояния. Состояние флажка определяют константы:

cbChecked (установлен); cbGrayed (серый, неопределенное состояние); cbUnChecked (сброшен)



AllowGrayed

Может ли флажок быть в промежуточном состоянии: если AllowGrayed = FALSE, то флажок может быть только установленным или сброшенным;

если AllowGrayed = TRUE, то допустимо промежуточное состояние






 






Свойство

Определяет



Left

Top

Height

Width

Font

ParentFont

Расстояние от левой границы флажка до левой границы формы

Расстояние от верхней границы флажка до верхней границы формы

Высоту поля вывода поясняющего текста

Ширину поля вывода поясняющего текста

Шрифт, используемый для отображения поясняющего текста

Признак наследования характеристик шрифта родительской формы






После того как компонент CheckBox будет добавлен к форме, а добавляется он обычным образом, нужно установить значения его свойств в соответствии с табл. 5.6.

Таблица 5.6. Значения свойств компонента CheckBox1






Свойство

Значение



Caption

Checked

Выводить протокол

True






В листинге 5.8 приведен текст процедуры обработки события Onclick для командной кнопки Поиск (Button1). Процедура вводит значения элементов массива и образец, затем, используя алгоритм бинарного поиска, проверяет, содержит ли массив элемент, равный образцу. Кроме того, переменная п (число сравнений с образцом) позволяет оценить эффективность алгоритма бинарного поиска по сравнению с поиском методом простого перебора.

При вычислении номера среднего элемента используется функция тгипс, которая округляет до ближайшего целого и преобразует к типу integer выражение, полученное в качестве аргумента. Необходимость использования тгипс объясняется тем, что выражение (niz-verh) /2 — дробного типа, переменная sred — целого, а переменной целого типа присвоить дробное значение нельзя (компилятор выдаст сообщение об ошибке).

Обратите внимание на процедуры обработки события onKeyPress для компонентов stringGridl и Editl. Первая из них обеспечивает перемещение курсора в следующую ячейку таблицы или в поле Editl (из последней ячейки) в результате нажатия клавиши , вторая — активизирует командную кнопку Поиск также в результате нажатия клавиши .

Листинг 5.8. Бинарный поиск в массиве

unit b_found_;

interface

uses

Windows, Messages, SysUtils, Classes,

Graphics, Controls, Forms, Dialogs, StdCtrls, Grids;

type

TForm1 = class(TForm)

Label1: TLabel;

Label2: TLabel;

Button1: TButton;

Label3: TLabel;

CheckBox1: TCheckBox;

StringGrid1: TStringGrid;

Editl: TEdit;

procedure ButtonlClick(Sender: TObject);

procedure StringGridlKeyPress(Sender: TObject; var Key: Char);

procedure EditlKeyPress(Sender: TObject; var Key: Char); private

{Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.DFM}

{ Бинарным поиск в массиве }

procedure TForm1.Button1Click(Sender: TObject);

const

SIZE=10; var

a:array[1..SIZE] of integer; { массив )

obr:integer; { образец для поиска}

verh:integer; { верхняя граница поиска }

niz: integer; { нижняя граница поиска }

sred:integer; { номер среднего элемента )

found:boolean;{ TRUE — совпадение образца с элементом массива }

n:integer; / число сравнений с образцом }

i:integer;

begin

// ввод массива и образца

for i:=l to SIZE do

a[i]:=StrToInt(StringGridl.Cells[i-l,0] ) ;

obr := StrToInt(Editl.text);

// поиск verh:=1;

niz:=SIZE; n:=0;

found:=FALSE; labels.caption:='';

if CheckBoxl.State = cbChecked

then Labels.caption: ='verh'+#9+'niz'#9'sred' #13;

// бинарный поиск в массиве repeat

sred:=Trunc ( (niz-verh) /2)+verh; if CheckBox1.Checked

then Labels.caption:=label3.caption +IntToStr(yerh) + #9

+IntToStr(niz) + #9 +IntToStr(sred) + #13; n:=n+1;

if a[sred] = obr then found:=TRUE else

if obr < a[sred]

then niz:=sred-1 else verh:=sred+1;

until (verh > niz) or found;

if found

then labels.caption:=label3.caption

+'Совпадение с элементом номер '

+ IntToStr(sred)+#13 + 'Сравнений '

+ IntToStr(n)

else label3.caption:=label3.caption

+'Образец в массиве не найден.';

end;

// нажатие клавиши в ячейке StringGrid

procedure TForml.StringGridlKeyPress(Sender: TObject; var Key: Char),

begin

if Key = #13 then // нажата клавиша

if StringGrid1.Col < StringGridl.ColCount - 1

then // курсор в следующую ячейку таблицы

StringGridl.Col := StringGrid1.Col +1

else // курсор в поле Editl, в поле ввода образца

Editl.SetFocus;

end;

// нажатие клавиши в поле Editl

procedure TForm1.Edit1KeyPress(Sender: TObject;. var Key: Char);

begin

if Key = #13 // нажата клавиша

then // сделать активной командную кнопку

Button1.SetFocus;

end;

end.

Категория: Алгоритмизация и программирование | Добавил: Ni-Cd (10 Декабря 2011)
Просмотров: 4240 | Рейтинг: 5.0/1
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
  Полезные материалы  

В нашем каталоге файлов можно найти много полезной информации. Также советуем заглянуть в каталог статей: в нем есть полезные статьи по темам: Экономика предприятия, Общая экономика, Финансы и Кредит, также Словарь терминов по экономике, Маркетинг, Бухучет и Мировая экономика
Также есть полезная страница Факультеты МИФИ, которая расскажет о том, какие есть в МИФИ факультеты.
Меню
 

Навигация
Высокоуровневые методы информатики и программирования [28]
Информатика и программирование [34]
Информационные системы в экономике [36]
Языки программирования и методы трансляции [15]
Алгоритмизация и программирование [61]
 

Поиск
 

Онлайн
Онлайн всего: 1
Гостей: 1
Пользователей: 0
 

Статистика


Рейтинг@Mail.ru

 


2007 - 2024 © Ni-Cd. All Rights Reserved