Билет № 18. Написать и отладить программу обработки массива (суммирование элементов, сортировка и пр.)

Pascal

QBasic

Написать и отладить программу обработки массива (суммирование элементов, сортировка и пр.). Проанализировать полученный результат.

Пример. Написать и отладить программу ввода и сортировки по возрастанию (неубыванию) целочисленного массива из 20 элементов.

Решение. Решим задачу в общем случае, т.е. отсортируем массив из n элементов. В качестве метода сортировки используем сортировку обменом (“пузырьковую” сортировку).

Напомним алгоритм сортировки. Массив просматривается от начала до конца столько раз, сколько в нем содержится элементов. При каждом просмотре поочередно сравниваются два соседних элемента. Если элемент с большим номером имеет меньшее значение, производится обмен элементов.

Запишем этот алгоритм на языках программирования (массив при этом заполняется случайным образом; если после запуска программы введем n = 20, то получим массив, удовлетворяющий условию исходной задачи).

DECLARE SUB Vvod (n!, A() AS INTEGER)

DECLARE SUB Vivod (n!, A() AS INTEGER)

DECLARE SUB Sort (n!, A() AS INTEGER)

DIM A(20) AS INTEGER

RANDOMIZE TIMER — 32767

PRINT "N? ": INPUT n

CALL Vvod(n, A())

CALL Vivod(n, A())

CALL Sort(n, A())

CALL Vivod(n, A())

SUB Sort (n, A() AS INTEGER)

FOR i = 1 TO n

FOR j = 1 TO n — 1

IF A(j) > A(j + 1) THEN

Vsp = A(j)

A(j) = A(j + 1)

A(j + 1) = Vsp

END IF

NEXT j

NEXT i

END SUB

SUB Vivod (n, A() AS INTEGER)

FOR i = 1 TO n

PRINT USING "####"; A(i);

NEXT i

PRINT

END SUB

SUB Vvod (n, A() AS INTEGER)

FOR i = 1 TO n

A(i) = -20 + INT(RND(1) * 41)

NEXT i

END SUB

Program Obmen;

Type arr = array[1..20] of integer;

Procedure Vvod(n: byte; var a: arr);

Var i: byte;

Begin

For i:= 1 to n do

A[i]:= -20 + random(41)

End;

Procedure Vivod(n: byte; const a: arr);

Var i: byte;

Begin

For i:= 1 to n do

Write(a[i]:4);

Writeln

End;

Procedure Sort(n: byte; var a: arr);

Var i, j: byte; Vsp: integer;

Begin

FOR i:= 1 TO n do

FOR j:= 1 TO n — 1 do

IF A[j] > A[j + 1] THEN

begin Vsp:= A[j];

A[j]:= A[j + 1];

A[j + 1]:= Vsp

end

End;

Var a: arr; n: byte;

Begin

Randomize;

Write('n? '); readln(n);

Vvod(n, a);

Vivod(n, a);

Sort (n, a);

Vivod(n, a)

End.

C++

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

void Vvod(int n, int a[21]);

void Vivod(int n, int a[21]);

void Sort(int n, int a[21]);

void main()

{int n, a[21];

cout << "Сколько элементов в массиве? "; cin >> n;

randomize();

Vvod(n, a);

Vivod(n, a);

Sort(n, a);

Vivod(n, a);

}

void Vvod(int n, int a[21])

{ int i;

for (i = 1; i <= n; i++)

a[i] = -20 + random(41);

}

void Vivod(int n, int a[21])

{ int i;

for (i = 1; i <= n; i++)

{ cout.width(4); cout << a[i];}

cout<<endl;

}

void Sort(int n, int a[21])

{ int i, j, Vsp;

for (i = 1; i <= n; i++)

for (j = 1; j <= n-1; j++)

if (a[j] > a[j+1])

{Vsp = a[j]; a[j] = a[j+1];

a[j+1] = Vsp;}

}

Варианты заданий

1. Сортировка выбором. Дана последовательность чисел a 1, a 2,..., an. Требуется переставить элементы так, чтобы они были расположены по убыванию. Для этого в массиве, начиная с первого, выбирается наибольший элемент и ставится на первое место, а первый — на место наибольшего. Затем, начиная со второго, эта процедура повторяется. Написать алгоритм сортировки выбором.

2. Сортировка вставками. Дана последовательность чисел a ₁, a ₂,..., a _n. Требуется переставить числа в порядке возрастания. Делается это следующим образом. Пусть a ₁, a ₂,..., a _i — упорядоченная последовательность, т.е. a ₁ a ₂ ... a _i. Берется следующее число a _i+1 и вставляется в последовательность так, чтобы новая последовательность была также возрастающей. Процесс производится до тех пор, пока все элементы от i + 1 до n не будут перебраны.

3. Дан массив n действительных чисел. Требуется упорядочить его по возрастанию. Делается это следующим образом: сравниваются два соседних элемента a _iи a _i+1. Если a _i a _i+1, то продвигаются на один элемент вперед. Если a _i > a _i+1, то производится перестановка и сдвигаются на один элемент назад. Составить алгоритм этой сортировки.

4. Сортировка подсчетом. Выходной массив заполняется значениями “–1”. Затем для каждого элемента определяется его место в выходном массиве путем подсчета количества элементов строго меньших данного. Естественно, что все одинаковые элементы попадают на одну позицию, за которой следует ряд значений “–1”. После чего оставшиеся в выходном массиве позиции со значением “–1” заполняются копией предыдущего значения.

5. Сортировка “хитрая”. Из массива путем однократного просмотра выбирается последовательность элементов, находящихся в порядке возрастания, переносятся в выходной массив и заменяются во входном на “–1”. Затем оставшиеся элементы включаются в полученную упорядоченную последовательность методом погружения, когда очередной элемент путем ряда обменов “погружается” до требуемой позиции в уже упорядоченную часть массива.

Дата добавления: 2015-04-23