Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Сортировка методом сцепления очередей. Поиск методом составных атрибутов

Название: Сортировка методом сцепления очередей. Поиск методом составных атрибутов
Раздел: Рефераты по информатике
Тип: реферат Добавлен 06:16:56 04 июня 2011 Похожие работы
Просмотров: 17 Комментариев: 12 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра “Комплексная Защита Информационных Систем”

Специальность 090104 “Комплексная Защита Объектов Информатизации”

КУРСОВАЯ РАБОТА

по Методам Программирования и Прикладным Алгоритмам

(дисциплина)

"Сортировка методом сцепления очередей. Поиск методом составных атрибутов"

(тема КР)

Допустить к защите

И.О. Зав. кафедрой д.ф-м.н. Добрица В.П.

Выполнил ______________________

(Ф.И.О. студента)

Студент __________________________

(курс, группа)

Работа защищена _________________

(дата)

Оценка ____________________________

Руководитель к.т.н. С.С.Шевелев

(подпись, Ф.И.О. преподавателя)

Курск 2009 г.

Содержание

1 Введение ………………………………….…………………………………………..3

2 Теоретическая часть………………………………….…………………………….5

3. Практическая часть………………………………….………………………..…...7

3.1. Листинг………………………………….……………………………..…...7

3.2. Блок-схема………………………………….……………………………..10

3.3. Описание переменных………………………………….………………..17

3.4. Внешний вид формы…………………………………………………….17

3.5. Результаты выполнения программы…………………………………18

4. Заключение……………………………………..………………………………….21

5. Список используемой литературы……………………………………………..22

1. Введение

Наиболее частый вопрос, который возникает в программировании: переразмещение элементов в возрастающем или убывающем порядке. Представьте, насколько трудно было бы пользоваться словарем, если бы слова в нем не располагались в алфавитном порядке. Точно так же от порядка, в котором хранятся элементы в памяти ЭВМ, во многом зависит скорость и простота алгоритмов, предназначенных для их обработки.

Хотя в словарях слово "сортировка" (sorting) определяется как "распределение, отбор по сортам; деление на категории, сорта, разряды", программисты традиционно используют это слово в гораздо более узком смысле, обозначая им сортировку предметов в возрастающем или убывающем порядке. Этот процесс, пожалуй, следовало бы назвать не сортировкой, а упорядочением (ordering), но использование этого слова привело бы к путанице из-за перегруженности значениями слова "порядок". В математической терминологии это слово также изобилует значениями (порядок группы, порядок перестановки, порядок точки ветвления, отношение порядка и т. п.). Итак, слово "порядок" приводит к хаосу.

В качестве обозначения для процесса упорядочения предлагалось также слово "ранжирование", но оно во многих случаях, по-видимому, не вполне отражает суть дела, особенно если присутствуют равные элементы, и, кроме того, иногда не согласуется с другими терминами. Конечно, слово "сортировка" и само имеет довольно много значений, но оно прочно вошло в программистский жаргон. Поэтому мы без дальнейших извинений будем использовать слово "сортировка" в узком смысле "сортировка по порядку".

Вот некоторые из наиболее важных применений сортировки:

Решение задачи "группировки", когда нужно собрать вместе все элементы с одинаковым значением некоторого признака. Допустим, имеется 10000 элементов, расположенных в случайном порядке, причем значения многих из них равны; и предположим, нам нужно переупорядочить файл так, чтобы элементы с равными значениями занимали соседние позиции в файле. Это, по существу, задача "сортировки" в широком смысле слова, и она легко может быть решена путем сортировки файла в узком смысле слова, а именно расположением элементов в неубывающем порядке v1 v2 ... v10000. Эффективностью, которая может быть достигнута в этой процедуре, и объясняется изменение первоначального смысла слова "сортировка".

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

Сортировка помогает и при поиске, с ее помощью можно сделать выдачи ЭВМ более удобными для человеческого восприятия. В самом деле, листинг (напечатанный машиной документ), отсортированный в алфавитном порядке, зачастую выглядит весьма внушительно, даже если соответствующие числовые данные были рассчитаны неверно.

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

2. Теоретическая часть

Сортировка

Поиск

3. Практическая часть

3.1. Листинг

unit Unit1;

interface

uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Grids;

type

FindRec = record

count:Integer;

dats:array of integer;

end;

put = record

ind:array of integer;

col_vo:Integer; end;

TForm1 = class(TForm)

StringGrid1: TStringGrid;

StringGrid2: TStringGrid;

StringGrid3: TStringGrid;

Button1: TButton;

Button2: TButton;

Button3: TButton;

Edit1: TEdit;

Edit2: TEdit;

Edit3: TEdit;

Edit4: TEdit;

Edit5: TEdit;

Edit6: TEdit;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

Label8: TLabel;

Label9: TLabel;

Label10: TLabel;

Edit7: TEdit;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

a,b:array of integer;

implementation

uses Math, DateUtils;

{$R *.dfm}

function obmen(i:integer;j:integer):Boolean;

var

p:integer;

begin

p:=a[i];

a[i]:=a[j];

a[j]:=p;

Result:=true;

end;

function Zameni(x:integer;y:integer):Integer;

var

i,j:Integer;

pr:boolean;

begin

i:=x;

j:=y;

pr:=false;

while i<j do begin

if a[i]>a[j] then

begin

if pr= false then

i:=i+1

else

j:=j-1;

end;

end;

end;

procedure ScepOch(l, t: integer);

var i: integer;

begin

if l<t then begin

i:=Zameni(l, t);

ScepOch(l,i-1);

ScepOch(i+1,t);

end;

end;

function SostAtr(obr:Integer;kol:Integer):FindRec;

var

sr,j:integer;

n,v:Integer;

founded:Boolean;

rez:FindRec;

tree:put;

begin

n:=0;

v:=kol-1;

founded:=false;

rez.count:=0;

SetLength(rez.dats,0);

tree.col_vo:=0;

while (n<=v) and (founded=false) do

begin

sr:=(n+v) div 2;

SetLength(tree.ind,tree.col_vo+1);

tree.ind[tree.col_vo]:=sr;

inc(tree.col_vo);

if a[sr]=obr then

begin

for j:=n to v do begin

if a[j]=obr then begin

inc(rez.count);

SetLength(rez.dats,rez.count);

rez.dats[rez.count-1]:=j;

end;

end;

end;

Result:=rez;

end;

procedure TForm1.Button1Click(Sender: TObject);

var

i,k:Integer;

t1,t2:integer;

r:TTimeStamp;

begin

t1:=MilliSecondOfTheMinute(time);

k:=0;

while k<=100 do

begin

a:=b;

ScepOch(0,StrToInt(Edit2.Text)-1);

k:=k+1;

end;

t2:=MilliSecondOfTheMinute(Time);

for i:=0 to StrToInt(Edit2.Text)-1 do

begin

StringGrid2.Cells[i,0]:=IntToStr(a[i]);

end;

Edit3.Text:=FloatToStr(abs(t1-t2)/1000);

end;

procedure TForm1.Button2Click(Sender: TObject);

var i:Integer;

begin

SetLength(b,StrToInt(Edit2.Text));

for i:=0 to StrToInt(Edit2.Text)-1 do begin

b[i]:=Random(StrToInt(Edit1.Text));

StringGrid1.Cells[i,0]:=IntToStr(b[i]);

end;

StringGrid1.ColCount:=StrToInt(Edit2.Text);

StringGrid2.ColCount:=StrToInt(Edit2.Text);

Button1Click(Sender);

StringGrid3.ColCount:=StrToInt(Edit2.Text);

for i:=0 to StrToInt(Edit2.Text)-1 do

StringGrid3.Cells[i,0]:=StringGrid2.Cells[StrToInt(Edit2.Text)-1-i,0];

end;

procedure TForm1.Button3Click(Sender: TObject);

var obr,i,k:integer;

f:FindRec;

t1,t2:Integer;

begin

obr:=StrToInt(Edit4.Text);

t1:=MilliSecondOfTheMinute(time); k:=0;

while k<=10000 do begin

f:=SostAtr(obr,StrToInt(Edit2.Text));

inc(k); end;

t2:=MilliSecondOfTheMinute(time);

if f.count<>0 then begin for i:=0 to f.count-1 do begin

Edit5.Text:=Edit5.Text+IntToStr(f.dats[i]+1)+';';

Edit7.Text:=Edit7.Text+IntToStr(StrToInt(Edit2.Text) - f.dats[i])+';';

end; end

else begin

Edit5.Text:='нет такого элемента';

Edit7.Text:='нет такого элемента'; end;

Edit6.Text:=FloatToStr(abs(t1-t2)/10000);

end; end.

3.2. Блок - схема :

procedure ScepOch (l, t: integer);

function Zameni(x:integer;y:integer):Integer;

function Obmen(i:integer;j:integer):Boolean;

procedure TForm1.Button1Click(Sender: TObject);

procedure TForm1.Button2Click(Sender: TObject);

procedure TForm1.Button3Click(Sender: TObject);

function SostAtr (obr:Integer;kol:Integer):FindRec;

3.3. Описание переменных :

function Obmen(i:integer;j:integer):Boolean;

p – переменная для перестановки двух элементов массива

function Zameni(x:integer;y:integer):Integer;

i,j – счетчики

procedure ScepOch (l, t: integer);

i – элемент массива для сортировки

procedure TForm1.Button1Click(Sender: TObject);

i – счетчик

procedure TForm1.Button2Click(Sender: TObject);

i – счетчик

procedure TForm1.Button3Click(Sender: TObject);

obr – образец для поиска

i - счетчик

f – номер данного элемента в массиве

function SostAtr (obr:Integer;kol:Integer):FindRec;

j - счетчик

n – количество элементов

v – промежуточная переменная для работы

rez – номер образца в массиве

3.4. Внешний вид формы:

3.5. Результаты выполнения программы:

Количество элементов

Среднее время поиска (мс)

100

5

1000

7,60

3000

8

5000

10

10000

12

Количество

элементов

время сортировки (мс)

10

14

50

16

100

17

200

18

300

20

500

25

1000

49

2000

127

3000

263

5000

405

6000

504

7000

559

8000

775

9000

965

10000

1068

4. Заключение

Поставщики вычислительных машин считают, что в среднем более 25% машинного времени систематически тратится на сортировку. Во многих вычислительных системах на нее уходит больше половины машинного времени. Из этой статистики можно заключить, что либо сортировка имеет много важных применений, либо ею часто пользуются без нужды, либо применяются в основном неэффективные алгоритмы сортировки. По-видимому, каждое из трех предположений содержит долю истины. Во всяком случае ясно, что сортировка заслуживает серьезного изучения с точки зрения ее практического использования.

Но даже если бы сортировка была почти бесполезна, нашлась бы масса других причин заняться ею! Изобретательные алгоритмы сортировки говорят о том, что она и сама по себе интересна как объект исследования. В этой области существует множество увлекательных нерешенных задач наряду с весьма немногими уже решенными.

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

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

5. Список использованной литературы

1. Д. Кнут «Искусство программирования» 3 том

2. Н. Вирт «Алгоритмы+структуры данных=программы».-М.:Мир.1977

3. Белова Т.М.,Старков Ф.А. «Программирование в Delphi».-КурскГТУ.Курск.2002

4. Фаронов В.В. «Delphi.Программирование на языке высокого уровня».-СПб.:Питер,2006

5. А.Ахо,Дж.Хопкрофт,Дж.Ульман «Построение и анализ вычислительных алгоритмов».-

М.:Мир,1979

6. Фаронов В. «Turbo Pascal.Наиболее полное руководство».-СПб.:БХВ-Петербург,2004

7. Иванов Б.Н. «Дискретная матеметика.Алгоритмы и программы».-М.:Лаборатория базовых знаний,2003

8. Липский В. «Комбинаторика для программистов».-М.:Мир,1988

9. Д.Грин , Д.Кнут «Комбинаторная теория».- М.:Мир,1987

10. Д.Грин , Д.Кнут «математические методы анализа алгоритмов».М.:Мир,1987

11. Дж.Макконнелл «Основы современных алгоритмов».М.:Техносфера,2004

12. Аветисян Р.Д.,Аветисян Д.О. «Теоретические основы информатики»

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Хватит париться. На сайте FAST-REFERAT.RU вам сделают любой реферат, курсовую или дипломную. Сам пользуюсь, и вам советую!
Никита18:57:56 05 ноября 2021
.
.18:57:53 05 ноября 2021
.
.18:57:51 05 ноября 2021
.
.18:57:48 05 ноября 2021
.
.18:57:45 05 ноября 2021

Смотреть все комментарии (12)
Работы, похожие на Реферат: Сортировка методом сцепления очередей. Поиск методом составных атрибутов

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(288308)
Комментарии (4159)
Copyright © 2005-2021 BestReferat.ru support@bestreferat.ru реклама на сайте

Рейтинг@Mail.ru