Then begin
n:=n+1;
read(buf[n]) ;
end;
untilEOLNor(n=BSIZE);
{ здесь прочитана строка и записана в массив buf }
{ преобразование строки к верхнему регистру}
fori:=1ton do
Begin
casebuf[i]of
'а'..'я':buf[i]:=chr(ord(buf[i])-32);
{ 'р'..'я':buf[i]:=chr(ord(buf[i])-80);}
End;
End;
{ вывод преобразованной строки }
writeln;
fori:=1tondo
write(buf[i] );
End.
В программе использована встроенная функция ORD, которая возвращает код (номер в таблице ASCII) символа, указанного в качестве ее аргумента.
Пример работы программы:
Преобразование строчных букв в прописные
ПРЕОБРАЗОВАНИЕ СТРОЧНЫХ БУКВ В ПРОПИСНЫЕ
Преобразование массива.
Пример 7.6.Перестановка элементов массива с номерами n и m. Алгоритм реализуется присвоением промежуточной переменной p значения элемента массива с индексомn ,элементу массива с индексомnзначения элемента массива с индексомm,а элементу массива с индексомmзначения промежуточной переменнойp. }
ProgramProg7_6;
UsesWinCrt;
Var
a:array[1..4] ofreal;
p:real;
i,n,m:integer;
Begin
read(n,m);
for i:=1 to 4 do
read(a[i]);
p:=a[n]; {перестановка}
a[n]:=a[m];
a[m]:=p;
for i:=1 to 4 do
write(a[i]);
end.
Пример 7_7. Удаление из массива элемента с номером k.
Алгоритм реализуется сдвигом всех элементов с k - номера
на одну позицию влево.
ProgramProg7_7;
usesWinCrt;
Var
a:array[1..7] ofinteger;
i,k:byte;
Begin
randomize;
write (' номер удаляемого элемента массива = ');
read(k);
writeln ('ввод массива')
fori:=1 to 7 do
Begin
a[i] := random(20);
write(a[i], ' ');
end;
writeln;
for i:=k to 7 do
Begin
a[i]:=a[i+1];
End;
fori:=1 to 6 do
Begin
write(a[i], ' ');
end;
end.
Пример 7.8. Перенос в конец массива элемента с k-ой позиции.
Алгоритм реализуется с помощью действий:
q сохранение k - элемента в дополнительной переменной p:
q сдвиг элементов следующих за k-ым на одну позицию влево.
q восстановление последнего значения из переменной p.
ProgramProgn;
usesWinCrt;
Const
n=7;
Var
a:array[1..n] ofinteger;
i,k:byte;
Begin
randomize;
write (' номер элемента = ');
read(k);
writeln ('ввод массива')
fori:=1 to n do
Begin
a[i] := random(20);
write(a[i], ' ');
end;
p:=a[k];
writeln;
for i:=k to n-1 do
Begin
a[i]:=a[i+1];
End;
a[n]:=p;
fori:=1 to n do
Begin
write(a[i], ' ');
end;
end.
Пример 7.9. Перенос в начало массива элемента с k-ой позиции.
Алгоритм реализуется с помощью следующих действий:
q Ввод элементов массива.
qСохранение k-элемента в дополнительной переменной p.
q Сдвиг всех элементов до элемента с номером k вправо.
q Записать на первое место значение из переменной р.}
ProgramProg7_9;
usesWinCrt;
Const
n=7;
Var
a:array[1..n] ofinteger;
i,k:byte;
Begin
randomize;
write (' номер элемента = ');
read(k);
writeln ('ввод массива')
fori:=1 to n do
Begin
a[i] := random(20);
write(a[i], ' ');
end;
p:=a[k];
writeln;
for i:=k downto 2 do
Begin
a[i]:=a[i-1];
End;
a[1]:=p;
fori:=1 to n do
Begin
write(a[i], ' ');
end;
End.
Пример 7.10. Вывод температуры воздуха в течение недели и вычисление
среднего значения. Для подсказок используется массив строк dey.
Var
dey:аггау[1..7] of string [11]; {названия дней недели}
temper:аггау[1..7] of геа1; {температура)
st:real;{сумма температур за неделю}
sred:геа1; (средняя температура за неделю}
i:integer;
Begin
st:=0;
dey[1]: ='Понедельник';
dey[2]: ='Вторник';
dey[3]: ='Среда';
dey[4]: ='Четверг' ;
dey[5]: ='Пятница';
dey[6]: ='Суббота' ;
dey[1]: ='Воскресенье';
Writeln ('Задайте температуру воздуха за неделю.');
for i:=1 to 7 do
Begin
writeln(dey[i]), ' ');
read(temper [1]) ;
st:=st+ temper [1;
end;
{ вычисление средней температуры за неделю }
sred:=st/7;
Wrtiteln ('Средняя температура за неделю: ', sred:6:2) ;
End.
Сортировка массива. Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием.
Например, если имеется массив целых чисел а , то после сортировки по возрастанию должно выполняться условие:
а[1] < а[2] <. ...< а[size]
где size - верхняя граница индекса массива.
Так как можно сравнивать переменные типовinteger, real, char, string, то можно сортировать массивы этих типов.
В информационных системах задача сортировки используется как предварительный этап задачи поиска, так как поиск в упорядоченном (отсортированном) массиве проводится намного быстрее, чем в
неупорядоченном.
Существует много методов (алгоритмов) сортировки массивов. Здесь мы рассмотрим два метода:
q метод прямого выбора
q метод прямого обмена
Сортировка методом прямого выбора. Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:
1. Просматривая массив от первого элемента, найти минимальный и
поместить его на место первого элемента, а первый на место минимального.
2. Просматривая массив от второго элемента, найти минимальный
поместить его на место второго элемента, а второй на место минимального.
3. И так далее до предпоследнего элемента.
Ниже представлена программа сортировки массива целых чисел по возрастанию. Для демонстрации процесса сортировки программа выводит массив после каждого обмена элементов.
ProgramProg7_3;
usesWinCrt;
const;
size=5;
Var
а:аrrау[1..size] of integer;
i:integer; { номер элемента, от которого ведется поиск }
{ минимального эл-та }
min, nc:integer; {значение минимального элемента и его номер }
j:integer; { номер эл-та, сравниваемого с минимальным }
buf: integer; { буфер, используемый при обмене эл-тов массива }
k:integer;
Begin
writeln ('Сортировка массива.');
write('Введите',size:3,'целых числа через пробел и нажмите<Enter>');
for k:=1 to size do read(a[k]);
writeln('Сортировка');
for i:=1 to size-1 do
Begin
{ поиск минимального элемента массива от а[1] до а[size]}
min:=a[i];
for j:=i+1 to size do
Begin
if a[i]>a[j] then
Begin
min:=a[j];nc:=j;
{поменяем местами а[min] и а[i]}
buf:=a[i];
а[i]:=а[j];
а[j]:=buf;
End;
End;
{ вывод массив}
fork:=1 to size do write(a[k]), ' ');
writeln;
end;
writeln ('Массив отсортирован.');
end.
Пример работы программы:
Сортировка массива.
Введите 5 целых в одной строке через пробел и нажмите <Еnter>
12 -3 56 47 10
Сортировка
-3 12 56 47 10
-3 10 56 47 12
-3 10 12 47 56
-3 10 12 47 56
Массив отсортирован.
Сортировка методом прямого обмена. В основе алгоритма - обмен значениями соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением сдвигаются к началу массива (всплывают), а элементы с большим значением - к концу массива (тонут), поэтому этот метод иногда называют "пузырьковым". Этот процесс повторяется на единицу меньше раз, чем элементов в массиве.
На рис. 7.1. показан пример процесса сортировки массива. Буквой ("а") обозначено исходное состояние массива и перестановки на первом проходе, буквой ("б") - состояние после перестановок на первом проходе и перестановки на втором проходе и так далее. Ниже представлена программа сортировки массива целых чисел по возрастанию. Программа выводит массив после каждого цикла обмена.
i=1 | 3 | |||||||||
i=2 | ||||||||||
i=3 | 4 | |||||||||
i=4 | ||||||||||
i=5 |
а б в г д
Пример 7.4. Программа сортировки массива целых чисел по возрастанию с
помощью метода прямого обмена.
Program Prog7_4;
uses wincrt;
Const
size=5;
Var
a:array[1..size] of integer;
i:integer; { счетчик циклов }
buf: integer; { буфер для обмена эл-тов массива }
k:integer; {текущий индекс элемента массива}
Begin
writeln ('Сортировка массива пузырьковым методом');
write('Введите',size:3,' целых числа через пробел и нажмите enter');
for k:=1 to size doread(a[k]);
writeln('Сортировка');
for i:=1 to size-1 do
Begin
for k:=1 to size-1 do
Begin
if a[k]>a[k+1] then begin
{меняем местами а[k] и а[k+1]}
buf:=a[k];
a[k]:=a[k+1];
a[k+1]:=buf;
End;
End;
{ выведем массив}
for k:=1 to size do write(a[k],' ');
writeln;
End;
writeln ('Массив отсортирован.');
End.
Пример работы программы:
Сортировка массива пузырьковым методом.
Введите 5 целых в одной строке через пробел и нажмите <Еnter>
3 2 4 5 1
Сортировка.
2 3 4 1 5 '
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5
Массив отсортирован.
Поиск в массиве. При решении многих задач возникает необходимость установить, содержит ли массив определенную информацию или нет. Задачи такого типа называются поиском в массиве. Поиск осуществляется сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы.
Поиск минимального (максимального) элемента массива.Алгоритм поиска минимального (максимального) элемента массива очевиден: делается предположение, что первый элемент массива является минимальным (максимальным), затем остальные элементы массива сравниваются с этим элементом. Если обнаруживается, что проверяемый элемент меньше (больше) принятого за минимальный (максимальный), то этот элемент
принимается за минимальный (максимальный) и продолжается проверка оставшихся элементов.
Пример 7.5. Программа поиска минимального элемента в массиве целых
чисел.
ProgramProg7_5;
uses WinCrt;
Const
n=10;
Vаг
a:array[1. .n] of integer; { массив целых }
min:integer; { номер минимального эл-та массива }
i:integer; { номер эл-та сравниваемого с минимальным }
Begin
{ ввод массива }
min:=a[1];{ пусть первый элемент минимальный }
for i:=2 to n do
If a[i] <min then min:=a[i]; nc:=i;
writeln ('Минимальный элемент массива:', min );
wtiteln('Номер элемента:',nc);
End.
Поиск с помощью алгоритма простого перебора. Алгоритм простого перебора применяется, если элементы массива не упорядочены. Ниже приведен текст программы поиска в массиве целых чисел.
Пример 7.6. Программа поиска методом простого перебора.
Перебор элементов массива осуществляет инструкция REPEAT, в теле которой инструкция IF сравнивает текущий элемент массива с образцом и присваивает переменной poisk значение True, если текущий элемент равен образцу. Цикл завершается, если в массиве обнаружен элемент, равный образцу (poisk=True), или если проверены все элементы массива. По завершении цикла, по значению переменной found можно определить, успешен поиск или нет.
ProgramProg7_6;
Var
mas:аггау[1. . 10] of integer; { массив целых}
obr: integer; { образец для поиска }
naiden:boolean; { признак совпадения с образцом )
i: integer;
Begin
(ввод 10 целых чисел}
Write ('Введите 10 целых чисел в одной строке через пробел ');
Writeln ('и нажмите <Еnter>');
For i:=1 to 10 do read (mas[i]); { числа введены в массив }
Write ('Введите образец для поиска (целое число)-> ');
Read(obr) ;
( поиск простым перебором }
naiden:=false;; ( совпадений нет }
i:=1; { проверяем с первого элемента массива }
Гереаt
if mas[i] =obr then naiden:= true { совпадение с образцом }
else i:=i+1;{ переход к следующему элементу }
Until (i>10) or naiden; {завершим, если совпадение с образцом или}
{проверен последний элемент массива }
If naiden then write ('Поиск успешен. Элемент ', i, ' найден');
elsewrite('Совпадений с образцом нет.');
End.
Пример работы программы:
Поиск в массиве.
Введите 10 целых в одной строке через пробел и нажмите <Enterг>
->123 45 -17 23 56 2 -8 0 14 324
Введите образец для поиска (целое число)->2
Совпадение с элементом номер 6. Поиск успешен.
Данный алгоритм может использоваться для поиска как в числовых, так и в строковых массивах.
На практике довольно часто проводится поиск в массиве, элементы которого упорядочены по некоторому критерию. Например, массив фамилий упорядоченный по алфавиту, массив данных о погоде упорядоченный по датам наблюдений.
Для поиска в упорядоченных массивах применяют другие, более эффективные по сравнению с методом простого перебора, алгоритмы, один из которых - метод бинарного поиска.
Суть метода бинарного поиска заключается в следующем. Выбирается средний элемент упорядоченного по возрастанию массива (элемент с номером sred), с которым сравнивается образец (рис. 7.2.).
-5 | -5 | |||||||||
| -1 | -1 | ||||||||
verh | 0 | |||||||||
sred | sred | |||||||||
13 | ||||||||||
| niz | |||||||||
Рис . Выбор среднего элемента массива при бинарном поиске
Если средний элемент равен образцу, то задача считается решенной.
Если средний элемент меньше образца, то искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred).
Если средний элемент больше образца, то искомый элемент расположен :
ниже среднего (между элементами с номерами sred и niz.
После того как определена часть массива, в которой может располагать искомый элемент, поиск проводят в этой части, выделяя новый средний элемент. Номер среднего элемента вычисляется по формуле (niz-verh)/2+verh.
Ниже(рис ) представлены алгоритм и текст программы бинарного поиска в массиве. В программу добавлены операторы вывода значений переменных verh, niz и sred. Выводимая информация полезна для понимания сути алгоритма. Кроме того, переменная n позволяет оценить эффективность этого алгоритма по сравнению с поиском методом простого перебора (для массивов, упорядоченных по возрастанию).
Дата добавления: 2015-01-13; просмотров: 874;