ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6814
Скачиваний: 51
286
repeat
while a[i]<x do i:=i+l; while x<a[j] do j:=j-l;
if i<=j then begin y:=a[i]; a[i]:=a[j];
a[j]:=y; i:=i+l; j:=j-1;
end;
until i>j ;
if L<j then SORT(L,j); if i<R then SORT(i.R); ' end;
begin , . (*задание искомого массива*) for i:=l to N do begin
write("Bвeди элемент a[',i, ']=');
readln(a[i]);
end;
for i:=l to N do begin write(a[i],' ');
end;
writeln;
(*алгоритм быстрой сортировки*) SORT(l,n);
(*рекурсивная процедура*) (*вывод отсортированного масси-
ва*) for i:=l to N do begin write(a[i],' ');
end;
readln;
end.
Сортировка файлов
. Главная особенность методов сортировки последовательных файлов
в том, что при их обработке в каждый момент непосредственно доступна одна компонента (на ко-
торую оказывает указатель). Чаще процесс сортировки протекает не в оперативной памяти, как в
случае с массивами, а с элементами на внешних носителях («винчестере», дискете и т.п).
Понять особенности сортировки последовательных файлов на внешних носителях позволит
следующий пример.
Предположим, что нам необходимо упорядочить содержимое файла с последовательным
доступом по какому-либо ключу. Для простоты изучения и анализа сортировки условимся, что
файл формируем мы сами, используя как и в предыдущем разделе некоторый массив данных. Его
же будем использовать и для просмотра содержимого файла после сортировки. В предлагаемом
ниже алгоритме необходимо сформировать вспомогательный файл, который позволит осущест-
вить следующую процедуру сортировки. Сначала выбираем из исходного файла первый элемент в
качестве ведущего, затем извлекаем второй и сравниваем с ведущим. Если он оказался меньше,
чем ведущий, то помещаем его во вспомогательный файл, в противном сл\чае во вспомогательный
файл помещается ведущий элемент, а его замещает второй элемент исходного файла. Первый про-
ход заканчивается, когда аналигичная процедура коснется всех последовательных элементов ис-
ходного файла. Ведущий элемент заносится во вспомогательный файл последним. Теперь необхо-
димо поменять местами исходный и вспомогательный файлы. После
nil
проходов в исходном фай-
ле данные будут
размещены в
упорядоченном виде.
Программа 52
program sortirovka_faila_l;
(сортировка последовательного файла) const N=8;
type item= integer;
var a: array[l..n] of item; i,k: integer; x,y: item;
fl,f2: text; (file of item);
begin
(задание искомого массива} for i:=l to N do begin write('введи
элемент а[ ',i,']=');
readin(a[i]);
end;
writein; assign(fl, 'datl.dat'); rewrite(fl);
assign(f2, 'dat2.dat'); rewrite(f2);
(формирование последовательного файла) for i:=l to N do begin
writein(fl,a[i]);
end;
(алгоритм сортировки с использованием вспомогательного файла) for
k:=l to (n div 2) do
287
begin (извлечение из исходного файла и запись во вспомогательный)
reset(fl); readin(fl,x);
for i:=2 to n do begin readln(fl,y);
if x>y then writein(f2,y) else begin writein(f2,x); x:=y;
end;
end;
writein(f2,x) ;
(извлечение из вспомогательного файла и запись в исходный) rewrite(fl);
reset(f2); readin(f2,x);
for i:=2 to n do begin readin(f2,у);
if x>y then writein(fl,y) else begin writein(f1,x); x:=y;
end;
end;
writeln(fl,x); rewrite(f2);
end;
(вывод результата} reset(fl);
for i:=l to N do readin(f1,a[i]);
for i:=l to N do begin write(a[i], ' ');
end;
close(fl); close(f2); readin;
end.
По сути можно в программе обойтись без массива а[1..п]. В качестве упражнения попытай-
тесь создать программу, в которой не используются массивы.
Многие методы сортировки последовательных файлов основаны на процедуре
слияния,
оз-
начающей объединение двух (или более) последовательностей в одну, упорядоченную с помощью
повторяющегося выбора элементов (доступных в данный момент). В дальнейшем (чтобы не осу-
ществлять многократного обращения к внешней памяти), будем рассматривать вместо файла мас-
сив данных, обращение к которому можно осуществлять строго последовательно. В этом смысле
массив представляется как последовательность элементов, имеющая два конца, с которых можно
считывать данные. При слиянии можно брать элементы с двух концов массива, что эквивалентно
считыванию элементов из двух входных файлов.
Идея слияния заключается в том, что исходная последовательность разбивается на две по-
ловины, которые сливаются вновь в одну упорядоченными парами, образованными двумя элемен-
тами последовательно извлекаемых из этих двух подпоследовательностей. Вновь повторяем деле-
ние и слияние, но упорядочивая пары, затем четверки и т.д. Для реализации подобного алгоритма
необходимы два массива, которые поочередно (как и в предыдущем примере) меняются ролями в'
качестве исходного и вспомогательного.
Если объединить эти два массива в один, разумеется двойного размера, то программа уп-
рощается. Пусть индексы i и j фиксируют два входных элемента с концов исходного массива, k и
L - два выходных, соответствующих концам вспомогательного массива. Направлением пересылки
(сменой ролей массивов) удобно управлять с помощью булевской переменной, которая меняет
свое значение после каждого прохода, когда элементы
а\, ...,
а„ движутся на место Оп+ь ...,
а^
и
наоборот. Необходимо еще учесть изменяющийся на каждом проходе размер объединяемых упо-
рядоченных групп элементов. Перед каждым последующим проходом размер удваивается. Если
считать, что количество элементов в исходной последовательности не является степенью двойки
(для процедуры разделения это существенно), то необходимо придумать стратегию разбиения на
группы, размеры которых q и г могут не совпадать с ведущим размером очередного прохода. В
окончательном виде алгоритм сортировки слиянием представлен ниже.
Программа 53
program sortirovka_faila_2;
(сортировка последовательного файла слиянием} const N=8;
type item= integer; var a: arrayd. ,2*n] of item;
i, j, k, L, t, h, m, p, q,^r: integer; f: boolean;
begin
(задание искомого массива}
for i:=l to N do begin write( 'введи элемент а[ ',i,
']='}!
readln(a[i]) ;
288
end;
writein;
(сортировка слиянием) f:=true; p:=l;
repeat
h:=l; т^п; if f then begin
i:=l; j:-n;k:=n+l; L:=2*n end else begin k:=l;
L:=n;i:=n+l; j:-2*n
end; . repeat
if m>=p then q:=p else q:»m; m:=m-q;
if m>=p then r:=p else r:=m; m:=in-r;
while (q<>0) and (r00) do begin
if a[i]<a(j] then begin a[k]:=a(i]; k:=k+h;
i:=i+l;q:=q-l
end else
begin a[k]:=a[j]; k:=k+h; j:=j-l;r:=r-l end;
end;
while r>0 do begin a[k]:=atj]; k:°k+h; j:=j-l; r:»r-l;
end;
while q>0 do begin
a[k]:=a[i]; k:°k+h; i:=i+l; q:=q-l;
end;
h:=-h; t:=k;k:=L; L:=t;
until m=0;
f:=not(f); p:°2*p;
until p>=n;
if not(f) then for i:=l to n do a[i]:=a[i+n] ;
(вывод результата} . for i:=l to N do begin
write(a[i], ' ');
end;
readin;
end.
Рассмотренные два предыдущих примера иллюстрируют большие проблемы сортировки
внешних файлов, если в них часты изменения элементов, например, удаления, добавления, кор-
ректировки существующих.
В подобных ситуациях эффективными становятся алгоритмы, в которых обрабатываемые
элементы представляются в виде структур данных, удобных для поиска и сортировки. В качестве
структур данных можно отметить, в частности, линейные списки, очереди, стеки, деревья и т.п. О
них было рассказано в предыдущем разделе.
Контрольные вопросы и задания
1. Как в общем случае формулируется задача поиска? сортировки?
2. Почему внутренняя и внешняя сортировки реализуются разными методами?
3. В чем состоят принципы линейного поиска? поиска делением пополам?
4. Какие вы знаете методы внутренней сортировки?
5. Как соотносятся эффективности различных методов сортировки массивов?
6. В чем состоит принцип метода слияния упорядоченных файлов?
7. Разработайте программу упорядочивания списка группы студентов:
а) методом прямого включения;
б) методом выбора;
в) методом обмена.
§ 5. БЕЙСИК КАК ЯЗЫК ОПЕРАЦИОНАЛЬНО-ПРОБЛЕМНО-
ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ
У языка Бейсик (Basic) весьма своеобразная судьба. Будучи созданным для, так называе-
мых, непрофессиональных программистов, многократно раскритикованный почти каждым пишу-
щим о программировании, он живет \же четверть века и продолжает иметь множество пусть не
289
поклонников, но пользователей. В своих старших версиях он давно перестал быть столь «про-
стым» как его принято почему-то представлять. Его возможности чрезвычайно велики, о чем
можно судить хотя-бы по названию одной из недавно вышедших книг - «Разработка экспертных
систем на языке Бейсик». На нем создают программы самой различной предметной ориентации.
По-видимому, Бейсик продолжает лидировать по количеству пользователей, и хотя бы поэтому
знакомство с ним необходимо.
В данном учебнике нет регулярного, «по-порядку». изложения Бейсика. Для человека, ос-
воившего Паскаль, приведенного ниже в этом параграфе текста достаточно, чтобы составить себе
отчетливое представление о Бейсике. Количество же учебников по нему столь велико, что нет
смысла приводить их список - достаточно заглянуть в любой библиотечный каталог.
Даже при беглом знакомстве обращает на себя внимание некоторая «недисциплинирован-
ность» Бейсика - с точки зрения программиста, привыкшего к структурному языку семейства Пас-
каля. Бейсик относится к языкам операциональным, рожденным от вечно живого Фортрана, в ко-
торых необязательно (хотя и вполне возможно) организовывать строго упорядоченные программ-
ные структуры. Это и большой недостаток (особенно при разработке крупных программных ком-
плексов), но иногда и достоинство - например, при разработке относительно небольшой диалого-
вой программы с регулярным обращением к внешним устройствам, сканированием клавиатуры и
т.п.
Еще одна проблема, систематически возникающая при работе с Бейсиком - обилие версий и
фактическое отсутствие базовой версии. Оставив обзор до конца данного параграфа, укажем лишь,
что многие команды и функции в разных версиях сильно различаются, а иногда, существуя в од-
ной, вовсе отсутствуют в другой. Это следует иметь в виду, если приведенные ниже примеры бу-
дут не просто анализироваться, а выполняться на ЭВМ, или по их аналогии будут разрабатываться
собственные программы. Справочник по реально используемой версии в таком случае просто не-
обходим.
Тексты приведенных в качестве примеров программ отлажены в широко распространенной
версии языка QuickBasic.
5.1. ВВЕДЕНИЕ В БЕЙСИК
Выполнять в среде Бейсика элементарные операции и вычисления, особенно в ранних вер-
сиях типа GW-Basic или MSX-Basic, действительно нетрудно. Если компьютер включен и Бейсик
загружен, можно смело приступить к работе. Начнем с того, что вы хотите что-то вычислить. Бей-
сик для этого лучше, чем любой калькулятор. Наберите команду
PRINT "Это команда вывода", 5*5
и нажмите клавишу <Enter> (слово PRINT может заменить знак ?). Немедленно возникает
ответ: 25. Команда PRINT выводит на экран результат вычислений или сообщений, заключенных в
кавычки: PRINT "Привет!"- на экране появилось «Привет!» (без кавычек).
При вычислениях необязательно, чтобы операндом было выражение, содержащее только
числа- Попробуйте ввести следующие команды (заканчивая каждую строчку нажатием на клави-
шу <Enter>):
а=5 b=4 ?а*b
Компьютер немедленно выдаст результат: 20. , . ;
Режим работы, описанный выше, часто так и называют- режим калькулятора (или непо-
средственный режим).
А теперь каждую из представленных выше трех команд пронумеруем, см. программу 54.
Программа 54
10 а=5 20 Ь=4
30 ? a*b
Обратим внимание, что после ввода этой программы команды не выполнялись, а записыва-
лись в память компьютера. Убедиться в этом можно введя команду LIST -текст этой маленькой
программы тут же появится на экране.
Если теперь ввести команду RUN, то она запустит программу на исполнение. Таким обра-
зом, последовательный набор команд с номерами строк является программой на языке Бейсик.
Программировать на языке Бейсик означает научиться составлять определенный набор команд для
290
решения поставленной вами задачи. Какие имеются команды у Бейсика и как ими пользоваться -
рассмотрим ниже. Режим, при котором команды не выполняются непосредственно, а «копятся»,
называют косвенным. В этом режиме, основном для Бейсика, он и является языком программиро-
вания.
Следует помнить, что существует множество версий языка Бейсик и все они имеют особен-
ности. Описать здесь все версии не представляется возможным, да и нет смысла. В каждой из со-
временных версий Бейсика можно выделить общее подмножество, в котором отражены характер-
ные (стандартные) грамматика, синтаксис и семантика языка. В этой связи в последующих описа-
ниях языка рассматривается лишь выделенное авторами подмножество, справедливое для наибо-
лее популярных в настоящее время версий Бейсика: Basic-MSX, Qbasic, Turbo-Basic. Последние
версии приобрели популярность благодаря удобному интерфейсу и предоставлению пользователю
ряда сервисных возможностей, присущих современным системам программирования.
Контрольные вопросы
1. Чем принципиально различаются прямой и косвенный режимы в Бейсике?
2. Обязательно ли в Бейсике явное описание типов данных?
5.2. БАЗОВЫЕ ОПЕРАТОРЫ
Основные базовые операторы (команды) языка Бейсик определяют ввод и вывод данных,
присвоение, изменение порядка выполнения команд и циклические конструкции.
INPUT <список объектов ввода>
- ввод данных;
PRINT < список объектов вывода>
- вывод данных;
LET a= <арифметическое, логическое
или символьное выражение>
(служебное слово LET можно не писать)
- присвоение;
IF <условие> THEN <оператор1>
ELSE <оператор2>
- условный оператор;
GOTO <номер строки>
-безусловный переход;
FOR х= 1 ТО n STEP h <оператор>
NEXTx
- циклическая конструкция.
Часто используют, так называемый, внутренний ввод данных посредством операторов
READ - DATA.
Добавим к этому списку несколько системных команд, с помощью которых программист и
пользователь занимаются отладкой и обслуживанием программы:
RUN
- команда запуска программы на выполнение;
LIST
- команда вывода текста программы на экран дисплея;
SAVE
- команда сохранения текста программы в виде файла;
LOAD
- загрузка ранее сохраненной программы из существующего файла.
Этих операторов и команд обычно хватает, чтобы написать и отладить любую вычисли-
тельную программу. Ниже мы познакомимся и с другими командами Бейсика.
Как и во многих языках программирования, в Бейсике имеется набор встроенных функций:
математических, логических, символьных и др. Можно сформировать собственные функции с по-
мощью описания DEF, например
DEF FNA(x,y,z)=x*x+y*y+z*z
Рассмотрим пример программы табуляции функции с целью определения ее максимального
значения на заданном отрезке. Суть алгоритма заключается в вычислении значений функции
Sin(.x) в 100 точках, определенных на задаваемом отрезке [а,Ь] с шагом h=(b-a)/100 и в выборе
среди этих значений максимального.
Программа 55
10 REM максимум функции на отрезке