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
verh

  -1       -1
      verh   0
sred         sred  
          13
niz

    niz  
         
         
         
                 
                     

Рис . Выбор среднего элемента массива при бинарном поиске

 

Если средний элемент равен образцу, то задача считается решенной.

Если средний элемент меньше образца, то искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred).

Если средний элемент больше образца, то искомый элемент расположен :

ниже среднего (между элементами с номерами sred и niz.

После того как определена часть массива, в которой может располагать ис­комый элемент, поиск проводят в этой части, выделяя новый средний эле­мент. Номер среднего элемента вычисляется по формуле (niz-verh)/2+verh.

Ниже(рис ) представлены алгоритм и текст программы бинарного поиска в массиве. В про­грамму добавлены операторы вывода значений переменных verh, niz и sred. Выводимая информация полезна для понимания сути алгоритма. Кроме того, переменная n позволяет оценить эффективность этого алгоритма по сравнению с поиском методом простого перебора (для массивов, упорядо­ченных по возрастанию).








Дата добавления: 2015-01-13; просмотров: 886;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.085 сек.