|
Реферат: Алгоритмизация и программирование процессов на Fox (Компьютеры)
Государственный Университет Управления
Институт заочного обучения Специальность – менеджмент
Объяснительная записка к курсовому проекту по дисциплине «Компьютерная подготовка»
по теме: «Алгоритмизация и программирование процессов обработки данных в среде СУБД типа Fox»
Выполнил студент Студенческий билет № Группа №УП4-1-98/2 Вариант №2 Адрес:
Москва, 1999 г. Содержание.
1. Введение 3
2. Задание на курсовой проект 4
3. Анализ и постановка задачи 4
4. Формализация задачи 5
5. Алгоритмы 6
5.1. Создание двухуровневого светового меню 6
5.2. Создание файла данных 7
5.3. Чтение файла данных 8
5.4. Добавление данных в файл данных 9
5.5. Печать сведений о суммарной стоимости продукции заданного вида по каждому предприятию и о среднем выпуске этой продукции одним предприятием. 10
5.6. Печать сведений о суммарной стоимости и суммарном выпуске каждой продукции. 11
5.7. Печать упорядоченного по суммарной стоимости списка продукции пяти видов 12
6. Программы 13
6.1. Создание двухуровневого светового меню 13
6.2. Создание файла данных 15
6.3. Чтение файла данных 16
6.4. Добавление данных в файл данных 17
6.5. Печать сведений о суммарной стоимости продукции заданного вида по каждому предприятию и о среднем выпуске этой продукции одним предприятием. 18
6.6. Печать сведений о суммарной стоимости и суммарном выпуске каждой продукции. 20
6.7. Печать упорядоченного по суммарной стоимости списка продукции пяти видов 21
7. Результаты решений 22
8. Заключение 29
9. Список литературы 30
Введение
Реляционные системы управления базами данных (СУБД), такие как FoxBase, FoxBase plus, FoxPro, Visual FoxPro относятся к новому поколению СУБД реляционного типа из семейства dBase – подобных СУБД. Пакеты этого семейства получили широкое распространение, и многие из них были русифицированы. СУБД типа Fox сохраняет преемственность по отношению к более ранним представителям dBase – подобных СУБД, в отношении структуры баз данных, команд создания и обработки данных, основных типов данных. В тоже время каждая последующая СУБД обладает большими возможностями по сравнению с предыдущими. Так, например, Visual FoxPro по сравнению с FoxPro обладает более значительными изобразительными возможностями. Данная работа использует язык команд СУБД семейства Fox. Используемые команды, в основном, применимы во всех СУБД этого типа, но отладка велась на русифицированной СУБД FoxPro для Windows версии 2.5b.
Задание на курсовой проект
Структура ЗАПИСИ исходного ДОКУМЕНТА: |Код предприятия |Вид продукции |Объем выпуска |Цена единицы | | | | |продукции |
Необходимо: 1. Определить суммарную стоимость продукции заданного вида и ее средний выпуск одним предприятием. 2. Для каждого из пяти видов продукции определить суммарную стоимость и суммарный выпуск. 3. Выдать на печать в порядке возрастания суммарной стоимости продукцию пяти видов.
Анализ и постановка задачи
Исходные данные задачи представляют собой записи заданной структуры, которые должны вводиться с клавиатуры, а затем выводиться в файл данных на магнитный диск. Следовательно, одной из подзадач должна быть задача создания файла данных на магнитном диске. Созданный файл данных необходимо просмотреть на экране или вывести на печать в виде таблицы с печатью заголовка и шапки этой таблицы. Для этого следующей подзадачей должна являться задача просмотра файла данных. Также должна быть возможность добавления записей в созданный файл данных. Затем необходимы еще три подзадачи, решение которых позволяет выполнить три пункта курсовой работы: 1. Выдача сведений о суммарной стоимости продукции заданного вида по каждому предприятию и о среднем выпуске этой продукции одним предприятием. 2. Выдача сведений о суммарной стоимости и суммарном выпуске каждой продукции. 3. Выдача на печать продукции пяти видов в порядке возрастания ее суммарной стоимости. Кроме того, для диалога пользователя с системой необходимо создать так называемое, «Меню».
Формализация задачи
В среде СУБД типа Fox каждая подзадача может оформляться в виде отдельного командного файла с расширением .prg и заканчиваться оператором возврата в вызывающий командный файл. В данном случае основным командным файлом является файл MainMenu.prg, который формирует полное экранное меню и осуществляет вызов других командных файлов, в зависимости от выбранного пункта меню: |CreateFd.prg |– создание файла данных; | |ReadFd.prg |– чтение созданного файла данных; | |AddFd.prg |– добавление данных в созданный файл данных; | |Zad1.prg |– выдача сведений о суммарной стоимости продукции| | |заданного вида по каждому предприятию и о среднем| | |выпуске этой продукции одним предприятием; | |Zad2.prg |– выдача сведений о суммарной стоимости и | | |суммарном выпуске каждой продукции; | |Zad3.prg |– выдача на печать продукции пяти видов в порядке| | |возрастания ее суммарной стоимости. |
Кроме того, необходимо предоставить пользователю возможность облегчить процесс создания файла данных, т.е. предусмотреть создание файла данных со структурой заданной в программе, а не выбираемой самим пользователем, что полностью исключит возможные ошибки пользователя в задании имен полей файла данных, что в сою очередь может сказаться на корректной работе всей программы.
Алгоритмы
1 Создание двухуровневого светового меню
2 Создание файла данных
3 Чтение файла данных
4 Добавление данных в файл данных
5 Печать сведений о суммарной стоимости продукции заданного вида по каждому предприятию и о среднем выпуске этой продукции одним предприятием.
6 Печать сведений о суммарной стоимости и суммарном выпуске каждой продукции.
7 Печать упорядоченного по суммарной стоимости списка продукции пяти видов
Программы
1 Создание двухуровневого светового меню
* Командный файл иерархического меню MainMenu set Talk off set Color to n/W* && Выбор цвета экрана Clear
* Описание массивов данных меню Declare GenMenu(3,2), menuFile(3), menuZad(3), menuExit(2)
* Задание значений элементов массивов GenMenu(1,1)=" Файл данных " GenMenu(1,2)="Работа с файлом данных" GenMenu(2,1)=" Задание " GenMenu(2,2)="Задания на курсовой проект" GenMenu(3,1)=" Выход " GenMenu(3,2)="Выход из программы"
menuFile(1)="Создание" menuFile(2)="Чтение" menuFile(3)="Добавление"
menuZad(1)="Задание №1" menuZad(2)="Задание №2" menuZad(3)="Задание №3"
menuExit(1)="Выход в Fox" menuExit(2)="Выход из Fox"
* Формировние главного меню Do While .T. set Color to gr+/g, gr+/b && Установка цвета меню Menu Bar GenMenu, 3 Read Menu Bar to L1, L2 && Вывод главного меню на экран Do While L1 > 0 && открыть подменю, если выбран && любой пункт главного меню * Формирование подменю set Color to gr+/g, gr+/b && Установка цвета подменю Menu 1, menuFile, 3,3 Menu 2, menuZad, 3,3 Menu 3, menuExit, 2,2 Read Menu Bar to L1, L2 && Вывод меню на экран set Color to n/W* && Возврат к цвету экрана
* Обработка выбранного пункта меню Do Case Case L1=0 Exit && Выход в панель главного меню Case L1=1 Do Case Case L2=1 && Выбрано действие 'Создание нового ФД' Do CreateFd Case L2=2 && Выбрано действие 'Чтение данных' Do ReadFd Case L2=3 && Выбрано действие 'Добавление новых данных' Do AddFd EndCase Case L1=2 Do Case Case L2=1 && Выбрано задание №1 из курсового проекта Do Zad1 Case L2=2 && Выбрано задание №2 из курсового проекта Do Zad2 Case L2=3 && Выбрано задание №3 из курсового проекта Do Zad3 EndCase Case L1=3 Do Case Case L2=1 && Выбран пункт 'Выход в Fox' Return Case L2=2 && Выбран пункт 'Выход из Fox' Quit EndCase EndCase EndDo EndDo
2 Создание файла данных
* Командный файл CreateFd - создание нового файла данных set Talk off set Status off set Escape off Clear Zag='Процесс создания нового файла данных' @ 4,22 to 4,58 Color u/w* @ 3,22 Say Zag Color u/w* @ 12,0 Accept ' Укажите имя создаваемого файла данных: ' to NameFd If Len(NameFd) > 0 && Если имя файла не ввели, то делать нечего
* Изменение заголовка Zag=Zag + ': ' + NameFd + '.dbf' LenZag=Int(Len(Zag)) @ 4,Int((80-lenZag)/2) to 4,Int((80-lenZag)/2)+LenZag Color u/w* @ 3,Int((80-LenZag)/2) Say Zag Color u/w* @ 14,0 Text Хотите автоматически создать пустую структуру с указанным именем, по заданию курсового проекта (Д/Н)? EndText
* Ответ на поставленный вопрос Do While .T. @ 16,57 Wait '' to ABC && Ожидание нажатия клавиши If ABC='н' Or ABC='д' ABC=Chr(Asc(ABC)-32) && Смена регистра EndIf If ABC='Н' Or ABC='Д' Exit EndIf EndDo
* Создание ФД If ABC='Д' && Автоматическое создание ФД Create Table &NameFd ; (KodOrg N(3,0), VidProd C(20), Volum N(4,0), Price N(6,2)) @ 8,0 set Talk on Display Structure && Вывод созданной структуры set Talk off Else && Создание ФД с возможностью заполнения полей Create &NameFd EndIf EndIf
* Конец работы @ 24,0 Wait 'Для возврата в меню нажмите любую клавишу ...' @ 24,0 Clear Return
3 Чтение файла данных
* Командный файл ReadFd - чтение файла данных set Talk off set Status off set Escape off Clear @ 4,27 to 4,54 Color u/w* @ 3,27 Say 'Процесс чтения файла данных' Color u/w* @ 12,0 Accept ' Введите имя считываемого файла данных: ' to NameFd If Len(NameFd) >0 && Если имя файла не ввели, то делать нечего
* Изменение заголовка @ 3,0 Clear to 5,79 Zag='Содержимое файла данных: ' + NameFd + '.dbf' LenZag=Int(Len(Zag)) @ 4,Int((80-lenZag)/2) to 4,Int((80-lenZag)/2)+LenZag Color u/w* @ 3,Int((80-LenZag)/2) Say Zag Color u/w*
* Вывод содержимого файла Use &NameFd Do While .Not.EOF() && Цикл вывода порций записей ФД && В определенную область экрана @ 7,0 Display Next 15 If EOF()=.F. && В последнем цикле не нужно переводить && указатель и держать паузу Skip && Перевод указателя, чтобы новый экран не начинался && с последней записи предыдущего экрана @ 24,0 Wait 'Нажмите любую клавишу для просмотра следующих 15 записей ...' EndIf EndDo Close DataBases && Закрытие ФД EndIf
* Конец работы @ 24,0 Wait 'Для возврата в меню нажмите любую клавишу ...' @ 24,0 Clear Return
4 Добавление данных в файл данных
* Командный файл AddFd - добавление файла данных set Talk off set Status off set Escape off Clear @ 4,25 to 4,56 Color u/w* @ 3,25 Say 'Процесс добавления файла данных' Color u/w* @ 12,0 Accept ' Введите имя файла данных для добавления данных: ' to NameFd If Len(NameFd) >0 && Если имя файла не ввели, то делать нечего
* Изменение заголовка @ 3,0 Clear Zag='Добавление данных в файл данных: ' + NameFd + '.dbf' LenZag=Int(Len(Zag)) @ 4,Int((80-lenZag)/2) to 4,Int((80-lenZag)/2)+LenZag Color u/w* @ 3,Int((80-LenZag)/2) Say Zag Color u/w*
* Добавление данных в ФД Use &NameFd Append Close DataBases && Закрытие ФД EndIf
* Конец работы @ 24,0 Wait 'Для возврата в меню нажмите любую клавишу ...' @ 24,0 Clear Return
5 Печать сведений о суммарной стоимости продукции заданного вида по каждому предприятию и о среднем выпуске этой продукции одним предприятием.
* Командный файл Zad1 - печать сведений о заданной продукции set Talk off set Status off set Escape off Clear @ 4,18 to 4,62 Color u/w* @ 3,18 Say 'Процесс печати сведений о заданной продукции' Color u/w* @ 12,0 Accept ' Введите имя файла данных: ' to NameFd @ 12,0 Clear @ 12,0 Accept ' Введите вид продукции: ' to TypeProd If Len(NameFd) >0 And Len(TypeProd) > 0 && Если имя файла или && вид продукции не ввели, && то делать нечего * Изменение заголовка @ 3,0 Clear Zag='Сведения о продукции: ' + TypeProd LenZag=Int(Len(Zag)) @ 4,Int((80-lenZag)/2) to 4,Int((80-lenZag)/2)+LenZag Color u/w* @ 3,Int((80-LenZag)/2) Say Zag Color u/w* Use &NameFd
* Формирование шапки L='+-----------------+---------------+--------+-----------+' @ 7,12 Say L @ 8,12 Say '| Код предприятия | Объем выпуска | Цена | Стоимость |' @ 9,12 Say L Row=10 && Текущий номер строки для вывода данных Do While .Not.EOF() If VidProd=TypeProd
* Формирование строки @ Row,12 Say '|' @ Row,20 Say KodOrg @ Row,30 Say '|' @ Row,36 Say Volum Picture '# ###' @ Row,46 Say '|' @ Row,48 Say Price Picture '###.##' @ Row,55 Say '|' @ Row,57 Say Volum*Price Picture '## ###.##' @ Row,67 Say '|' Row=Row+1 EndIf Skip EndDo
* Формирование итоговой части таблицы @ Row,12 Say L Row=Row+1
* Расчет суммарной стоимости Sum Volum*Price For VidProd=TypeProd to AllPrice
* Расчет среднего выпуска Average Volum For VidProd=TypeProd to AvVol @ Row,29 Say 'Общая суммарная стоимость:' @ Row,56 Say AllPrice Picture '### ###.##' @ Row+1,21 Say 'Средний выпуск одним предприятием:' @ Row+1,58 Say AvVol Picture '# ###' Close DataBases && Закрытие ФД EndIf
* Конец работы @ 24,0 Wait 'Для возврата в меню нажмите любую клавишу ...' @ 24,0 Clear Return
6 Печать сведений о суммарной стоимости и суммарном выпуске каждой продукции.
* Командный файл Zad2 - печать сведений об объемах и стоимости продукции set Talk off set Status off set Escape off Clear @ 4,15 to 4,64 Color u/w* @ 3,15 Say 'Процесс печати сведений об объемах всей продукции' Color u/w* @ 12,0 Accept ' Введите имя файла данных: ' to NameFd @ 12,0 Clear If Len(NameFd) >0 && Если имя файла не ввели, то печатать нечего Use &NameFd
* Формирование шапки таблицы L='+---------------------+---------------+---------------------+' @ 7,10 Say L @ 8,10 Say '| Вид продукции | Общий объем | Суммарная стоимость |' @ 9,10 Say L
* Сортировка данных по виду продукции Index On VidProd to &NameFd && Создание индексного файла Use &NameFd Index &NameFd
* Формирование строк таблицы Row=10 && Текущий номер строки для вывода данных Do While .Not.EOF() VP=VidProd RNom=RecNo() && Запомнить номер текущей записи Sum Volum For VidProd=VP to AllVol && Общий объем Sum Volum*Price For VidProd=VP to AllPrice && Суммарная стоимость GoTo RNom && Вернуться на текущую запись @ Row,10 Say '|' @ Row,12 Say VidProd @ Row,32 Say '|' @ Row,37 Say AllVol Picture '### ###' @ Row,48 Say '|' @ Row,55 Say AllPrice Picture '### ###.##' @ Row,70 Say '|'
* Пропуск записей с отработанным видом продукции Do While VidProd = VP And .Not.EOF() Skip EndDo Row=Row+1 EndDo
* Формирование итоговой части таблицы @ Row,10 Say L Close DataBases && Закрытие ФД Delete File NameFd + '.idx' && Удаление индексного файла EndIf
* Конец работы @ 24,0 Wait 'Для возврата в меню нажмите любую клавишу ...' @ 24,0 Clear Return
7 Печать упорядоченного по суммарной стоимости списка продукции пяти видов
* Командный файл Zad3 - печать упорядоченных сведений о стоимости продукции set Talk off set Status off set Escape off Clear @ 4,9 to 4,71 Color u/w* @ 3,9 Say 'Печать сведений о суммарной стоимости продукции по возрастанию' Color u/w* @ 12,0 Accept ' Введите имя файла данных: ' to NameFd @ 12,0 Clear If Len(NameFd) >0 && Если имя файла не ввели, то печатать нечего Use &NameFd
* Формирование шапки таблицы L='+---------------------+---------------------+' @ 7,17 Say L @ 8,17 Say '| Вид продукции | Суммарная стоимость |' @ 9,17 Say L
* Поиск продукции с наименьшим значением стоимости Store 0 to MinAP, LastAP For I=1 to 5 && Цикл для пяти видов продукции Do While .Not.EOF() && Цикл поиска нового минимума VP=VidProd && Текущий вид продукции RNom=RecNo() && Текущая запись Sum Volum*Price For VidProd=VP to AllPrice If AllPrice > LastAP If AllPrice < MinAP Or MinAP=0 MinAP=AllPrice MinVP=VP EndIf EndIf If RNom < RecCount() GoTo RNom+1 && Переход на следующую запись EndIf EndDo
* Формирование строки таблицы @ 9+I,17 Say '|' @ 9+I,19 Say MinVP @ 9+I,39 Say '|' @ 9+I,46 Say MinAP Picture '### ###.##' @ 9+I,61 Say '|' LastAP=MinAP && Предыдущее минимальное значение && (нижняя граница минимальных значений) MinAP=0 GoTo Top && Возобновить просмотр с первой строки Next * Формирование итоговой части таблицы @ 15,17 Say L Close DataBases && Закрытие ФД EndIf * Конец работы @ 24,0 Wait 'Для возврата в меню нажмите любую клавишу ...' @ 24,0 Clear Return
Результаты решений
Выбор создания файла данных
|1 |Ручка |1000 |2,00 | |1 |Карандаш |500 |1,50 | |1 |Фломастер |1000 |4,70 | |1 |Чернила |500 |3,00 | |2 |Ручка |1200 |1,85 | |2 |Фломастер |750 |5,00 | |2 |Ластик |5000 |1,20 | |2 |Карандаш |1500 |1,35 | |3 |Чернила |400 |3,20 | |3 |Ручка |800 |1,90 | |3 |Карандаш |1200 |1,40 | |3 |Фломастер |2000 |4,50 | |4 |Ручка |900 |1,85 | |4 |Ластик |200 |2,00 | |4 |Фломастер |1400 |4,70 | |4 |Чернила |500 |3,05 | |5 |Карандаш |700 |1,45 | |5 |Чернила |1100 |2,60 | |5 |Ластик |1400 |1,65 | |5 |Фломастер |500 |5,30 |
Выбор чтения файла данных
Выбор добавления данных в файл данных
|6 |Ластик |600 |1,55 | |6 |Чернила |800 |3,10 | |6 |Карандаш |1000 |1,55 |
Выбор выполнения Задания №1
Выбор выполнения Задания №2
Выбор выполнения Задания №3
Выход из СУБД
Заключение
Реляционные СУБД, такие как FoxPro действительно являются мощным средством управления большим объемом данных. СУБД этого типа позволяют производить быструю сортировку большого массива данных, осуществлять быстрый переход по записям в произвольном порядке, производить быструю выборку большого количества данных из всего массива данных по заданным критериям. В таких реляционных СУБД каждый файл данных рассматривается как двумерная таблица, столбцы которой соответствуют полям записей, а строки соответствуют отдельным записям файла и обращение к данным идет через указание номера записи имени поля. При этом работа с отдельным полем таблицы данных напоминает работу с переменными – обращение к данным максимально упрощено, и пользователю не нужно знать всю иерархическую структуру данных.
Язык команд СУБД семейства Fox содержит широкий набор команд, выполняющих действия сложных конструкций, например, сортировка записей файла сводится только к двум командам. Помимо этого в СУБД предусмотрены команды создания светового меню для организации прямого диалога с пользователем. Все это максимально упрощают написание программ и подтверждает, что реляционные СУБД семейства Fox действительно являются мощным инструментом для создания и обработки баз данных большого объема.
Список литературы
1. Лемашко Е.В., Романчуков В.Г. Программирование в системе команд СУБД семейства Fox: учебное пособие / ГАУ, М., 1998.
2. Компьютерный практикум. Программирование в среде Турбо-Паскаль и СУБД типа Fox. Методические указания к выполнению курсового проекта. /Сост.: О.Н. Леонова, И.А. Несмеянов; ГАУ, М.,1998.
----------------------- Do While .Not.EOF()
Запрет реакции команд Задание цвета экрана
Len(NameFd) >0
Len(NameFd) >0
Wait
Формирование главного меню
Выбор пункта главного меню
Выбор пункта подменю
Do While .T.
Формирование подменю
Case
L1=0
Exit
L1=1
L1=2
L1=3
Case
L2=3
L2=2
L2=1
AddFd
ReadFd
CreateFd
VidProd=TypeProd
Вывод шапки таблицы
Zad3
Zad2
Zad1
L2=3
L2=2
L2=1
Case
True
Ввод вида продукции, TypeProd
Quit
Return
Очистка экрана
L2=2
L2=1
Case
Конец
False
Do While .T.
Начало
True
Wait
Запрет вывода реакции команд Запрет изменения строки состояния Запрет прерывания выполнения программы
Ввод имени ФД, NameFd
Wait
Return
Do While .Not.EOF()
False
False
Return
Wait
Return
Начало
Wait
False
True
Вывод вопроса
Чтение 15 записей из ФД
Запрет вывода реакции команд Запрет изменения строки состояния Запрет прерывания выполнения программы
Изменение заголовка
Изменение заголовка
ABC=’Д’
Формирование заголовка
Формирование заголовка
Очистка экрана
Очистка экрана
Create &NameFd
False
Create Table &NameFd ()
True
Ввод имени ФД, NameFd
Append
Ввод имени файла, NameFd
Ввод ответа (Д/Н) to ABC
Запрет вывода реакции команд Запрет изменения строки состояния Запрет прерывания выполнения программы
Начало
Изменение заголовка
Формирование заголовка
Очистка экрана
Len(NameFd) >0
Начало
True
False
Return
Запрет вывода реакции команд Запрет изменения строки состояния Запрет прерывания выполнения программы
Ввод имени ФД, NameFd
Переход на следующую запись
Изменение заголовка
Формирование заголовка
Очистка экрана
Len(NameFd) >0 And Len(TypeProd)>0
Начало
True
Вывод строки таблицы
2
1
1
2
Вывод заключения таблицы
AvVol=Average(Volum)
AllPrice=Sum(Volum*Price)
Вывод AllPrice AvVol
Wait
False
Return
Запрет вывода реакции команд Запрет изменения строки состояния Запрет прерывания выполнения программы
Ввод имени ФД, NameFd
2
1
Формирование заголовка
Очистка экрана
Len(NameFd) >0
Начало
True
Вывод строки таблицы
Вывод шапки таблицы
Вывод заключения таблицы
Сортировка по полю VidProd с помощью индексного файла
Do While .Not.EOF()
AllVol=Sum(Volum)
Вывод заключения таблицы
AllPrice=Sum(Volum*Price)
Переход на запись с новым видом продукции
1
2
1
2
Wait
Return
1
[pic]
Переход на следующую запись
AllPrice=Sum(Volum*Price)
Store 0 to MinAP, LastAP
Начало
Do While .Not.EOF()
For I=1 to 5
Вывод в строке таблицы MinVP, MinAP
Вывод шапки таблицы
False
Запрет вывода реакции команд
Ввод имени ФД, NameFd
Формирование заголовка
Очистка экрана
Len(NameFd) >0
True
Переход к первой записи
LastAP=MinAP
[pic]
Запрет прерывания выполнения программы
Запрет изменения строки состояния
2
VP=VidProd
AllPrice>LastAP
AllPrice1. Sprend?iant rekurentin? formul? galim u?ra?yti: f(n) ( f( (n/2( ) + 1 ( f( (n/21( ) + 1(( f( (n/22( )+1) + 1 ( f( (n/22( )+2 (...( f( (n/2i( ) + i, kol ( n/2i ((1; i((logn(. f(n)((logn(+1 arba f(n) ( (log (n+1)( . Vid. palyginim? sk. ideliu atveju kai n ( 2k-1: f(n)(1* 1/n + 2*2/n + 3*4/n +...+ ((log n( + 1)*2k-1/n ( 1/n * (i(1(log n(+1 (i * 2i-1). 2k-1-11 dideliems n).
Balansavimas (skaidymas ? vienodas dalis). Reikia sur??iuoti n ilgio masyv? did?jimo tvarka. 1.surandam min, kur? sukei?iam su pirmu, po to i? (n-1) elemento surandam min ir sukei?iam su antru ir t.t.. Rekursyvin? lygtis apra?anti palyginim? sk.: T(n) ( {0, n(1T(n-1)+n-1, n>1 ; T(n) ( n(n-1)/2, o algoritmo sud?tingumas ((n2). ?ia skaldymas ? dvi nelygias dalis: ? vieno elemento ir (n-1).2. Gaunamas suskald?ius u?davin? ? dvi lygias dalis ( n/2. Tarkim, kad n ( 2k. Viena dalis nuo x1 iki xn/2 , o kita nuo xn/2+1 iki xn. ?ias dalis sur??iuojam ir sujungiam palyginant minimalius elementus. Sujungimui reiks maksimum n-1 palyginim?. Tok? skaidym? galima rekursyviai t?sti toliau, kol lieka dalyse po 1 element?. Rekursyvin? lygtis apra?anti tok? algoritm? yra: T(n) ( {0, n(1 2T(n/2) + n - 1, n>1. ?io algoritmo sud?tingumas (( n log n).
Dinaminis programavimas. Kartais galima efektyvius algoritmus gauti naudojant dinamin? programavim?. ?iuo b?du reik?t? skai?iuoti visus dalinius u?davnius, bet sprend?iami nuo ma?? prie dideli?. Atsakymai prisimenami lentel?je ir u?daviniai jungiami, kad b?t? i?spr?stas visas u?davinys ir gautas optimumas. Pvz. sudauginant n matric? yra labai svarbus daugybos eili?kumas, kuris nulemia bendr? veiksm? skai?i?. Pa?ymim mi j minimalus veiksm? sk. dauginant matricas: Mi*Mi+1*...*Mj, kur 1 ( i < j ( n. Kai M ( M1*M2*...*Mn, tai j? mati?kumas yra r0*r1*r2*...*rn. mi j ( {0, i(j MIN( mik + mk+1, j + ri-1 rk rj ), j > i, i ( k < j (1). M` (Mi*Mi+1*...*Mk, [ri-1*rk]. Min vei-ksm? sk. mi,k. M``(Mk+1 *Mk+2 *... * Mj, [rk*rj]. Atliekant ?i? daugyb? min veiksm? sk. mk+1, j, o sudauginant M` su M``, min veiksm? sk. ri-1 rk rj. Tai atliekam tol kol negaunam m1n.1-a lygtis ya dinaminio programavimo rekurentin? lygtis. mi,j reik?m?s skai?iuojamos tvarka, kai did?ja indeks? sk. I? prad?i? skai?iuojam mi,i( 0 (visiem i), toliau mi, i+1, po to mi, i+2, kol neprieinam m1n.
R??IAVIMO ALGORITMAI
K-ma?i? korte?? r??iavimas Tegul mes turime sek? A1 A2 ... An k-ma?i? korte??, t.y., A erdvinis Ai elementas, sudarytas i? ai1 ai2 ... aik.Reikia ?i? sek? r??iuoti taip: B1 B2 ... Bn, kad visiem i Bi ( Bi+1. R??iavimas atliekamas k kart? pereinant per duot? sek?. Pirm? kart? atliekamas r??iavimas pagal k-?j? komponent?. Antr? kart? pagal (k-1) komponent? ir t.t. Pr?jus pagal i-?j?, tur?sim s?ru?iuot? sek?. Kiekviena skiltis ai j yra nuo 0 iki m-1. Reikia organizuoti m pagalbini? eili? Q(j), kur j ( 0,...,m-1, kurios i? prad?i? turi b?ti tu??ios. Duomenis A1 A2 ... An i? prad?i? sura?om ? s?ra?? EIL?. Paimam eilin? korte?? Ai i? EIL?S ir patalpinam ? pagalbin? eil? Q(j) pagal analizuojamos komponent?s reik?m?. Taip darom tol, kol bendra EIL? i?tu?t?ja. Visi korte?ai atsiduria pagalbin?se eil?se. Po to jie suduriami: Q(0) Q(1)...Q(m-1) ir jie sudaro vien? bendr? eil? EIL?. Kai praeinam pro visas komponentes, tai EIL? bus sur??iuota. Algoritmo sud?tingumas yra tiesinis ([(n+m)/k]. Naudoti ?? metod? neverta, kai n yra ma?as.
Nevienodo ilgio korte?? r??iavimas Kad suvienodinti korte?? ilgius galima priekyje prira?yti nulius, ta?iau tai ne efektyvu, nes bus bereikaling? daug per?i?r?jim?. Tuomet tegul lmax- korte?? maksimalus ilgis, tai reikia i? prad?i? sur??iuoti maksimalaus ilgio korte?us pagal l max paskutin? komponent?. Reik?s lmax kart? r??iuoti visus korte?us.Antr? kart? reikia r??iuoti korte?us, kuri? ilgis lmax -1 ir jau sur??iuotus pagal paskutin? komponent?, kuri? ilgis lmax. Ir paskutin? kart? lmax per?jus per vis? s?ra??, bendram s?ra?e bus sur??iuota seka. Pastabos: 1. Prie? naudojant ?? algoritm?, visi korte?ai turi b?ti i?skirstyti pagal ilgius. Tam formuojami s?ra?ai ILGIS(l), kur l ( 1,...,lmax, kuriuose sura?yti atitinkamo ilgio korte?ai. Pirmame ?ingsnyje r??iuojamas tik s?ra?as ILGIS(lmax) pagal paskutin? komponent?. 2. Be to matom, kad pra?jus kart? pro vien? komponent? gali b?ti daug pagalbini? eili? Q(i) (kur i ( 0,1,...,m-1) tu??ios. Ne?i?rint to jas visas reikia jungti ? bendr? s?ra??, tod?l naudinga b?t? i? prad?i? nustatyti kurios pagalbin?s eil?s bus netu??ios ir tik jas jungti ? vien? bendr? s?ra??.
R??iavimas lyginant elementus “Burbuliuko” metodas. Paprastai elementai r??iuojami pagal raktin? ?od?. Tarkim turim K1..K16 element? ir lyginame K1 >K2. Jeigu daugiau sukei?iam vietom. Jeigu ne nieko nedarom ir t.t. Paskutinis palyginimas bus Km > Kn. Po 1 iteracijos did?iausias skai?ius atsiranda pabaigoje. Sekanti iteracija vyksta su n-1 elementu, nes paskutinio neimame ir t.t. Pirmoje iteracijoje bus (n-1) palyginim?. Antroje iteracijoje (n-2), i- tojoje iteracijoje (n-i). Tuomet bendras palyginim? skai?ius bus [pic] Kadangi ne visuomet elementai sukei?iami, tuomet jeigu i?r??iuota seka bus 0 pakitim?, o atvirk??iai i?r??iuota seka - n(n-1)/2 pakeitim?. Tada vidutinis pakeitim? sk. bus n(n-1)/4. Jeigu yra n element? seka, tai i? jos gali b?ti padaryti n! sek?. Mes laikome kad bet kuri seka gali pasitaikyti su vienoda tikimybe 1/n!. Kiekvienai sekai galima para?yti inversi?k? sek?. Jeigu turime tokias 2 sekas, ir jas sur??iuosime, tai sumalinis pakeitim? sk. bus n(n-1)/4. Algoritmo sud?tingumas ((n2). Iterpimo metodas. ?ia eilinis elementas yra ?terpiamas ? jau sur??iuot? elemet? sek?. Tegul turime n element? i? viso ir turime jau i sur??iuot? element?. Mums reikia ?terpti i+1 element? Ki+1. Ki+1 atsidurs tarp Kj < Ki+1 < Kj+1 element?. ?statant i+1 element? mums reik?s max palyginim? (su 1, su 2…).Max palyginim? sk. b?t?: [pic]Pagal tai ir algoritmo sud?tingumas bus ((n2).Vidutini?kai bus ma?iau palyginim?.?iuo b?du r??iuojant masyvus (paprastus) patogiau prad?ti elemt? lyginim? nuo sur??iuotos sekos pabaigos. Tai yra nuo i-tojo elemento. Panagrin?kime koks ?iame algoritme yra vidutinis palyginim? sk. Tegul turime i sur??iuot? elemt? ir reikia ?statyti I+1 element?. Pirmiau lyginsime su 1 elememtu. Yra i+1 pozicijos, ? kurias galima ?statyti i+1 element? ir priekyje ir gale. Laikome, kad i+1 elementas ? bet kuri? pozicij? gali patekti su vienoda tikimybe 1/(i + 1). Vidutinis palyginim? sk. ?statant element? bus: [pic]jei patenka ? paskutin? prie? pirm?j? pozicij? element? (gale) =1/(i+1)(1+2+…+i+i) = 1/(i+1)*((i+1)/i ) /2 + i / ( i + 1 ) = i / 2 + i / ( i + 1 ) Tiek pagal max,tiek pagal vidutin? palyginim? skai?i? ?io algoritmo sud?tingumas yra ((n2)
Ekspermentinis statistinis algoritm? tyrima.s ?iuo metodu pvz. tiriant r??iavimo algoritmus mums reikia para?yti atitinkam? program?, paiimti atsitiktin? sek? i? n duomen? ir atlikti skai?iavimus, pvz.: fikstuoti laik? t1, po to paimame kit? sek? ir gauname laik? t2 po to paimame kit? sek? taip pat i? n duomen? ir gauname laik? t3 ir tokius bandymus kartojame k kart?. Gauname atsitiktini? dyd?i? imt? t1, t2, …. tk. Vidurkis bus ( = 1/K(i(1K (ti), vidurkis - atsitiktinis dydis. Dirpersija bus : S2(t)=[pic]i-t)2= =[pic]ti2-2(t ti +(t2) = =[pic] ti2- 2t[pic]ti+K(t2]= =[pic][pic]ti2-2([pic][pic]ti)* *[pic]ti + K/K2 ([pic]ti)2] = [pic]* *[ [pic]ti2 - [pic]( [pic]ti)2] ?i dispersijos fomul? patogesn? ma?ininiuose skai?iavimuose, nes su kiekvienu nauju atsitiktiniu dyd?iu ti mes kaupiame tik dvi sumas : (ti ir (ti2.(t - atvirk?tinis dydis ir jis vertina tam tikr? matematin? vilt?.(t dispersija yra tokia: D((t )= D [[pic][pic]ti] = 1/K2[pic] D(ti) = 1/K*D(t); D - tikroji dispersija;S-?vertinimas.S2((t)=S2(t)/K arba i?traukus ?akn?: S(t) = S(t)/[pic]; |(t - m| a2 Jei a6 < a3, tai reikia palyginti ir ar a3 > a6 Radom max per 2 palyginimus. Pirami-d?je radom per n-1 palyginim?. Tai yra sekantis randamas per (log n( -1 palygi-nim?. Gauname, kad ?iuo metodu palygi-nim? sk. yra optimalus: n + (log n( - 2 .
Geriausio (max) ir blogiausio (min) elemento i?rinkimas Galima si?lyti suskaidyti sek? n ? 2 dalis ir sura?yti ?iose dalyse max ir min elementus. Palyginus max-ius elementus gaunamas max-is elementas, min- ius -min-is. Rekursyviai galima suskaidyti iki 1,2 element?. Palyginant 2 elementus tarpusavyje i? karto gauname max ir min elementus. Rekurentin? lygtis, apra?anti tok? akgoritm?: f(n)=[pic] Bendras ?ios srities sprendinys: |[pic|(n-2(log | |] |n()/2, kai| | |n =k, tai imame S1, kuriame yra (i- 1) ele-t?. Jei i | |