Алгоритмическое мышление при решении задач (на примере языка C#). Шамшев А.Б - 16 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

16
ПРОСМАТРИВАЛИ четверку, которая после удаления стала нулевым
элементом массива. А это ошибка.
Если обобщить, то ошибка звучит следующим образом: элемент после
удаляемого не проверяется на необходимость удаления. Очевидно, что если в
массиве будет 2 элемента подряд, которые необходимо удалить, то эта ошибка
«всплывет» (не будет удален второй элемент). Причина этой ошибки
кроется в
том, что мы не учли важное следствие удаления по индексу – смещение
индексации элементов после удаляемого.
Если мы удалили элемент, то все элементы после него сами к нам
«пододвигаются» и поэтому нам не надо переходить на следующий элемент.
Однако операция i++ будет выполнена в любом случае (как действие в конце
итерации цикла), поэтому ее можно только «компенсировать». Если мы
уменьшим i на 1, а потом увеличим на 1, то i не изменится. Поэтому алгоритм
на псевдокоде будет выглядеть следующим образом:
Для каждого индекса от 0 до размер массива - 1
Начало действия
Если элемент с текущим индексом равен удаляемому, то
НачалоЕсли
Удалить элемент по текущему индексу.
Уменьшить текущий индекс на 1.
ОкончаниеЕсли
Окончание действия.
Реализация этого алгоритма будет следующая:
public static void delByValue(ref int[] data, int delValue) {
for (int i = 0; i < data.Length; i++) {
if (data[i] == delValue) {
delByIndex(ref data, i);
i--;
}
}
}
Следует отметить, что в delByIndex есть уменьшение размера массива, и
как следствие условие в условии i < data.Length нельзя заменить data.Length на
константу (в данном случае 8).
Однако существует другой, более оптимальный метод решения этой
задачи. В псевдокоде мы писали «Для каждого элемента массива». Но при этом
не сказано, как обходятся элементы массива – от начала к концу
массива или от
конца к началу.
Рассмотрим, что будет, если мы будем обходить массив от конца к началу.
Последний элемент в массиве размером data.Length имеет индекс data.Length –
1, поэтому надо начинать с него. Мы будем двигаться к началу массива, т. е.
текущий индекс будет уменьшаться (i--). Мы должны просмотреть все
элементы, включая нулевой, поэтому
условие окончания прохода по циклу
будет (i >= 0).

Страницы