Сжать массив, удалив элементы, принадлежащие интервалу

Задача

Сжать массив, удалив из него все элементы, величина которых находится в интервале [а, b]. Освободившиеся в конце массива элементы заполнить нулями.

Пояснение к задаче и алгоритм решения

Задачу можно разбить на три подзадачи:

  1. Удаление элементов массива, принадлежащих заданному интервалу.
  2. Сдвиг оставшихся элементов.
  3. Заполнение "освободившейся" части массива нулями.

На самом деле первая и вторая подзадача решаются совместно по следующему алгоритму:

  1. В цикле перебираем элементы массива, начиная с первого.
  2. При обнаружении элемента, принадлежащего удаляемому интервалу,
  3. размерность массива уменьшаем на единицу (поэтому лучше использовать цикл while, а не for.),
  4. остальную (правую) часть массива сдвигаем на одну ячейку в лево.

Сдвиг правой части массива выполняется в цикле от текущего индекса элемента до размерности массива.

После того, как все элементы, принадлежащие заданному интервалу будут удалены, следует заполнить конец массива нулями от элемента с индексом на единицу больше новой размерности массива до количества элементов в "старом" массиве.

Данная задача схожа с этой.

Исходный код на языке программирования Pascal

const N = 10;
var
    a: array[1..N] of integer;
    l, h: integer;
    i, k, m: byte;
begin
    write('Границы массива: ');
    readln(l,h);
    randomize;
    for i:=1 to N do begin
        a[i] := random(h-l) + l;
        write(a[i]:4)
    end;
    writeln;

    write('Удалить элементы в интервале: ');
    readln(l,h);
    i := 1;
    m := N;
    while i<=m do
        if (a[i] >= l) and (a[i] <= h) then begin
            m := m-1;
            for k:=i to m do
                a[k] := a[k+1];
            { здесь не сдвигаемся вперед, так как
             записанный в текущую (i) ячейку элемент не проверялся }

        end
        else
            i := i+1;
    for i:=m+1 to N do
        a[i] := 0;
 
    for i:=1 to N do
        write(a[i]:4);
    writeln;
end.

Пример(ы) выполнения программы на языке Pascal

Границы массива: -10 10
  -5 -10  -6   3   4   4  -6   2   0  -6
Удалить элементы в интервале: -5 5
 -10  -6  -6  -6   0   0   0   0   0   0

Исходный код на языке программирования C

#include <stdio.h>
#define N 10
main() {
    int a[N], i,j, m, l,h;
    printf("Границы массива: ");
    scanf("%d%d", &l,&h);
    srand(time(NULL));
    for (i=0; i<N; i++) {
        a[i] = rand()%(h-l) + l;
        printf("%d ", a[i]);
    }
    printf("\n");
   
    printf("Удаляемый диапазон: ");
    scanf("%d%d", &l,&h);
    i = 0;
    m = N;
    while (i < m)
        if (a[i] <= h && a[i] >= l) {
            m -= 1;
            for (j=i; j < m; j++)
                a[j] = a[j+1];
        } else
            i += 1;
   
    for (i=m; i<N; i++) a[i]=0;
    for (i=0; i<N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

Пример(ы) выполнения программы на языке C

Границы массива: -23 35
-13 4 23 11 -8 14 26 2 -11 6
Удаляемый диапазон: -10 14
-13 23 26 -11 0 0 0 0 0 0

Исходный код на языке программирования Python

from random import random
N = 10
a = []
l = int(input('Нижняя граница массива: '))
h = int(input('Верхняя граница массива: '))
for i in range(N):
    n = int(random()*(h-l)) + l
    a.append(n)
print(a)
print('Удаляемый диапазон')
l = int(input('   нижняя граница: '))
h = int(input('   верхняя граница: '))
i = 0
m = N
while i < m:
    if l <= a[i] <= h:
        del a[i]
        m -= 1
    else:
        i += 1
for i in range(m,N):
    a.append(0)
print(a)

Пример(ы) выполнения программы на языке Python

Нижняя граница массива: 50
Верхняя граница массива: 100
[77, 97, 57, 75, 73, 91, 78, 75, 58, 54]
Удаляемый диапазон
   нижняя граница: 55
   верхняя граница: 75
[77, 97, 91, 78, 54, 0, 0, 0, 0, 0]

Исходный код на языке программирования КуМир

алг сжатие
нач
    цел N = 10
    цел таб a[1:N]
    цел i,k,m, l,h
    вывод "Границы массива: "
    ввод l, h
    нц для i от 1 до N
        a[i] := irand(l,h)
        вывод a[i], " "
    кц
    вывод нс
    вывод "Границы удаляемого интервала: "
    ввод l, h
    i := 1
    m := N
    нц пока i <= m
        если a[i] <= h и a[i] >= l то
            m := m-1
            нц для k от i до m
                a[k] := a[k+1]
            кц
        иначе
            i := i + 1
        все
    кц
    нц для i от m+1 до N
        a[i] := 0
    кц

    нц для i от 1 до N
        вывод a[i], " "
    кц
кон

Пример(ы) выполнения программы на языке КуМир

Границы массива: 10 20
20 14 18 16 16 13 11 12 20 14
Границы удаляемого интервала: 14 16
20 18 13 11 12 20 0 0 0 0

Исходный код на языке программирования Basic

input "Нижняя граница массива: ", l
input "Верхняя граница массива: ", h
N = 10
dim a(N)
for i=0 to N-1
        a[i] = int(rand*(h-l)) +l
        print a[i] + " ";
next i
print

print "Удалить элементы в интервале"
input "от ", l
input "до ", h
i = 0
m = N
while i < m
        if a[i] <= h and a[i] >= l then
                m = m-1
                for j=i to m-1
                        a[j] = a[j+1]
                next j
        else
                i = i + 1
        endif
endwhile

for i=m to N-1
    a[i] = 0
next i

for i=0 to N-1
    print a[i] + " ";
next i
print

Особенности решения на языке программирования Basic

Возникает ошибка, если последний элемент входит в удаляемый диапазон. Для цикла сдвига пишет, что начальный индекс больше конечного.

Тема

Массивы

Уровень сложности

Сложный

Дата публикации