Пример 4.5.
Включить заданное число D в массив A(N), упорядоченный по
возрастанию, с сохранением упорядоченности.
Система тестов
|
Номер теста
|
Проверяемый случай
|
Данные
|
Результат
|
|
D
|
Массив А
|
|
1
|
D <= a1
|
0
|
A=(1, 3, 5)
|
A=(0, 1, 3, 5)
|
|
2
|
a1< D <= aN
|
4
|
A=(1, 3, 5)
|
A=(1, 3, 4, 5)
|
|
3
|
aN < D
|
6
|
A=(1, 3, 5)
|
A=(1, 3, 5, 6)
|
Демонстрация
Школьный АЯ
алг Включение (арг цел N, арг вещ D, арг рез вещ таб A[1:N+1])
дано | А - упорядоченная по возрастанию последовательность
надо | в А включено число D с сохранением упорядоченности
нач цел i
i:=N
нц пока (i>=1) и (A[i]>D)
A[i+1] := A[i] | сдвиг очередного элемента вправо на одну позицию
i := i-1
кц
A[i+1] := D | включение числа D в последовательность
кон
Исполнение алгоритма
Обозначение проверяемого условия:
(i >= 1) и (A[i] > D) => (1)
|
Номер теста
|
i
|
(1)
|
Массив А
|
|
1
|
3
2
1
|
+
+
+
-(кц)
|
(1, 3, 5)
(1, 3, 5, 5)
(1, 3, 3, 5)
(1, 1, 3, 5)
(0, 1, 3, 5) |
|
2
|
3
2
|
+
-(кц)
|
(1, 3, 5)
(1, 3, 5, 5)
(1, 3, 4, 5) |
|
3
|
3
|
-(кц)
|
(1, 3, 5)
(1, 3, 5, 6) |
|
Блок-схема (фрагмент)
|
Turbo Pascal
Program Insertion;
Uses Crt;
Var A : Array [1..20] of Real;
D : Real;
N, i : Integer;
{--------------------------------------------}
Procedure InputOutput; {описание процедуры ввода-вывода}
Begin ClrScr;
Write(’Количество элементов массива - ’); ReadLn(N);
WriteLn(’Введите элементы массива, упорядоченные по возрастанию:’);
For i := 1 to N do
begin Write(’A[’ , i , ’] = ’); ReadLn(A[i])
end; WriteLn;
Write(’Введите число, которое требуется включить в массив: ’);
ReadLn(D);
ClrScr; Write(’Исходный массив :’);
For i := 1 to N do Write(A[i] : 5 : 1); WriteLn;
WriteLn(’Включаемый элемент – ’, D : 5 : 1);
End; { of InputOutput }
{--------------------------------------------}
Procedure Insert; {описание процедуры включения нового элемента}
Begin
i:=N;
While (i>=1) and (A[i]>D) do
begin A[i+1] := A[i]; {сдвиг очередного элемента вправо}
i:=i–1
end;
A[i+1] := D {включение числа D в последовательность}
End;
{--------------------------------------------}
Procedure Result; {описание процедуры вывода результатов}
Begin WriteLn;
Write(’О т в е т : массив с включенным элементом ’);
For i := 1 to N+1 do Write( A[i] : 5 : 1); WriteLn;
ReadLn
End;
{--------------------------------------------}
BEGIN
InputOutput; {вызов процедуры ввода-вывода }
Insert; {вызов процедуры включения нового элемента}
Result; {вызов процедуры вывода результатов }
END.
QBasic
CLS
INPUT "Количество элементов массива – ", N
DIM A(N+1)
PRINT "Введите элементы массива, упорядоченные по возрастанию:"
FOR i = 1 TO N
PRINT "A(" ; i ; ") = " ; : INPUT A(i)
NEXT i : PRINT
INPUT "Введите число, которое требуется включить в массив: ", D
CLS : PRINT "Исходный массив – ";
FOR i = 1 TO N
PRINT A(i) ;
NEXT i : PRINT
PRINT "Включаемый элемент – "; D
i = N
WHILE i >= 1 AND A[i]>D
A(i+1) = A[i] : i = i – 1 'сдвиг очередного элемента вправо
WEND
A(i+1) = D ’включение числа D в последовательность
PRINT : PRINT "О т в е т : массив с включенным элементом ";
FOR i = 1 TO N + 1
PRINT A(i) ;
NEXT i : PRINT
END