Постановка задачи
Получить упорядоченный по убыванию массив C[n] путем слияния упорядоченных по убыванию массивов A[20] и B[n-20]. Массив C формировать непосредственно из массивов A и B без последующей сортировки массива C.
Примечания:
– n целое число больше 20 и меньше 100;
– Все элементы массивов целые числа;
– Массивы вводятся и выводятся, поэлементно, через пробел;
– Если количество введенных чисел превышает длину массива, то в массив записываются первые k чисел, где k – длина массива.
Текстовый алгоритм решения задачи
Таблица 1 – Алгоритм решения
Номер шага | Назначение шага |
1. | Ввод: n, A[0..19], B[0..(n-21)] |
2. | i:=0 |
3. | j:=0 |
4. | k:=0 |
5. | Начало цикла А. Проверка выполнения условия ((j < 20) and (k < n-20)). Если условие истинно, то идти к шагу 6, иначе – к шагу 13 |
6. | Проверка выполнения условия: (A[j] >= B[k]). Если условие истинно, то идти к шагу 7, иначе – к шагу 9 |
7. | C[i]:=A[j] |
8. | j:=j+1. Идти к шагу 11 |
9. | C[i]:=B[k] |
10. | k:=k+1 |
11. | i:=i+1 |
12. | Конец цикла А. Идти к шагу 5 |
13. | Проверка выполнения условия: (j < 20). Если условие истинно, то идти к шагу 14, иначе – к шагу 19 |
14. | Начало цикла B1. Проверка выполнения условия (j < 20). Если условие истинно, то идти к шагу 15, иначе – к шагу 24 |
15. | C[i]:=A[j] |
16. | i:=i+1 |
17. | j:=j+1 |
18. | Конец цикла B1. Идти к шагу 14 |
19. | Начало цикла B2. Проверка выполнения условия (k < n-20). Если условие истинно, то идти к шагу 20, иначе – к шагу 24 |
20. | C[i]:=B[k] |
21. | i:=i+1 |
22. | k:=k+1 |
23. | Конец цикла B2. Идти к шагу 19 |
24. | Вывод: C[0..(n-1)] |
25. | Останов |
Структура данных
Таблица 2 – Данные
Элементы данных | Рекомендуемый тип | Назначение |
Dlina[1] | Integer | Максимальная длина итогового массива |
A | array [0..19] of integer | Хранение исходного массива А[20] |
B | array [0..(Dlina-21)] of integer | Хранение исходного массива B[n-20] |
C | array[0..(Dlina-1)] of integer | Хранение итогового массива С[n] |
i, k | 0..Dlina | Счетчик цикла |
j | 0..20 | Счетчик цикла |
Oshibka | Boolean | Логическая переменная, обозначающая наличие ошибки во входных данных |
Схема алгоритма решения задачи по ГОСТ 19.701-90
Рисунок 1– Графическая схема алгоритма(часть 1)
Рисунок 2– Графическая схема алгоритма (часть 2)
Приложение А
(обязательное)
Исходный код программы
Program Вариант_50_1;
{ Краткое условие.
Даны отсортированные в порядке убывания
массивы A[20] и B[n-20].
Необходимо получить упорядоченный по убыванию
массив C[n] путем слияния массивов A и B,
без дальнейшей сортировки массива C.
Массивы A и B вводятся с клавиатуры.}
{$APPTYPE CONSOLE} // консольная программа
uses
{ Объявление библиотек }
SysUtils, // системная библиотека
windows; // библиотека для работы с консолью
Const
{ Объявление констант }
Dlina = 100; // максимальная длина итогового массива
Var
{ Объявление переменных }
A: array [0..19] of integer;
B: array[0..(Dlina-21)] of integer;
C: array[0..(Dlina-1)] of integer;
n: integer;
j: 0..20;
i,k: 0..Dlina;
Oshibka: boolean;
Begin
Try
{ Настройка параметров консоли }
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
{ Инициализация переменных }
Oshibka:= false;
{ Ввод данных }
{ Ввод длины итогового массива}
write('Введите количество элементов итогового
массива(20<n<=',Dlina,'):');
readln(n);
{ Проверка корректности введенной длины }
if (n <= 20) or (n > Dlina) then
Oshibka:=true
else
begin
{ Поэлементный ввод массива А }
writeln('Введите массив A(поэлементно,
через пробел):');
read(A[0]);
i:=0;
repeat
Inc(i);
read(A[i]);
until (i >= 19) or (A[i] > A[i-1]);
readln;
{ Проверка отсортированности массива A}
if A[i] > A[i-1] then
Oshibka:=true
else
begin
{ Поэлементный ввод массива В }
writeln('Введите массив B(поэлементно,
через пробел):');
read(B[0]);
i:=0;
repeat
Inc(i);
read(B[i]);
until (i >= n-21) or (B[i] > B[i-1]);
readln;
{ Проверка отсортированности массива B}
if B[i] > B[i-1] then
Oshibka:=true
else
begin
{ Получение массива C слиянием массивов A и B }
i:=0;
j:=0;
k:=0;
{ Заполняем массив С пока не дойдем до границы
массива А или массива В (цикл A)}
while (j < 20) and (k < n-20) do
begin
{ Выбор i-того элемента массива C }
if A[j] >= B[k] then
begin
C[i]:= A[j];
Inc(j);
end
else
begin
C[i]:= B[k];
Inc(k);
end;
Inc(i);
end;
{ Получение оставшихся(n-i) элементов
массива C (цикл B1 или B2)}
if j < 20 then
while j < 20 do
begin
C[i]:= A[j];
Inc(i);
Inc(j);
end
else
while k < n-20 do
begin
C[i]:= B[k];
Inc(i);
Inc(k);
end;
{ Вывод ответа }
{ Поэлементный вывод массива C }
writeln('Полученный массив C:');
for i:= 0 to n-1 do
write(C[i],' ');
end;
end;
end;
{ Главная проверка корректности данных }
Except
on E: Exception do
Oshibka:=true
end;
{ Проверка на наличие ошибок во входных данных}
if Oshibka then
begin
writeln('Некорректные данные.');
end;
readln;
End.
Приложение Б
(обязательное)
Тестовые наборы
Группа тестов 1
Тестовые ситуации: Наличие ответа
Тест 1.1
Тестовая ситуация: Работа с граничными значениями
Исходные данные:
Количество элементов итогового массива n:42
Исходный массив А:
2147483647 2000000000 437 49 47 45 43 42 41 40 10 0 -13 -15
-18 -19 -20 -2000000 -300000000 -2147483648
Исходный массив B:
48 46 44 41 40 39 10 10 0 0 -12 -14 -16 -17 -19 -21 -123456
-2000000 -300000001 -2147483628 -2147483638 -2147483647
Ожидаемый результат:
Полученный массив С:
2147483647 2000000000 437 49 48 47 46 45 44 43 42 41 41 40
40 39 10 10 10 0 0 0 -12 -13 -14 -15 -16 -17 -18 -19 -19 -20
-21 -123456 -2000000 -2000000 -300000000 -300000001
-2147483628 -2147483638 -2147483647 -2147483648
Полученный результат:
Рисунок 3—Тест 1.1
Тест 1.2
Тестовая ситуация: Количество вводимых чисел больше длины массива
Исходные данные:
Количество элементов итогового массива n:22
Исходный массив А:
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2
Исходный массив B:
-3 -4
Ожидаемый результат:
Полученный массив С:
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 -3 -4
Полученный результат:
Рисунок 4—Тест 1.2
Группа тестов 2
Тестовые ситуации: Некорректные данные
Тест 2.1
Тестовая ситуация: Некорректное значение длины массива
Исходные данные: n=20
Ожидаемый результат: Некорректные данные.
Полученный результат:
Рисунок 5—Тест 2.1
Тест 2.2
Тестовая ситуация: Массивы не отсортированы в порядке убывания
Исходные данные:
Количество элементов итогового массива n:25
Исходный массив А:
11 10 9 8 7 6 5 4 3 2 1 0 -11 -10 -9 -8 -7 -6 -5 -4
Ожидаемый результат:
Некорректные данные.
Полученный результат:
Рисунок 6—Тест 2.2
Тест 2.3
Тестовая ситуация: Один из элементов массива дробный
Исходные данные:
Количество элементов итогового массива n:25
Исходный массив А:
24 23 22 21 20 19 18.5 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Ожидаемый результат:
Некорректные данные.
Полученный результат:
Рисунок 7—Тест 2.3
Тест 2.4
Тестовая ситуация: Выход за границу типа
Исходные данные:
Количество элементов итогового массива n:25
Исходный массив А:
21474836477 23 22 21 20 19 18.5 17 16 15 14 13 12 11 10 9 8 7 6 5
Ожидаемый результат:
Некорректные данные.
Полученный результат:
Рисунок 8—Тест 2.4
Тест 2.5
Тестовая ситуация: Ошибка ввода
Исходные данные:
Количество элементов итогового массива n:25
Исходный массив А:
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Исходный массив B:
20 1а9б 18 17 16 15
Ожидаемый результат:
Некорректные данные.
Полученный результат:
Рисунок 9—Тест 2.5
[1] Величина с постоянным значением, ограниченная типом integer