Задачи для изучающих программирование самостоятельно 30 Задания на лабораторную работу по теме "Обработка одномерных массивов" 39
| Вид материала | Документы |
- Обработка одномерных массивов, 21kb.
- Поэтому при написании программы будьте особенно внимательны, не путайте индексы элементов, 363.59kb.
- Лекция № Распределение памяти. Динамические переменные, 73.48kb.
- Алгоритмы сортировки одномерных массивов, 53.15kb.
- Урок 6 (1 час) Тема урока, 169.57kb.
- Поняття масиву. Одновимірний масив, 62.45kb.
- План урока Выступление со словами: Нередко… Показ презентации, 73.14kb.
- Курс является базовым как для изучения других математических дисциплин, так и для более, 36.89kb.
- В. А. Давыденко программирование и основы алгоритмизации лабораторный практикум, 1951.1kb.
- Методические указания могут быть полезны для студентов экономических специальностей,, 198.11kb.
Вставка новых элементов в массив
Задача 11: В массив после максимального элемента вставить элемент, равный 0.
Пример исходного массива A: 1 2 5 1 0 1 2
максимальный элемент A[3]=5
Массив после вставки элемента: 1 2 5 0 1 0 1 2
Алгоритм вставки элемента в массив:
1. Сдвинуть элементы от позиции вставляемого элемента в конец.
2. В позицию вставляемого элемента вписать нужное значение.
3. Количество элементов n увеличить на 1 .
Общий алгоритм программы следующий:
1 . Введем массив А.
2 . Найдем индекс max элемента.
3 . Вставим после max 0.
4 . Выведем получившийся массив.
Приведем полный текст программы:
{Пример обработки одномерного массива}
{ Задание: В массив после максимального элемента
вставить элемент, равный 0}
Program InsertExample;
Const {определение констант}
maxN = 20; {максимально возможное количество элементов
в массиве}
Type {определение типов}
IndexEll = 1 .. maxN; {индексы массива лежат в интервале
от 1 до maxN}
arrInt = array[interval] of integer; {массив целых чисел,
содержащий до maxN элементов}
Var
a:arrInt; {массив}
n:integer; {количество элементов в массиве}
i:IndexEl; {переменная для сканирования массива}
max: IndexEl; {номер max элемента массива}
Begin
{1 - ввод массива - генерируем случайные элементы}
randomize;
n:=random(6)+5; {n в интервале 5..10}
for i:=1 to n do
A[i]:=random(19)-9; {Генерируем элементы массива}
{ каждый элемент имеет значение в интервале -9..9}
{2 - ищем индекс max элемента}
max:=1;
for i:=2 to n do
if A[i]>A[max] then max:=i;
{3- вставляем 0 после максимального элемента}
{сначала сдвигает “хвост” массива вправо}
for i:=n downto max+1 do
A[i+1]:=A[i];
{заносим в следующий за максимальным элемент 0}
A[max+1]:=0;
{увеличиваем количество элементов массива}
Inc(n);
{4 - выводим массив}
writeln('Массив А после вставки:');
for i:=1 to n do
write(A[i]:3);
readln; {ждем нажатия клавиши Enter}
End.
Данная программа демонстрирует модульный подход к решению задач - задача разбивается на подзадачи, полученные подзадачи решаются отдельно. Если подзадача не решается непосредственно, то она снова разбивается на подзадачи и т.д. Такой подход называется "программирование сверху вниз".
Замечание: данная программа таит в себе ошибку. Если n=20, то после вставки еще одного элемента n станет равной 21, и, скорее всего, программа повиснет (потому что элементов в массиве может быть НЕ БОЛЬШЕ 20). Следовательно, при вставке элементов необходимо следить, чтобы было n<=maxN .
Удаление нескольких элементов массива
Задача 12: Удалить из массива все элементы между k-м и z-м элементами.
Рассмотрим задачу на примере при количестве элементов в массиве n=10, k=3, z=7 (т.е. надо удалить элементы между третьим и седьмым).
Будем использовать переменную d - количество удаляемых элементов. Значение d можно вычислить по формуле: d = z - k – 1 ( в нашем примере получится d = 7 - 3 - 1 = 3).
Массив A до удаления:
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
1 3 9 1 0 1 3 2 7 2
a[k] a[z] a[n]
Массив A после удаления:
a[1] a[2] a[3] a[4] a[5] a[6] a[7]
1 3 9 3 2 7 2
a[k] a[z] a[n]
После удаления n стало меньше на d (в нашем примере на 3).
Общий алгоритм решения:
1 . Сдвинуть элементы вперед на d элементов, начиная с z-го.
2 . Уменьшить n на d.
Фрагмент программы:
Var {дополнительные переменные}
k: integer; {индекс элемента, после которого удаляем}
z: integer; {индекс элемента, до которого удаляем}
d: integer; {количество удаляемых элементов}
…
Begin
…
{вычисляем количество удаляемых элементов}
d:=z-k-1;
{1 - сдвигаем элементы}
for i:=z to n do
A[i-d]:=A[i];
{2 - уменьшаем n на d}
Dec(n,d);
…
Задача 13: Из массива удалить все элементы, которые меньше 0.
Рассмотрим два решения этой задачи.
Алгоритм первого решения:
1. Просматриваем массив .
2. Если элемент<0, то удаляем его и n уменьшаем.
3. Если элемент>=0, то переходим к следующему.
Фрагмент программы:
…
{в цикле просматриваем элементы массива}
i:=1;
while i<=n do
begin
{проверяем ,не нужно ли i-ый элемент удалять}
if A[i]<0 then
begin
{если нужно – удаляем i-ый элемент}
for j:=i to n-1 do {сдвигаем}
A[j]:=A[j+1];
Dec(n); {уменьшаем количество элементов}
end
else Inc(i); {если удалять не нужно, то переходим
к следующему элементу}
end;
Пример прогона алгоритма:
Исходный массив:
0: i=1, n=6: -1 -2 2 -3 -4 3
Состояния массива после обработки очередного элемента массива:
1: i=1, n=5: -2 2 -3 -4 3 (удален -1)
2: i=1, n=4: 2 -3 -4 3 (удален -2)
3: i=2, n=4: 2 -1 -2 3 (перешли на следующий)
4: i=2, n=3: 2 -4 3 (удален -3)
5: i=2, n=2: 2 3 (удален -4)
6: i=3, n=2: 2 3 (перешли на следующий)
Алгоритм второго решения:
1. Счетчик переписанных элементов k=0.
2. Просматриваем элементы массива.
3. Если элемент A[i] не меньше 0, k увеличиваем на 1 и переписываем элемент A[i] на k-ое место.
4. После просмотра всего массива количество переписанных элементов k заносим в n.
Фрагмент программы:
Var {дополнительные переменные}
k:IndexEl; {количество переписанных элементов}
…
Begin
...
{1 - переписанных элементов пока не было}
k:=0;
{2 - в цикле просматриваем элементы массива}
for i:=1 to n do
{3 - если A[i] не <0}
if not(A[i]<0) then
begin
Inc(k); {увеличиваем значение k на 1}
A[k]:=A[i]; {переписываем i-ый элемент в позицию k}
end;
{4 - в массиве оставляем k элементов}
n:=k;
Пример прогона алгоритма:
Исходный массив: -1 -2 2 -3 -4 3
Состояния массива после просмотра очередного элемента массива:
0: k=0, i=1, n=6: -1 -2 2 -3 -4 3 {не переписываем}
1: k=0, i=2, n=6; -1 -2 2 -3 -4 3 {не переписываем}
2: k=1, i=3, n=6; 2 -2 2 -3 -4 3 {переписываем
a[1]:=a[3]}
3: k=1, i=4, n=6; 2 -2 2 -3 -4 3 {не переписываем}
4: k=1, i=5, n=6; 2 -2 2 -3 -4 3 {не переписываем}
5: k=2, i=6, n=6; 2 3 2 -3 -4 3 {переписываем
a[2]:=a[6]}
6: k=2, i=7, n=6: 2 3 2 -3 -4 3 {выход из цикла}
7: n=2: 2 3 {значение k переписываем в n}