Метод сортировки в программировании
Обработать массивы таким образом, чтобы группы, состоящие из трех или более подряд стоящих нулей, были переписаны в начало массива. В рамки соответствующего цветного контура поочерёдно вписываются значения соответствующих ячеек массивов по столбцам. Если в массиве обнаружится группа, состоящая из трех или более подряд стоящих нулей, то переписать ее в начало массива. Матрица должна иметь… Читать ещё >
Метод сортировки в программировании (реферат, курсовая, диплом, контрольная)
1. Постановка задачи
сортировка пузырек массив матрица
1.1 Список контуров
· 1,1−1,3−2,4−5,4−4, 3−4,1−1,1
· 3,5−4,6−4,9−7,9−7,6−6,5−3,5
· 7,3−4,6−7,9−7,3
сортировка пузырьковый массив листинг
1.2 Описание метода сортировки
Метод парных перестановок будет работать гораздо эффективнее, если при перестановке пары элементов мы поднимаемся по массиву вверх, найдя место для переставляемого элемента. Это и будет пузырек, который сразу же «всплывет» на соответствующий его весу уровень.
В последовательности AI, А2, …, AN сравниваются поочерёдно два соседних элемента АК и AK+I, где 1<= К <= N — I; если АК<�АК +1, осуществляется перестановка соседних сравниваемых элементов и делается проверка для всех элементов от К-го до 1-го, т. е. движение влево по последовательности с перестановкой соответствующих элементов.
1.3 Условие дополнительного задания
Массив упорядочен.
Если в массиве обнаружится группа, состоящая из трех или более подряд стоящих нулей, то переписать ее в начало массива.
Исходная матрица:
Курсовой проект
2. Разработка проекта
2.1 Обработка массивов
Обработать массивы таким образом, чтобы группы, состоящие из трех или более подряд стоящих нулей, были переписаны в начало массива.
Для обработки в программе написана процедура { procedure obrabotka (str:string;dl:integer;var mas: masr);}, которая включает в себя вложенную процедуру {procedure vivod (mas:masr;dl:byte;str:string);} вывода на монитор результата обработки.
Рис.1
Курсовой проект
Фрагмент исходного текста
procedure obrabotka (str:string;dl:integer;var mas: masr);
var i, l, k, i_end:integer;
begin
k:=0;
for i:=1 to dl do
begin
while mas[i]=0 do
begin
k:=k+1;
if i
i:=i+1
else break;
end;
if k>=3 then
begin
if i=dl then i_end:=dl
else
i_end:=i-1;
for j:=1 to k do
for l:=i_end downto 1 do
mas[l]: =mas[l-1];
mas[1]:=0;
end;
k:=0;
end;
vivod (mas, dl, str);
end;
Комментарии к выше указанному фрагменту текста
while mas[i]=0 do — цикл с предусловием
begin
k:=k+1;
if i
i:=i+1
else break;
end;
if k>=3 then
begin
if i=dl then i_end:=dl
else
i_end:=i-1;
for j:=1 to k do
for l:=i_end downto 1 do
mas[l]: =mas[l-1];
mas[1]:=0;
end;
k:=0; стр. 5 из 15
Курсовой проект
2.2 Сортировка полученных массивов методом всплывающего пузырька
Сортировка — это процесс упорядочивания набора данных одного типа по возрастанию или убыванию значения какого-либо признака. При сортировки элементы массива меняются местами таким образом, что их значения оказываются упорядоченными или по возрастанию или по убыванию. Если в массиве есть одинаковые элементы, то говорят о сортировке по неубыванию или по невозрастанию.
Один из самых популярных методов сортировки — «пузырьковый» основан на том, что в процессе исполнения алгоритма более «легкие» элементы массива постепенно «всплывают». Особенностью данного метода является сравнение, а затем, если нужно, и перестановка соседних элементов Метод нашел свое название в результате следующей аналогии. Если элементы в вертикально расположенном массиве представить себе пузырьками в резервуаре с водой, обладающими весом, равным значению элемента, то каждый просмотр массива и перестановки элемента будут рассматриваться как «всплывание» пузырька на соответствующий его весу уровень Для сортировки в программе написана процедура {procedure sortirovka (str:string;l:integer;mas:mas;var mas_r.mas); } в которой идет сортировка заданным методом. Процедура включает в себя вложенную процедуру {procedure vivod (str:string;l:integer;mas:mas);} вывода на монитор результата сортировки.
Рис
Фрагмент исходного текста программы
procedure sortirovka (str:string;l:integer;mas:mas;var mas_r:mas);
begin
for i:=2 to L do
for j:=L downto i do
begin
if mas[j-l]>mas[j] then
begin
temp:=mas[j-l];
mas[j-l]:=mas[j];
mas[j]:=temp;
еnd;
end;
vivod (str, L, mas);
for i:=l to 1 do
mas_r[i]: =mas[i];
end;
Комментарии к выше указанному фрагменту текста for i:=2 to L2 do — цикл обработки значений ячеек массива 2 начиная с ячейки 2. L2 — показывает количество ячеек, for j:=L2 downto i do — цикл обработки значений ячеек массива 2 начиная с последней и заканчивая текущим значением i. if mas2[j-l]>mas2[j] - условие которое сравнивает две ячейки — текущую и предыдущую ячеки. И в случае выполнение условия происходит замена их местами begin — начала процесса замены ячеек в зависимости от выбранного направления сортировки temp:=mas2[j-l] - занесение во вспомогательную переменную значение предыдущей ячейки. mas2[j-l]: =mas2[j] -mas2[j]: =temp; end;
2.3 Вывод на дисплей монитора обновленной матрицы
Матрица должна иметь следующий вид: все контура полученные после сортировки включаются в матрицу по столбцам.
Рис.2
Фрагмент исходного текста
p:=1;
r:=1;
k:=1;
l:=1;
for j:=1 to n do
begin
for i:=1 to m do
begin
{napolnyaem kontur 1}
if
((i>=1) and (i<=4) and (j>=1) and (j<=3))
or
((i>=2) and (i<=5) and (j=4))
then
begin
mas[i, j]: =mas1[p];
p:=p+1;
end
{napolnyaem kontur 3}
else if
((i>=4) and (i<=7))
and
(
{levyi treugolnik}
((j>=3) and (j<=6) and (j>=10-i))
or
{pravyi treugolnik}
((j>=6) and (j<=9) and (j<=i+2))
)
then
begin
mas[i, j]: =mas3[k];
k:=k+1;
if
((i>=3) and (i<=6) and (j=5))
or
((i>=4) and (i<=7) and (j>=6) and (j<=9))
then
begin
udalit_element (mas2, dl2, r);
end
end
{napolnyaem kontur 2}
else if стр. 9 из 15
((i>=3) and (i<=6) and (j=5)) Курсовой проект
or
((i>=4) and (i<=7) and (j>=6) and (j<=9))
then
begin
mas[i, j]: =mas2[r];
r:=r+1;
end
else
begin
mas[i, j]:=mas4[l];
l:=l+1;
end;
end;
end;
writeln;
writeln ('Обновлённый массив:');
otrisovka_matricy (mas, n, m);
readln;
end.
Комментарии к выше указанному фрагменту текста
В рамки соответствующего цветного контура поочерёдно вписываются значения соответствующих ячеек массивов по столбцам.
3. Листинг программного кода задачи
program kurs;
uses crt;
const n=7;
m=9;
dl=75;
color1 = 4;
color2 = 5;
color3 = 10;
color23 = 3;
bgcolor = 15;
type
mas0=array [1.n, 1. m] of integer;
masr=array[1.dl] of integer;
var
i, j, t, k, l, p, r, code, dl1, dl2,dl3,dl4,tmp: integer;
d: text;
mas:mas0;
mas1,mas2,mas3,mas4:masr;
s, w, str:string;
procedure vivod (mas:masr;dl:byte;str:string);
var
i:integer;
begin
writeln (str);
for i:=1 to dl do
write (mas[i]: 4);
writeln;
end;
procedure obrabotka (str:string;dl:integer;var mas: masr);
var
i, l, k, i_end:integer;
begin
k:=0;
for i:=1 to dl do
begin
while mas[i]=0 do
begin
k:=k+1;
if i
i:=i+1
else break;
end;
if k>=3 then
begin
if i=dl then i_end:=dl
else
i_end:=i-1;
for j:=1 to k do
for l:=i_end downto 1 do
mas[l]: =mas[l-1];
mas[1]:=0;
end;
k:=0;
end;
vivod (mas, dl, str);
end;
procedure sortirovka (str:string;dl:integer;var mas: masr);
var
k, i: byte;
temp:integer;
begin
for i:=2 to dl do
for j:=dl downto i do
if mas[j-1]
begin
temp:=mas[j-1];
mas[j-1]:=mas[j];
mas[j]:=temp;
k:=k+1;
end;
vivod (mas, dl, str);
end;
procedure otrisovka_matricy (var mas: mas0; kol_strok:integer; kol_stolbcov:integer);
var
i, j: integer;
begin
for i:=1 to kol_strok do
begin
for j:=1 to kol_stolbcov do
begin
{risuem kontur 1}
if
((i>=1) and (i<=4) and (j>=1) and (j<=3))
or
((i>=2) and (i<=5) and (j=4))
then
textcolor (color1)
{risuem peresechenie konturov 2 i 3}
else if
(
((i>=3) and (i<=6) and (j=5))
or
((i>=4) and (i<=7) and (j>=6) and (j<=9))
)
and
(
((i>=4) and (i<=7))
and
(
{risuem levyi treugolnik}
((j>=3) and (j<=6) and (j>=10-i))
or
{risuem pravyi treugolnik}
((j>=6) and (j<=9) and (j<=i+2))
)
)
then
textcolor (color23)
{risuem kontur 2}
else if
((i>=3) and (i<=6) and (j=5))
or
((i>=4) and (i<=7) and (j>=6) and (j<=9))
then
textcolor (color2)
{risuem kontur 3}
else if
((i>=4) and (i<=7))
and
(
{risuem levyi treugolnik}
((j>=3) and (j<=6) and (j>=10-i))
or
{risuem pravyi treugolnik}
((j>=6) and (j<=9) and (j<=i+2))
)
then
textcolor (color3)
{risuem ostalnye elementy}
else
textcolor (bgcolor);
write (mas[i, j]: 4);
end;
writeln;
end;
end;
procedure udalit_element (var mas: masr; razmer_matricy: integer; nomer_elementa: integer);
var
i: integer;
begin
for i:=nomer_elementa to razmer_matricy do
begin
mas[i] := mas[i+1];
end;
end;
begin
clrscr;
assign (d, 'matr1.dat');
reset (d);
j:=1;
i:=1;
repeat
readln (d, s);
s:=s+' ';
w:='';
for k:=1 to length (s) do
begin
if s[k]<>' ' then w:=w+s[k] else
begin
val (w, t, code);
w:='';
mas[i, j]: =t;
j:=j+1;
end;
end;
until eof (d);
close (d);
otrisovka_matricy (mas, n, m);
dl1:=0;
dl2:=0;
dl3:=0;
dl4:=0;
for i:=1 to n do
begin
for j:=1 to m do
begin
{napolnyaem kontur 1}
if
((i>=1) and (i<=4) and (j>=1) and (j<=3))
or
((i>=2) and (i<=5) and (j=4))
then
begin
dl1:=dl1+1;
mas1[dl1]: =mas[i, j];
end
{napolnyaem peresechenie konturov 2 i 3}
else if
(
((i>=3) and (i<=6) and (j=5))
or
((i>=4) and (i<=7) and (j>=6) and (j<=9))
)
and
(
((i>=4) and (i<=7))
and
(
{levyi treugolnik}
((j>=3) and (j<=6) and (j>=10-i))
or
{pravyi treugolnik}
((j>=6) and (j<=9) and (j<=i+2))
)
)
then
begin
{napolnyaem matricu 2}
dl2:=dl2+1;
mas2[dl2]: =mas[i, j];
{napolnyaem matricu 3}
dl3:=dl3+1;
mas3[dl3]: =mas[i, j];
end
{napolnyaem kontur 2}
else if
((i>=3) and (i<=6) and (j=5))
or
((i>=4) and (i<=7) and (j>=6) and (j<=9))
then
begin
dl2:=dl2+1;
mas2[dl2]: =mas[i, j];
end
{napolnyaem kontur 3}
else if
((i>=4) and (i<=7))
and
(
{levyi treugolnik}
((j>=3) and (j<=6) and (j>=10-i))
or
{pravyi treugolnik}
((j>=6) and (j<=9) and (j<=i+2))
)
then
begin
dl3:=dl3+1;
mas3[dl3]: =mas[i, j];
end
else
begin
dl4:=dl4+1;
mas4[dl4]:=mas[i, j];
end;
end;
end;
textcolor (color1);
vivod (mas1,dl1,' Массив 1');
textcolor (color2);
vivod (mas2,dl2,' массив 2');
textcolor (color3);
vivod (mas3,dl3,' массив 3');
textcolor (bgcolor);
vivod (mas4,dl4,' массив 4');
writeln;
readln;
textcolor (color1);
obrabotka ('Обработанный массив 1:', dl1, mas1);
textcolor (color2);
obrabotka (''Обработанный массив 2:', dl2, mas2);
textcolor (color3);
obrabotka (''Обработанный массив 3:', dl3, mas3);
textcolor (bgcolor);
obrabotka (''Обработанный массив 4:', dl4, mas4);
writeln;
readln;
textcolor (color1);
sortirovka ('Отсортированный массив 1:', dl1, mas1);
textcolor (color2);
sortirovka (''Отсортированный массив 2:', dl2, mas2);
textcolor (color3);
sortirovka (''Отсортированный массив 3:', dl3, mas3);
textcolor (bgcolor);
sortirovka (''Отсортированный массив 4:', dl4, mas4);
writeln;
readln;
p:=1;
r:=1;
k:=1;
l:=1;
for i:=1 to n do
begin
for j:=1 to m do
begin
{napolnyaem kontur 1}
if
((i>=1) and (i<=4) and (j>=1) and (j<=3))
or
((i>=2) and (i<=5) and (j=4))
then
begin
mas[i, j]: =mas1[p];
p:=p+1;
end
{napolnyaem kontur 3}
else if
((i>=4) and (i<=7))
and
(
{levyi treugolnik}
((j>=3) and (j<=6) and (j>=10-i))
or
{pravyi treugolnik}
((j>=6) and (j<=9) and (j<=i+2))
)
then
begin
mas[i, j]: =mas3[k];
k:=k+1;
{peresechenie konturov 2 i 3}
{udalyaem nenuzhnye elementy is kontura 2}
if
((i>=3) and (i<=6) and (j=5))
or
((i>=4) and (i<=7) and (j>=6) and (j<=9))
then
begin
udalit_element (mas2, dl2, r);
end
end
{napolnyaem kontur 2}
else if
((i>=3) and (i<=6) and (j=5))
or
((i>=4) and (i<=7) and (j>=6) and (j<=9))
then
begin
mas[i, j]: =mas2[r];
r:=r+1;
end
else
begin
mas[i, j]:=mas4[l];
l:=l+1;
end;
end;
end;
writeln;
writeln ('Обновлённый массив:');
otrisovka_matricy (mas, n, m);
readln;
end
.ru