 |
Алгоритм выполнения работы.
|
|
|
|
1. Создайте форму, для свойства Caption задайте значение «Линейная сортировка массива».
2. На форме разместите компоненты Edit1, Edit2 и Edit3, кнопку Button1, для свойства Caption которой задайте значение «Создать массив».
3. Удалите текст Edit1, Edit2, Edit3 из соответствующих компонентов.
4. Разместите на форме компоненты Label1, Label2 и задайте для их свойств Caption значения «Число элементов» и «Исходный массив» соответственно.
5. Ниже объекта Edit3 на форме разместите панель RadioGroup1, для свойства Caption которой задайте значение «Порядок сортировки».
6. Для выбора порядка сортировки задайте два переключателя в панели RadioGroup1 и подписи к ним. Выбрав в Инспекторе объектов компонент RadioGroup1, на странице свойств выберите свойство Items, затем в окне String List Editor введите список элементов: По невозрастанию, По неубыванию и нажмите ОК.
7. Справа от панели RadioGroup1 разместите кнопку Button2, для свойства Caption которой задайте значение «Отсортировать».
8. В нижней части формы разместите Edit3 для вывода отсортированного массива. Над объектом Edit3 разместите объект Label3, для свойства Caption которого задайте значение «Отсортированный массив».
9. Выровняйте компоненты на форме
10. Зафиксируйте положение компонентов на форме, выбрав в меню Delphi команду Правка ► Зафиксировать.
11. Сохраните файл проекта и программного модуля.
12. Прежде чем создавать обработчики событий щелчка мышью по кнопкам Button1 и Button2, опишите глобальные переменные целого типа N и I, где N — размер массива, а I — порядковый номер элемента массива, а также М — динамический массив целых чисел.
Var
Form1: TForm1;
N, I: integer;
M: array of integer; {описание динамического массива целых чисел}
13. Для предупреждения ошибки ввода в окно Edit1 нечислового значения введите обработку события нажатия клавиши в окне Edit1, чтобы запретить ввод любых символов, кроме цифр от 0 до 9. Для создания процедуры обработчика события нажатия клавиши в окне Edit1 выберите в окне Инспектора объектов компонент Edit1 и на странице События дважды щелкните левой кнопкой мыши на пустом поле списка в событии On Key Press. После этого в текст процедуры обработчика события добавьте следующий оператор: if not (Key in ['0'..'9']) then Key:=#O;. Полный текст процедуры обработчика события будет выглядеть следующим образом:
|
|
|
procedure Edit1KeyPress(Sender: TObject; var Key: Char);
Begin
if not (Key in ['0'..'9']) then Key:=#0;
end;
14. Создание массива целых чисел опишите в процедуре обработчика события щелчка мышью на кнопке Button1. Для создания процедуры обработчика события выберите в окне Инспектора объектов объект Button1, затем на странице События произведите двойной щелчок на пустом поле списка в событии OnClick. После этого в окне Редактора кода в заготовку процедуры обработчика события введите следующий текст:
procedure TForm1.Button1Click(Sender: TObject);
Begin
Randomize;
N:=StrToInt(Edit1.Text); {число элементов массива}
SetLength(M, N); {задать динамическому массиву М длину N}
Edit2.Text:=' ';
for I:= 0 to N-1 do {заполнить массив случайными значениями целых чисел}
Begin
M[I]:=Round(Sin(Random(100))*100); {присвоить элементу массива случайное значение}
Edit2.Text:=Edit2.Text+' '+IntToStr(M[I]); {вывести элементы массива}
end; end;
15. Обработка события нажатия кнопки Button2 «Вычислить» начинается с сортировки массива, которую можно записать с помощью оператора цикла for.
Для хранения номера элемента массива, сравниваемого с текущим (имеющим номер I) введем переменную целого типа J. Для запоминания элемента массива при обмене в процессе сортировки введем переменную Тmр.
Линейная сортировка массива выполняется путем перестановки элементов в массиве при соблюдении следующих условий: если в неотсортированной части массива найден элемент с номером J, больший, чем элемент с номером I (для сортировки по невозрастанию), или меньший, чем элемент с номером I (для сортировки по неубыванию). Поэтому можно записать следующий оператор if then else с составным условием:
|
|
|
if (RadioGroup1.ItemIndex=0) and (M[I]<M[J]) or (RadioGroup1.ItemIndex=1) and (M[I]>M[J]) then
Перестановка элементов массива осуществляется с использованием третьей переменной:
Тmр:= М[I]; {запомнить на время значение М[1]}
М[I]:= M[J];
M[J]:= Tmp;
Вывод отсортированного массива в окне Edit3 можно записать оператором:
for I:=0 to N-1 do Edit3.Text:=Edit3.Text+' '+IntToStr(M[I]);
В целом текст процедуры сортировки и вывода отсортированного массива будет выглядеть следующим образом:
procedure TForm1.Button2Click(Sender: TObject);
var J, Tmp: integer;
Begin
Edit3.Text: = ' ';
for I:= 0 to N - 2 do {изменять размер неотсортированной части массива}
for J:=I+1 to N-1 do {сравниваем поочередно I-й элемент неотсортированной части массива со всеми от I+1-го до конца}
begin {выбор операции в зависимости от значения свойства RadioGroup1.ItemIndex}
if (RadioGroup1.ItemIndex=O) and (M[I]<M[J])
or (RadioGroup1.ItemIndex=1) and (M[I]>M[J]) then
{если в неотсортированной части массива нашли J-й элемент, больший чем I-й (для сортировки по невозрастанию) или меньший чем 1-й(для сортировки по неубыванию)}
begin {обменять местами элементы массива}
Тmр:= М[I]; {запомнить на время значение М[I]}
M[I]:= M[J];
M[J]:= Tmp;
end;end;
for I:=0 to N-l do {вывести отсортированный массив}
Edit3.Text:=Edit3.Text+' '+IntToStr(M[I]);
end;
16. Сохраните файлы проекта и программного модуля, откомпилируйте и запустите программу на выполнение.
17. Задавая различные значения числа элементов массива и щелкая мышью на кнопке Создать массив, создавайте линейный массив целых чисел. Выбирая при помощи переключателей в панели RadioGroup1 вариант сортировки и щелкая мышью на кнопке Отсортировать, как показано на рис., убедитесь в правильной работе процедуры сортировки и вывода отсортированного массива.
Рис. Окно приложения линейной сортировки массива
18. После окончания проверки работы приложения закройте его окно.
Дополнительное задание.
1 Отредактируйте форму, компоненты вывода другими.
2 Удалите с формы выбор порядка сортировки, добавьте еще один компонент вывода и выполните линейную сортировку и по возрастанию, и по убыванию.
|
|
|
Контрольные вопросы
1 Опишите суть метода сортировки «пузырьком»
2 Запишите фрагмент программы: поменять местами два соседних элемента массива
Практическая работа №8
Лабораторная работа №8
Тема. Поиск в массиве. Разработка программ поиска в массиве
Цель работы: изучить один из методов поиска; овладеть практическими навыками методов поиска в массиве.
Ход работы
1 Повторить теоретический материал
2 Ответить на контрольные вопросы
3 Выполнить практическое задание
4 Составить отчет
Краткие теоретические сведения
Поиск в массиве
При решении многих задач возникает необходимость установить, содержит ли массив определенную информацию или нет. Наиболее простой алгоритм для организации поиска в массиве – это алгоритм простого перебора. Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Алгоритм простого перебора применяется, если элементы массива не упорядочены.
Бинарный поиск в массиве
На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). Например, массив фамилий, как правило, упорядочен по алфавиту, массив данных о погоде — по датам наблюдений. В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых — метод бинарного поиска.
Пусть есть упорядоченный по возрастанию массив целых чисел. Нужно определить, содержит ли этот массив некоторое число (образец).
Метод (алгоритм) бинарного поиска реализуется следующим образом:
1. Сначала образец сравнивается со средним (по номеру) элементом массива
§ Если образец равен среднему элементу, то задача решена.
§ Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz), и за новое значение verb принимается sred+i, а значение niz не меняется
|
|
|
§ Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1), и за новое значение niz принимается sred-1, а значение verh не меняется
2. После того как определена часть массива, в которой может находиться искомый элемент, по формуле (niz-verh) /2+verh вычисляется новое значение sred и поиск продолжается.
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 // нажата клавиша <Enter>
// курсор в следующую ячейку таблицы
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
// нажата клавиша <Enter>
if Key = #13 then // сделать активной командную кнопку
Button1.SetFocus;
end; end.
Практическое задание
Внимательно познакомьтесь с текстом модуля. Для массива из лр5 определите образец для поиска.
Выясните, есть ли этот образец в массиве, используя метод простого перебора. Подсчитайте количество выполненных сравнений.
Отсортируйте массив.
Выясните, есть ли образец в массиве, используя метод половинного деления. Подсчитайте количество выполненных сравнений.
Контрольные вопросы
|
|
|
1 В чем заключается метод простого перебора
2 В чем смысл метода половинного деления
3 Почему специальные методы поиска можно применять только для отсортированных массивов
Практическая работа№9.
Лабораторная работа №9
Тема. Работа с текстом. Разработка программ обработки текста
Цель работы: овладение практическими навыками работы со строками; освоить применение компонентов ListBox и ComboBox для создания приложения, в котором используются строки.
Ход работы
1 Повторить теоретический материал
2 Ответить на контрольные вопросы
3 выполнить практическое задание
4 Составить отчет
|
|
|
