|
Реферат: Алгоритмизация и программирование процессов на 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 | |
