Решение задач второго класса
Характерным признаком задач второго класса является изменение порядка следования элементов массива. Для этого часто приходится менять местами элементы массива. Эта работа в C# выполняется с помощью приведенных ниже операторов:
//обменять местами элементы a[i] и a[j]
r=a[i]; // запомнили a[i] во вспомогательной переменной
a[i]=a[j]; /* записали значение a[j] на место a[i], старое значение последнего потерялось, но сохранилась его копия в переменной r */
a[j]=r // записали запомненное значение a[i] на место a[j]
Частой ошибкой при решении задач этого класса является потеря нужного значения вследствие записи на его место другого значения. Ниже приводятся характерные задачи этого класса и методы их решений.
Пример 6. Разделить каждый элемент одномерного массива на его пятый элемент.
Решение. Например, для массива a={1, 2, 3, 4, 5, 6, 7, 8, 9} должен получиться результат a={1/5, 2/5, 3/5, 4/5, 1, 6/5, 7/5, 8/5, 9/5}. Ясно, что пятый элемент результата всегда будет равен 1, поэтому исходное значение этого элемента нужно сохранить, иначе последующие элементы будут вычислены неправильно. Для хранения исходного значения пятого элемента используем переменную r. Поскольку требуется разделить КАЖДЫЙ элемент массива, то выберем схему перебора по одному. Вообще, если в условии задачи встречаются слова КАЖДЫЙ, ВСЯКИЙ, ДЛЯ ВСЕХ элементов массива, то это означает, что в решении появится цикл перебора элементов. Таким образом, формулировка задачи может подсказать решение.
r=a[4];
for (i=0; i<n; i++) a[i]:=a[i]/r;
Пример 7. Задан одномерный массив. Нужно переставить его элементы в обратном порядке. Другой массив использовать не разрешается. Например, для массива a={1,2,3,4,5,6,7,8,9} получится результат a={9,8,7,6,5,4,3,2,1}.
Решение. Заметим, что при преобразовании меняются местами два элемента: первый и последний, второй и предпоследний и так далее. В случае нечетного количества элементов в массиве имеется центральный элемент, который должен меняться сам с собой, т.е. остаться на месте. Меняются элементы, расположенные симметрично относительно центра массива. Индексы каждой пары таких элементов можно определить по следующим формулам: i и n-1-i. Всего в массиве должно произойти n/2 обменов. Последняя фраза легко переводится на C#: нужно организовать арифметический цикл со счетчиком до n/2, в теле которого меняются местами элементы a[i] и a[n-1-i].
for (i=0; i<= n/2; i++)
{ r=a[i];
a[i]=a[n-1-i];
a[n-1-i]=r;
}
Другое решение этой задачи можно получить, если ввести обозначения для пары меняемых элементов: i - элемент, входящий в пару и расположенный в начале массива, а j - соответствующий элемент пары, расположенный в конце массива. При таком соглашении i должно быть меньше j. Если i= = j, то они указывают на один и тот же элемент, который можно не менять. Если i>j, то пар больше нет. Таким образом, имеем итерационный цикл, который выполняется до тех пор, пока есть пары элементов. В теле цикла a[i] и a[j] меняются местами.
i=0; j=n-1;
while (i<j)
{ r=a[i];
a[i]=a[j];
a[j]=r;
i++; j--;
}
Пример 8. Задан одномерный массив. Нужно переставить в обратном порядке его элементы, начиная с элемента с индексом p и заканчивая элементом с индексом q. Дополнительный массив использовать не разрешается. Например, для массива a={1,1,2,3,4,5,6,7,7,7,7,8} и p=2, а q=6 получится результат a={1,1,6,5,4,3,2,7,7,7,7,8}.
Решение. Заметим, что эта задача похожа на предыдущую. В ней изменялся массив целиком, а здесь только часть, расположенная между элементами с индексами p и q включительно. Решение этой задачи легко получается из второго решения предыдущей задачи заменой начальных значений переменных i и j.
i=p;
j=q;
while (i<j)
{ r=a[i];
a[i]=a[j];
a[j]=r;
i++;
j--;
}.
Пример 9. Сдвинуть элементы одномерного массива на r элементов вправо. Выпадающие из массива элементы становятся в его начало. Например, для исходного массива a={1,2,3,4,5,6,7,8,9} и r=3 последовательно получаем: после первого сдвига a={9,1,2,3,4,5,6,7,8}, после второго сдвига a={8,9,1,2,3,4,5,6,7}, после третьего сдвига a={7,8,9,1,2,3,4,5,6}.
Решение. Описанную выше идею можно положить в основу алгоритма. Тогда для решения задачи нужно r раз выполнить следующее: запомнить последний элемент; сдвинуть все оставшиеся элементы на один вправо; записать запомненный элемент на первое место в массиве. Получаем решение:
for (i=0; i< r; i++)
{ s=a[n-1];
for (j=n-1; j>=0; j--) a[j+1]=a[j];
a[0]:=s
}
Недостатком предложенного алгоритма является его медленная работа. В самом деле, для сдвига массива на r элементов требуется просмотреть массив r раз. Если воспользоваться алгоритмом переворота части массива, то можно получить результат за один просмотр массива. Для этого последовательно выполняем следующие операции (операции показаны на примере массива a={1,2,3,4,5,6,7,8,9} и r=3):
1) переворачиваем часть массива между индексами 7 - 9; получаем: a={1,2,3,4,5,6,9,8,7};
2) переворачиваем часть массива между индексами 1 - 6; получаем: a={6,5,4,3,2,1,9,8,7};
3) переворачиваем весь массив; получаем: a={7,8,9,1,2,3,4,5,6}.
Упражнения:
1. Запишите описанный алгоритм на C#.
2. Докажите, что в этом алгоритме массив просматривается один раз при любом r.
3. Напишите аналогичный алгоритм для сдвига массива влево.