Глава 3. Алгоритмы, использующие
одномерные массивы
Массив - это упорядоченный набор однотипных значений (элементов массива). Каждый массив имеет имя, что дает возможность различать массивы между собой и обращаться к ним по имени.
Каждый элемент массива имеет три характеристики:
1) имя, совпадающее с именем массива;
2) индекс - это целое число или множество целых чисел, однозначно определяющее местоположение элемента в массиве. В качестве индекса может использоваться также переменная или арифметическое выражение целого типа. Примеры индексов: 3, 15, i, j, i - 1, j + 2. Индексы принято указывать в скобках после имени массива.
3) значение.
Пример 1. х[50] = 90. Здесь х - имя массива, 50 - индекс, 90 - значение.
Элементы массива могут выбираться произвольно и являются одинаково доступными. Доступ к элементам массива производится по его индексу.
Различают разные виды массивов в зависимости от их внутреннего строения и взаимного расположения элементов.
Массивы могут быть числовыми и символьными (текстовыми). Например, список студентов группы - символьный массив, а оценки студентов - числовой массив.
Также массивы могут быть одномерными и многомерными (двумерными, трехмерными и т.д.). В этой главе мы будем рассматривать только одномерные массивы.
3.1. Ввод и вывод элементов массива
Одномерный массив определяется именем и числом элементов (размером) и мы обозначим его a[n], где a - имя массива; n - число элементов массива. Например, a[10]. Каждый элемент одномерного массива имеет один индекс, равный порядковому номеру элемента в массиве. Например, массив из 10 элементов выглядит так:
| Индекс | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| А | 3 | 0 | 15 | 4 | 6 | -2 | 11 | 0 | -9 | 7 |
a[1] = 3; a[5] = 6; a[7] = 11; a[9] = -9; a[10] = 7.
Так как всегда известно количество элементов в массиве, то для ввода и вывода его элементов используется цикл с заданным числом повторений.
Мы рассматриваем массив, состоящий из произвольного числа элементов. Поэтому, прежде чем задать значения элементов массива, требуется ввести количество элементов массива n.
| Ввод элементов массива | Вывод элементов массива |
| Ввод(n); Ввод (a[i]); кц | нц Вывод (a[i]); кц |
Здесь и далее мы будем обозначать через i - текущий индекс элемента массива. Он же будет являться параметром цикла, так как количество повторений цикла зависит от количества элементов в массиве.
3.2 Задачи заполнения массива
При решении задач приходится заполнять массивы (присваивать значения элементам). Рассмотрим несколько способов заполнения массивов.
Первый способ заполнения одномерного массива - это ввод данных с клавиатуры.
Второй способ - это заполнение с помощью генератора случайных чисел.
Третий способ - использование оператора присваивания.
Ввод элементов с клавиатуры нами только что был рассмотрен. Посмотрим, как используется генератор случайных чисел. Мы должны воспользоваться стандартными процедурами, определенными в том языке программирования, который вы будете использовать. Мы предполагаем, что процедура Randomize устанавливает генератор случайных чисел в начальное состояние, а функция Random генерирует случайное число.
Randomize;
нц
Для i от 1 до n повторять
a[i] = -25 + Random(51)
кц
Диапазон генерируемых случайных чисел от 0 до -25 + (51 - 1) = 25.
Если все элементы массива имеют одно и тоже значение, то для его задания удобно использовать оператор присваивания:
нц
Для i от 1 до n повторять
a[i] = 0
кц
Все элементы массива получат значение, равное нулю.
Далее во всех задачах мы будем считать, что элементы массива заданы тем или иным способом и показывать только реализацию алгоритма решения задачи, опуская команды ввода данных и вывода результата.
Пример 3.1. Сформировать новый одномерный массив из положительных элементов заданного массива.
Дано: n - размер массива произвольный, массив Х[n].
Найти: массив Y[n].
Обозначим: i - текущий индекс элементов массива Х, k - текущий индекс элементов массива Y.
Ясно, что для реализации алгоритма необходимо использовать цикл с заданным числом повторений, так как количество элементов в массиве Х известно. Приведем фрагмент блок-схемы алгоритма и описание алгоритма на псевдокоде.
|
|
k =0 нц Если X[i] > 0 То k = k+1; Y[k] = X[i] Все если кц
|
Тест
| Данные | Результат |
| N = 7 X = (-1, 2, 0, 4, -3, -2 0) |
Y = (2, 4) |
Задачи для самостоятельного решения
1. Заполните массив {ai} размера n нулями.
2. Заполните массив {ai} размера n четными числами.
3. Заполните массив {ai} размера n числами Фибоначчи. Числа Фибоначчи определяются рекуррентными соотношениями a1 = 1; a2 = 2; ai = ai-1 + ai-2.
4. Заполните массив, запрашивая значения элементов в диалоге.
5. Заполните массив случайными числами в интервале от 1 до k.
6. Робот стоит перед входом в коридор, уходящий в бесконечность вправо. В коридоре много закрашенных клеток. Запишите в массив уровни радиации в первых N закрашенных клетках.
7. Робот стоит перед входом в коридор, который ведет вправо и заканчивается тупиком. Некоторые клетки закрашены. Запишите в массив уровни радиации в закрашенных клетках.
8. Из заданного массива {ai} размером n запишите в массив {bi} элементы, удовлетворяющие условию ai <= T, где Т - произвольное число.
3.3. Задачи анализа массива
Мы используем циклы с заданным числом повторений. Напомним, что циклы с заданным числом повторений (арифметические циклы) применяются, когда число повторений цикла известно к началу его выполнения.
Пример 3.2. Вычислить сумму элементов одномерного массива.
Дано: n - размер массива, массив А = (a1, a2, ... ,an).
Найти S - сумму элементов массива.
| Фрагмент алгоритма | Исполнение алгоритма | |
| S = 0 нц Для i от 1 до n повторять S = S + a[i] кц
| i | S |
|
| 0 | |
| 1 | 0+ a1 = 0 + 3 = 3 | |
| 2 | a1 +a2 = 3 + 5 = 8 | |
| 3 | a1 +a2 + a3 = 8 - 2 = 6 | |
| 4 | a1 +a2 + a3 + a4 = 6 + 6 = 12 | |
Тест
| Данные | Результат | |
| N = 4 | A = (3, 5, -2, 6) | S = 12 |
Пример 3.3. Найти сумму элементов одномерного массива, кратных заданному числу.
Дано: n - размер массива, массив А = (a1, a2, ... ,an), k - заданное число.
Найти S - сумму элементов массива, кратных числу k.
Математическая модель:
Пусть S - сумма элементов массива. Будем суммировать не все элементы, а только те, которые удовлетворяют заданному условию, то есть только те, которые делятся нацело на заданное число (остаток от деления на данное число равен 0). Для вычисления остатка от деления числа нацело используем операцию Mod.
Фрагмент алгоритма:
Ввод k
S = 0
нц
Для i = 1 до n повторять
Если (a [i] Mod k =0) то s = s + a [i]
Все если
кц
Тест
| Данные | Результат | ||
| N = 5 | A = (3, 5, -2, 8, 9) | k=3 | S = 12 |
Пример 3.4. Найти количество положительных и отрицательных чисел в данном массиве.
Дано: n - размер массива, массив А = (a1, a2, ... , an). Обозначим k1 - количество положительных чисел, k2 - количество отрицательных чисел.
Найти k1, k2 - количество положительных и отрицательных чисел массива.
Математическая модель:
Пусть k1 = 0 и k2 = 0. Если a[i] > 0, то k1 = k1 + 1. Если a[i] < 0, то k2 = k2 + 1. Процесс повторяется до просмотра всех чисел массива.
k1 = 0; k2 = 0
нц
Для i от 1 до n повторять
Если a [i] > 0 то k1 = k1 + 1 Все если
Если a[i] < 0 то k2 = k2 + 1 Все если
кц
Вывод "Количество положительных чисел", k1
Вывод "Количество отрицательных чисел", k2
В примере нам понадобилось два условных оператора, т.к. в массиве могут встретиться нулевые элементы, количество которых нам считать не надо.
3.4. Нахождение элементов, обладающих
определенным свойством
Пример 3.5. Дан массив произвольной длины. Найти наибольший элемент массива и определить его номер.
Дано: n - размер массива; массив А = (a1, a2, ... , an).
Найти Amax - наибольший элемент массива; k - его номер.
Математическая модель:
Пусть Amax = a[0]; k = 0;
Если Amax < a[i], то Amax = a[i], k = i, для i = 1, 2, 3, ..., n - 1.
|
| i | Amax< A[i] | Amax | k |
|
|
| 3 | 1 | |
| 2 | -1 < 3? Да |
|
| |
| 3 | 10 < 3? Нет | 10 | 3 | |
| 4 | 1 < 10? Да |
|
| |
| 5 | 6 < 10? Да |
|
| |
|
|
|
|
|
Тест
| Данные | Результат | ||
| N = 4 | A = (3, -1, 10, 1, 6) | Amax = 10 | k = 3 |
Пример 3.6. Задан числовой массив A[n]. Найти длину самой длинной последовательности идущих подряд элементов массива, равных нулю.
Этот алгоритм использует алгоритм нахождения наибольшего числа среди группы чисел, который мы только что рассмотрели.
Обозначим: A[n] - массив вещественных чисел, где n - размер массива. Max - длина наиболее длинной последовательности подряд идущих нулей; len - длина последовательности из подряд идущих нулей.
| Фрагмент алгоритма | Комментарии |
| len = 0 max = 0 нц Для i от 0 до n повторять Если a[i] <> 0 то Если max < len то max = len len = 0 Все если иначе len = len + 1 Все если кц Если (max < len) max=len
| Присваивание начальных значений В цикле выполняем следующие действия: 1) Если очередной член последовательности не равен нулю, то вычисляем наибольшее значение из длин последовательности идущих подряд нулевых элементов. 2) После окончания работы оператора «если» обнуляем значение len, для определения длины новой последовательности. 3) Определяем длину последовательности из нулей. По окончании цикла сравниваем длину последней последовательности с наибольшим значением. |
Тест
| Данные | Результат | |
| N = 10 | A = (3, 0, 0, 2, 3, 0, 0, 0, 6, 0) | max = 3 |
Результаты работы алгоритма.
| i | A[i] | A[i] <> 0? | len < max? | len | max |
|
|
|
|
| 0 | 0 |
| 1 | 3 | 3 <> 0? Да | 0 < 0? Нет |
|
|
| 2 | 0 | 0 <> 0? Нет |
| 0 + 1 = 1 |
|
| 3 | 0 | 0 <> 0? Нет |
| 1 + 1 = 2 |
|
| 4 | 2 | 2 <> 0? Да | 0 < 2? Да | 0 | 2 |
| 5 | 3 | 3 <>0? Да | 2 < 0? Нет |
|
|
| 6 | 0 | 0 <> 0? Нет |
| 0 + 1 = 1 |
|
| 7 | 0 | 0 <> 0? Нет |
| 1 + 1 = 2 |
|
| 8 | 0 | 0 <> 0? Нет |
| 2 + 1 = 3 |
|
| 9 | 6 | 6 <> 0? Да | 2 < 3? Да | 0 | 3 |
| 10 | 0 | 0 <> 0? Нет |
| 0 + 1 = 1 |
|
|
|
|
| 3 < 1? Нет |
|
|
Итак, в результате работы алгоритма длина самой длинной последовательности подряд идущих нулевых элементов массива, равна 3.
Пример 3.7. Найти и напечатать номера четных элементов массива.
Дано: n - размер массива, массив А = (a1, a2, ... , an).
Найти номера четных элементов массива.
Словесное описание алгоритма:
Необходимо просмотреть весь массив, и если просматриваемый элемент является четным, вывести его номер.
Приведем фрагмент, реализующий этот алгоритм.
нц
Для i от 1 до n повторять
Если (a [i] Mod 2 = 0) То Вывод i;
Тест
| Данные | Результат | |
| N= 11 | A = (3, 0, -4, 2, 3, 20, -5, 15, 6, 5, -1) | 3, 4, 6, 9 |
Задачи для самостоятельного решения
1. Найдите сумму положительных элементов массива и их количество.
2. Определите, сколько элементов массива P размером n удовлетворяет условию Pi > T, где Т - произвольное число.
3. Определите среднее арифметическое элементов массива.
4. Дана последовательность {ai} размером n, где ai = sin2(3i + 5). Определите, сколько членов последовательности с четными номерами имеют значение, меньше чем 0, 25.
5. Даны натуральное число n, действительные числа х1,..., xn. Получите y = (1 + r)/(1 + s), где r - сумма всех тех членов последовательности, которые не превосходят 1, а s - сумма членов, больших 1.
6. Дано натуральное число n, действительные числа y1,...,yn. Найдите
max (|z1|,...,|zn|), где zi = 
7. У прилавка магазина выстроилась очередь из n покупателей. Время обслуживания продавцом i-го покупателя ti (i = 1,..., n). Пусть даны натуральное число n и действительные числа t1,..., tn. Получите c1,...,.cn, где ci - время пребывания i-го покупателя в очереди. Укажите номер покупателя, для обслуживания которого продавцу понадобится наименьшее время.
8. Выясните, какое число в последовательности {аi} встречается раньше, положительное или отрицательное.
9. Даны натуральное число n, действительные числа a1,...,an. В последовательности определите число соседств: а) двух положительных чисел; b) двух чисел одного знака, причем модуль первого числа должен быть больше модуля второго числа.
3.5. Изменение значений некоторых элементов
Пример 3.8. Заменить отрицательные элементы массива их абсолютными величинами.
Дано: n - размер массива, массив А = (a1, a2, ... , an).
Найти массив того же размера, в котором отрицательные числа будут заменены их модулями.
Математическая модель:
Пусть k1 = 0 и k2 = 0. Если а[i] < 0, то а[i] = -а[i]. Вычисления повторяются, пока не будут просмотрены все числа массива.
Приведем фрагмент алгоритма.
нц
Для i от 1 до n повторять
Если a[i] <0 то a[i] = -a[i]
Все если
кц
нц
Для i от 1 дo n повторять {Печать элементов массива}
Вывод a[i]
кц
Тест
| Данные | Результат | |
| N= 9 | A=(-1, 10, 1, -6, -5, 12, 36, -15, -21) | A=(1, 10, 1, 6, 5, 12, 36, 15, 21) |
Пример 3.9. Если очередной элемент массива четный, то прибавить к нему первый, если нечетный - прибавить последний. Первый и последний элементы массива не изменять.
Дано: n - размер массива, массив А = (a1, a2, ... , an).
Найти массив того же размера, в котором к четному элементу будет добавлен первый, а к нечетному - последний.
Математическая модель:
Рассмотрим все элементы массива, кроме первого и последнего. Если а[i] - четный элемент, то а[i] = а[i] + а[1], иначе а[i] = а[i] + а[n]. Процесс повторяется, пока не будут просмотрены все числа массива. Заметим, что число является четным, если оно делится на 2 без остатка.
Приведем фрагмент алгоритма.
нц
Для i от 2 до n - 1 повторять
Если a[i] Mod 2 = 0 То a[i] = a[i] + a[1]
Иначе a[i] = a[i] + a[n]
Все если
кц
Пример 3.10. Дан первый член арифметической прогрессии и ее разность. Записать в массив первые n членов прогрессии.
Обозначим m1 - первый элемент прогрессии, k - ее разность, n - размер массива.
Дано: m1, k, n.
Найти массив A[n].
Математическая модель:
При i = 1, a[1] = m1, i-й элемент массива можно найти по следующему правилу: a[i] = a[i - 1] + k, здесь i меняется от 2 до n.
Приведем фрагмент алгоритма.
a[1] = m1
нц
Для i = 2 до n повторять
a[i] = a[i-1] + k
кц
Пример 3.11. Даны два одномерных массива - А и В. Найти их скалярное произведение.
Дано: n - размер массива, А, В - массивы размера n.
Найти S - скалярное произведение двух массивов.
Математическая модель:
Скалярным произведением двух массивов одинаковой размерности называется сумма произведений соответствующих элементов:
a[1] ? b[1] + a[2] ? b[2] + ... + a[n] ? b[n], где n - количество элементов в массивах.
Фрагмент алгоритма:
s = 0
нц
Для i от 1 до n повторять
s = s + a[i] * b [i]
кц
Тест
| Данные | Результат | |
| N = 5 | A = (3, -1, 10, 1, -6,); | S = 3?2 -1?4 -10?3+1?5 +6?4 = 1 |
Задачи для самостоятельного решения
1. Измените знак у максимального по модулю элемента массива.
2. Замените все четные элементы массива их квадратами, а нечетные элементы - удвойте.
3. Вычтите из положительных элементов массива элемент с номером k1, а к отрицательным прибавить элемент с номером k2, нулевые элементы оставьте без изменения.
4. К четным элементам массива прибавьте произвольное число А, а из элементов с четными номерами вычтите произвольное число В.
5. Отрицательные элементы массива возведите в квадрат.
6. Даны два целочисленных массива, состоящих из одинакового числа элементов. Получите третий массив той же размерности, каждый элемент которого равен наибольшему из соответствующих элементов данных массивов.
Например, даны два массива - А и В, состоящие из пяти элементов. Получим массив С, тоже состоящий из пяти элементов. Первый элемент этого массива равен большему из первых элементов массива А и В, второй - большему из вторых элементов массивов - и так далее.
7. Дан первый член геометрической прогрессии и ее знаменатель. Найдите и запишите в массив первые n членов этой прогрессии.
8. Даны два массива. Найдите среднее арифметическое элементов каждого и сравните эти значения.
3.6. Обмен значений элементов
Пример 3.12. В массиве поменять местами два соседних элемента с номерами k1 и k2.
Номера элементов, которые меняются местами, должны быть известны.
Дано: n - размер массива; A[n] - массив вещественных чисел; k1, k2 - номера элементов, подлежащих обмену.
Найти новый массив А размера n.
Фрагмент алгоритма решения задачи выглядит так:
x = A[k1]; A[k1] = A[k2]; А[k2] = x.
Здесь х - вспомогательная переменная, в которой сохраняется первоначальное значение элемента массива A[k1].
Тест
k1=2; k2 = 6
| Данные | Результат | |
| N=9 | A=(3, 1, 10, 1, 6, 5, 12, 36, -15) | A = (3, 5, 10, 1, 6, 1, 12, 36, -15) |
Усложним задачу.
Пример 3.13. Дан одномерный массив A, состоящий из 2n элементов. Поменять местами его половины.
Дано: 2 ? n - размер массива; A[n] - массив вещественных чисел.
Найти новый массив А размера 2 ? n.
Словесное описание алгоритма.
Пусть массив А состоит из 10 элементов, тогда n = 5. Из массива
А(1, 12, 23, 3, 7, 13, 27, 6, 9, 11) нужно получить массив А(13, 27, 6, 9, 11, 1, 12, 23, 3, 7). Мы должны поменять местами элементы с номерами 1 и 6, 2 и 7, 3 и 8, 4 и 9, 5 и 10, иными словами 1 и n + 1, 2 и n +2, 3 и n + 3, 4 и n + 4, 5 и n + 5. Можно заметить, что элемент с номером i меняется местами с элементом с номером n + i. Поэтому, используя фрагмент алгоритма, приведенный в примере 3.12, можно применить такой цикл:
нц
Для i от 1 до n повторять
x = A[i]
A[i] = A[n + i]
A[n + i] = x
кц
Задачи для самостоятельного решения
1. Дан одномерный массив. Поменяйте местами:
а) первый и максимальный элементы массива;
б) второй и минимальный элементы массива;
в) первый и последний отрицательный элементы массива.
2. Дан одномерный массив А, состоящий из 2n элементов. Поменяйте местами его половины следующим образом: первый элемент поменять местами с последним, второй - с предпоследним и так далее.
3. Дан одномерный массив В, состоящий из 2n элементов. Переставьте его элементы по следующему правилу:
а) b[n + 1], b[n + 2], ..., b[2n], b[1], b[2], ..., b[n];
б) b[n + 1], b[n + 2], ..., b[2n], b[n], b[n - 1],..., b[1];
в) b[1], b[n + 1], b[2], b[n + 2], ..., b[n], b[2n];
4. Дан одномерный массив. Переставьте в обратном порядке элементы массива, расположенные между минимальным и максимальным элементами.
3.7. Удаление и вставка элементов массива
Пример 3.14. Удалить из массива, в котором все элементы различны, наибольший элемент. После удаления массив уплотнить, сдвинув все следующие за ним элементы, влево.
Дано: n - размер массива; A[n] - массив вещественных чисел.
Найти новый массив А размера n - 1.
Для решения задачи необходимо:
1) найти номер k наибольшего элемента массива. Эта задача решена в примере 3.5.
2) сдвинуть все элементы массива, начиная с k-го на один элемент влево.
Для того чтобы разработать алгоритм, рассмотрим конкретный пример. Пусть дан одномерный массив, состоящий из 10 элементов: А(6, 3, 7, 11, 2, 8, 1, 5). Номер наибольшего элемента равен 7 (k = 7), то есть, начиная с седьмого элемента, будем сдвигать элементы на один влево: седьмому элементу присвоим значение восьмого, восьмому элементу присвоим значение девятого, а девятому присвоим значение десятого элемента. На этом сдвиг заканчивается. Таким образом, сдвиг начинается с k-го элемента и заканчивается элементом с номером n - 1, где n -количество элементов в массиве. После этого количество элементов в массиве станет на один элемент меньше. Массив примет вид: А(6, 3, 4, 7, 11, 8, 1, 5).
Фрагмент алгоритма решения задачи:
|
| Нахождение максимального элемента и его номера max = а[1] k = 1 нц Для i от 2 до n повторять Если а[i] > max то max = а[i] k = i Все если кц Сдвиг элементов массива нц Для i от = k до n - 1 повторять а[i] = а[i+1] кц Уменьшение количества элементов массива n = n - 1
|
Мы уже рассматривали подробно алгоритм нахождения максимального элемента массива и его номера. Покажем, как выполняется вторая часть алгоритма (сдвиг элементов массива) для тестового примера.
Тест
| Данные | Результат | |
| N = 8 | A = (6, 3, 7, 11, 2, 8, 1, 5) | A = (6, 3, 7, 2, 8, 1, 5) N = 7 |
В массиве номер наибольшего элемента k = 4. Удаляем этот элемент.
| i | Массив |
| 4; 4 ? 7? Да | А = (6, 3, 7, 2, 2, 8, 1, 5) |
| 5; 5 ? 7? Да | А = (6, 3, 7, 2, 8, 8, 1, 5) |
| 6; 6 ? 7? Да | А = (6, 3, 7, 2, 8, 1, 1, 5) |
| 7; 7 ? 7? Да | А = (6, 3, 7, 2, 8, 1, 5, 5) |
| 8; 8 ? 7? Нет | Конец цикла. n = 8 - 1 = 7 |
Пример 3.15. Решить предыдущую задачу, считая, что максимальных элементов может быть несколько.
Дано n - размер массива; A[n] - массив вещественных чисел.
Найти: Новый массив А размера n - k, где k - количество удаленных элементов массива.
Когда необходимо удалять несколько элементов, то это лучше делать с конца массива, так как иначе нужно будет снова возвращаться к элементу, который только что удаляли. Эта проблема возникает в том случае, когда подряд идут два максимальных элемента: если первый удалить, то на его место снова встанет максимальный элемент. Просматривать массив с конца можно при помощи цикла с параметром, который имеет следующий вид:
нц
Для i от iкон до iнач шаг -1 повторять
<тело цикла>
кц
Значение переменной i уменьшается на единицу, начиная от iкон до iнач.
Кроме того, номер максимального элемента запоминать не будем, а просмотрим массив с конца, и если текущий элемент имеет максимальное значение, то удалим его, при этом значение счетчика удаленных элементов k будем увеличивать на 1. Для решения этой задачи фрагмент алгоритма для нахождения максимального элемента выглядит так:
Amax = a[1];
нц
Для i от 2 до n повторять {Нахождение максимального элемента}
Если a[i] > Amax то Amax = a[i];
Все если
кц
Просматриваем элементы, удаляем элемент, равный максимальному значению, подсчитываем количество удаленных элементов.
|
| нц Для i от n до 1 шаг -1 повторять Если a[i] = Amax то a[i] = a[i + 1] k = k + 1 Все если кц n = n - k
|
Задачи для самостоятельного решения
1. Удалите все отрицательные элементы массива.
2. Удалите все элементы, большие данного числа А (значение числа А вводится с клавиатуры).
3. Удалите все четные элементы, стоящие на нечетных местах.
4. Удалите все повторяющиеся элементы, оставив их первые вхождения, то есть в массиве должны остаться только различные элементы.
5. Удалите последний четный элемент массива.
6. Удалите все элементы, кратные 3 или 5.
Пример 3.16. Вставить произвольное число в одномерный массив A[n] после элемента с заданным номером.
Дано: n - размер массива; A[n] - числовой вещественный массив; k - номер элемента, после которого вставляется число, равное m.
Найти новый массив A размера n + 1.
Словесное описание алгоритма.
Вставка нового элемента осуществляется следующим образом:
1) первые k элементов массива остаются без изменения;
2) все элементы, начиная с (k + 1)-го необходимо сдвинуть вправо;
3) элементу с номером (k + 1) присвоить значение m. Количество элементов массива увеличить на 1.
Рассмотрим пример. Пусть дан массив из n = 5 элементов: A(3, -12, 5, 14, 27). Надо вставить элемент со значением 10 после второго элемента массива. Мы получим массив A(3, -12, 10, 4, 14, 27). Количество элементов n = 6.
Запишем фрагмент алгоритма.
{Сдвиг элементов массива}
нц
Для i от n до k+1 шаг -1 повторять
a[i+1] = a[i]
кц
{Вставляем новый элемент}
a[k+1] = m
{Количество элементов в массиве увеличиваем}
n = n + 1
Тест
| Данные | Результат | |
| N = 5; k = 2; m=10 | A = (3, -12, 5, 14, 27) | A = (3, -12, 10, 5, 14, 27); N=6 |
Покажем, как выполняется этот алгоритм для тестового примера.
| i | Массив |
| 5; 5 ? 3? Да | A = (3, -12, 5, 14, 27, 27) |
| 4; 4 ? 3? Да | A = (3, -12, 5, 14, 14, 27) |
| 3; 3 ? 3? Да | A = (3, -12, 5, 5, 14, 27) |
| 2; 2 ? 3? Нет | Конец цикла |
|
| A[3] = 10; n = 5 + 1 = 6 |
|
| A = (3, -12, 10, 5, 14, 27) |
Пример 3.17. Вставить произвольное число в одномерный массив A[n] перед элементом с заданным номером.
Дано: n - размер массива; A[n] - числовой вещественный массив; k - номер элемента, перед которым вставляется число, равное m.
Найти: Новый массив A размера n+1.
В этой задаче, в отличие от предыдущей, мы сдвигаем все элементы с k-го и на место k-го элемента записываем новый.
Пусть задан следующий одномерный массив из n (n =10) элементов: 3, -12, 5, 14, 27, -6, 1, 34, 10, -15. Надо вставить элемент со значением 100 перед пятым элементом массива. Получим следующий массив: 3, -12, 5, 14, 100, 27, -6, 1, 34, 10, 15.
Сдвиг элементов на одну позицию вправо и вставка элемента на место k-го элемента:
нц
Для i от n до k шаг -1 повторять
a[i + 1] = a[i]
кц
a[k] = x;
Тест
| Данные | Результат | |
| N = 10; k = 5; | A = (3, -12, 5, 14, 27, -6, 1, 34, 10, -15) | A = (3, -12, 5, 14, 100, 27, -6, 1, 34, 10, 15); N=6 |
Предположим, что необходимо вставлять не один элемент, а по одному элементу после всех элементов с заданным свойством.
Пример 3.18. Вставить данное число после всех элементов массива, кратных трем.
Максимальное количество элементов, после которых может быть вставлен новый элемент, совпадает с количеством элементов массива, ведь может случиться так, что все элементы обладают заданным свойством. Поэтому массив может увеличиться максимум в два раза
Если мы будем просматривать элементы массива сначала и вставлять новый элемент после элемента с данным свойством, то номер последнего элемента каждый раз будет меняться, кроме того, придется пропускать («перепрыгивать») новый (вставленный) элемент, поэтому решение будет не эффективным.
Удобнее просматривать массив с конца, тогда вставляемый элемент мешать не будет.
Дано: n - размер массива; A[n] - вещественный массив; k - номер элемента, перед которым вставляется число, равное m.
Найти: Новый массив A размера 2n.
Фрагмент алгоритма:
|
| Количество сдвигаемых элементов k = 0.
Цикл по всем элементам массива от n-го до
Проверка деления каждого числа a[i] на 3. Если число делится на 3 без остатка, то выполняем сдвиг элементов на одну позицию вправо. n + k - это в данный момент номер последнего элемента. Во внутреннем цикле параметр цикла j меняется от n + k до i + 1 с шагом -1.
После окончания сдвига вставляем элемент на место после i-го и увеличиваем количество вставленных элементов. |
Тест
| Данные | Результат | |
| N = 5; х=10 | A = (1, -12, 5, 14, 27) | A = (1, 10, -12, 10, 5, 14, 27, 10) ; N=7 |
Покажем выполнение алгоритма для тестового примера.
| k | i | A[i] mod 3 = 0? | j | Массив после сдвига | Массив после вставки |
| 0 | 5 | 27 mod 3 = 0? Да | 5 | 1, -12, 5, 14, 27, 27 |
|
|
| 4 | 1, -12, 5, 14, 14, 27 |
| ||
|
| кц |
| 1, -12, 5, 14, 10, 27 | ||
| 1 | 4 | 14 mod 3 = 0? Нет |
|
|
|
| 3 | 5 mod 3 = 0? Нет |
|
|
| |
| 2 | -12 mod 3 = 0? Нет | 6 | 1, -12, 5, 14, 10, 27, 27 |
| |
|
| 5 | 1, -12, 5, 14, 10, 10, 27 |
| ||
|
| 4 | 1, -12, 5, 14, 14, 10, 27 |
| ||
|
| 3 | 1, -12, 5, 5, 14, 10, 27 |
| ||
|
| кц |
| 1, -12, 10, 5, 14, 10, 27 | ||
| 2 | 1 | 1 mod 3 = 0? Нет | кц |
|
|
Задачи для самостоятельного решения
1. Вставьте элемент с данным значением после первого отрицательного элемента массива.
2. Вставьте элемент с данным значением перед последним положительным элементом массива.
3. Вставьте в массив два элемента с данным значением: первый - после максимального элемента, второй - перед максимальным элементом.
4. Вставьте по одному элементу с данным значением перед всеми элементами массива, кратными заданному числу.
5. Вставьте по одному элементу с заданным значением перед всеми нулевыми элементами данного массива.
6. Дан произвольный массив. Вставьте два элемента с данными значениями: первый - после всех элементов, больших данного числа Р , а второй - перед всеми элементами, большими данного числа Р (Р вводится с клавиатуры).
7. Дан произвольный массив. Вставьте элемент со значением А перед всеми элементами, большими А, а элемент со значением В - после всех элементов, меньших В.
3.8. Алгоритмы, реализуемые
с помощью циклов с предусловием
С помощью циклов с предусловием можно запрограммировать любые повторяющиеся фрагменты алгоритмов. Но на практике цикл этого типа чаще всего используют в двух следующих случаях:
- Число повторений цикла заранее неизвестно (например, цикл до достижения требуемой точности результата, цикл до достижения числа с заданными свойствами и т.д.). Такой цикл называется циклом с прерыванием.
- Число повторений цикла заранее известно, но шаг параметра цикла не равен 1. Такой цикл называют циклом без прерываний.
Пример 3.19. Определить, является ли заданная последовательность различных чисел a1, a2, ..., an монотонно убывающей.
Пусть переменная Otvet принимает значение, равное 1, если последовательность является монотонно убывающей, и 0 - в противном случае.
Дано: n - размер массива; а[n] - числовой вещественный массив.
Найти Otvet = 1, если последовательность монотонно убывает; Otvet = 0, в противном случае.
Словесное описание алгоритма.
Присвоим переменной Otvet начальное значение, равное 1. В цикле последовательно сравниваем значения двух соседних элементов. Выход из цикла возможен в двух случаях:
- просмотрены все элементы заданной последовательности. Это означает, что условие а[i] < а[i+1] никогда не выполнялось и последовательность является монотонно убывающей. Тогда Otvet = 1.
- условие а[i] < а[i+1] выполнилось для пары соседних элементов, тогда Otvet = 0. Цикл прерывается. Следовательно, последовательность не является монотонно убывающей.
Приведем фрагмент блок-схемы и фрагмент алгоритма.
|
| i = 1 Otvet = 1 пока (I <= n) и (Otvet = 1) повторять нц Если(a[i] < a[i+1]) то Otvet = 0 Иначе i = i+1 Все если кц |
Система тестов
| № теста | Проверяемый | Данные | Результат | |
| N | Массив А | Otvet | ||
| 1 | Является | 3 | (3, 2, 1) | 1 |
| 2 | Не является | 3 | (2, 3, 1) | 0 |
Исполнение алгоритма
| № теста | i | Otvet | (i <= n) и (Otvet = 1) | A[i] < A[i+1] |
| 1 | 1 | 1 | «Да» |
|
| 2 | «Да» |
| ||
| 3 | «Нет» |
| ||
| 2 | 1 | 1 | «Да» | «Да» |
| 0 | «Нет» |
|
Пример 3.20. Вставить заданное число m в одномерный упорядоченный по возрастанию массив A[n] с сохранением упорядоченности.
Дано: n - размер массива; A[n] - числовой упорядоченный вещественный массив; число, равное m.
Найти новый упорядоченный массив A размера n + 1.
Словесное описание алгоритма.
Начинам просмотр массива с последнего элемента. Пока не просмотрены все элементы массива, ищем место нового элемента в упорядоченной последовательности, сдвигая элементы массива вправо на одну позицию. Пока не просмотрен последний элемент (i >= 1) и не найдено место нового элемента
(a[i] > m) будем переходить к следующему элементу (i = i - 1). Таким образом, мы закончим просмотр массива в одном из двух случаев: 1) найдено место нового элемента и новый элемент вставляется на это место; 2) весь массив просмотрен. Место нового элемента не найдено. Следовательно, этот элемент нужно поставить в начало массива.
|
| i = n Сдвиг элементов вправо на одну позицию пока (i >=1) и (a[i]> m) повторять нц a[i+1] = a[i] I = i-1 кц Включение числа m в последовательность a[i+1] = m
|
Система тестов
| Номер теста | Проверяемый случай | Данные | Результат | |
| m | Массив А | |||
| 1 | m ? A[i] | 0 | A = (1, 3, 5) | A = (0, 1, 3, 5) |
| 2 | A[i] < m < A[n] | 4 | A = (1, 3, 5) | A = (1, 3, 4, 5) |
| 3 | m >A[i] | 6 | A = (1, 3, 5) | A = (1, 3, 5, 6) |
Посмотрим, как исполняется алгоритм.
| № теста | i | (i >= 1) и (A[i] > m) | Массив А |
| 1 |
|
| (1, 3, 5) |
| 3 | Да | (1, 3, 5, 5) | |
| 2 | Да | (1, 3, 3, 5) | |
| 1 | Да | (1, 1, 3, 5) | |
|
| Нет | (0, 1, 3, 5) | |
| 2 |
|
| (1, 3, 5) |
| 3 | Да | (1, 3, 5, 5) | |
| 2 | Нет | (1, 3, 4, 5) | |
| 3 |
|
| (1, 3, 5) |
| 3 | Нет | (1, 3, 5, 6) |
Пример 3.21. Определить, если в одномерном массиве отрицательный элемент.
Пусть переменная Otvet = 1, если в массиве есть отрицательный элемент, и Otvet = 0 - в противном случае.
Дано: n - размер массива; A[n] - числовой вещественный массив.
Найти Otvet = 1, если отрицательный элемент есть; Otvet = 0, в противном случае.
Словесное описание алгоритма.
Начинаем просматривать массив с первого элемента (i = 1). Пока не просмотрен последний элемент (i < n) и не найден отрицательный элемент (a[i] >= 0) будем переходить к следующему элементу (i = i + 1). Таким образом, мы закончим просмотр массива в одном из двух случаев: 1) просмотрели все элементы и не нашли отрицательного, тогда i > n, а Otvet = 0; 2) нашли нужный элемент, при этом i < n и Otvet = 1.
Система тестов
| № теста | Проверяемый | Данные | Результат | |
| N | Массив А | Otvet | ||
| 1 | Есть | 3 | (3, -2, 1) | 1 |
| 2 | Нет | 3 | (2, 3, 1) | 0 |
Исполнение алгоритма
| № теста | i | Otvet | (i < n) и (Otvet = 0) | а[i] < 0 |
| 1 | 1 | 0 | Да | Нет |
| 2 | 1 | Да | Да | |
| 2 | 1 | 0 | Да | Нет |
| 2 | 0 | Да | Нет | |
| 3 | 0 | Да | Нет | |
| 4 | 0 | Нет |
|
Задачи для самостоятельного решения
1. Даны целые числа а1, а2,... Известно, что а1 > 0 и что среди а2, а3,... есть хотя бы одно отрицательное число. Пусть а1, ..., an - члены данной последовательности, предшествующие первому отрицательному члену (n заранее неизвестно). Получите:
а) max (a1,...,an);
б) min(a1 + a2, a2 + a3, ..., a n-1 + an);
в) количество нечетных чисел среди a1,..., an.
2. Найдите номер последнего отрицательного элемента массива.
3. Найдите номер первого положительного члена произвольной последовательности.
4. Найдите номер последнего нечетного члена произвольной последовательности.
5. Даны натуральное число n, действительные числа a1,..., an. В последовательности определите число соседств: а) двух положительных чисел; b) двух чисел одного знака, причем модуль первого числа должен быть больше модуля второго числа.
6. Даны целые числа с1,..., cn. Определите, имеются ли в этой последовательности два идущих подряд нулевых члена.
7. Является ли заданная последовательность целых чисел знакопеременной?
3.9. Использование вложенных циклов
Возможны случаи, когда внутри тела цикла необходимо повторить некоторую последовательность операторов, т.е. организовать внутренний цикл. Такая структура называется цикл в цикле или вложенные циклы. Глубина вложения циклов (количество вложенных друг в друга циклов) может быть различной.
Мы рассмотрим задачи, алгоритмы, решения которых используют различные комбинации вложенных циклов.
Пример 3.22. Определить, имеется ли в заданном целочисленном массиве хотя бы одна пара совпадающих по значению чисел.
Алгоритм реализуется с использованием вложенных циклов пока.
Пока <условие 1> повторять
нц
кц
При выполнении цикла для каждого значения параметра внешнего цикла, параметр внутреннего цикла пробегает все значения.
Пусть переменная Flag = 1, если пара совпадающих чисел найдена и Flag = 0, если пара совпадающих чисел не найдена.
Во внешнем цикле берем очередное число (номер числа i меняется от 1 до
n - 1)и сравниваем его с оставшимися j числами (j изменяется от i + 1 до n).
Внутренний цикл может закончиться в двух случаях:
1) пара совпадающих чисел найдена (т.е. выполнилось условие a[i] = a[j]) и тогда Flag = 1. На этом просмотр массива заканчивается.
2) совпадающие числа не найдены, при этом Flag = 0.
Система тестов
| № теста | Проверяемый | Данные | Результат | |
| n | Массив А | Otvet | ||
| 1 | Имеется | 4 | (1, 3, 2, 3) | «Есть совпадающие числа» |
| 2 | Не имеется | 3 | (1, 2, 3) | «Нет совпадающих чисел» |
Исполнение алгоритма
| № теста | i | Flag | (i?n-1) и (Flag=0) | j | (j ?n) и (Flag=0) | A[i] = A[j] | Otvet |
| 1 | 1 | 0 | Да | 2 | Да | Нет |
|
| 3 | Да | Нет |
| ||||
| 4 | Да | Нет |
| ||||
| 5 | Нет |
|
| ||||
| 2 | 1 | Да | 3 | Да | Нет |
| |
| 4 | Да | Да |
| ||||
|
| Нет |
|
| ||||
| 3 | Нет (кц) |
|
|
| «Есть» | ||
| 2 | 1 | 0 | Да | 2 | Да | Нет |
|
| 3 | Да | Нет |
| ||||
| 4 | Нет | Нет |
| ||||
| 2 | Да | 3 | Да | Нет |
| ||
| 4 | Нет | Нет |
| ||||
| 3 |
| Нет (кц) |
|
|
| «Нет» |
Пример 2.23. Упорядочить по возрастанию элементы заданного числового массива.
Мы воспользуемся простым алгоритмом: будем сравнивать попарно числа между собой и при необходимости менять их местами. Для реализации алгоритма нам необходим воженный цикл. Поскольку количество повторений циклов известно к началу их выполнения, то используем вложенный арифметический цикл «для». Схема такого цикла выглядит так:
 |
Для i от iнач до iкон; выполнить
Это не самый лучший алгоритм сортировки, но эффективность алгоритма нас в данном случае не интересует. Наша цель - продемонстрировать структуру вложенных арифметических циклов.
| Фрагмент блок-схемы алгоритма | Исполнение алгоритма |
| |||
|
| i | j | A[i] > A[j] | Массив А |
|
| 1 | 2 | Да | 2, 5, 7, 1 |
| |
|
| 3 | Нет |
|
| |
|
| 4 | Да | 1, 5, 7, 2 |
| |
| 2 | 3 | Нет |
|
| |
|
| 4 | Да | 1, 2, 7, 5 |
| |
| 3 | 4 | Да | 1, 2, 5, 7 |
| |
|
| |||||
|
| |||||
Мы видим, что при выполнении вложенного цикла типа «для» внутренний цикл выполняется полностью для всех значений параметра внешнего цикла. Общее число повторений циклов будет равно n ? (n - 1).
Задачи для самостоятельного решения
1. Дан натуральный массив А размера n. Не создавая дополнительные массивы, определите, какой из элементов повторяется в массиве наибольшее число раз, и найдите его порядковый номер, ближайший к началу последовательности.
2. Заданный массив А сдвиньте циклически на m элементов вправо. Дополнительный массив не используйте. Например, при сдвиге массива А(1, 2, 3, 4, 5, 6, 7) вправо на 3 позиции получаем массив А(5, 6, 7, 1, 2, 3, 4).
3. В заполненном наполовину массиве продублируйте все элементы с сохранением порядка их следования. Например, из массива А(1, 2, 3,...) нужно получить массив А(1, 1, 2, 2, 3, 3,...).
4. Дан массив целых чисел. Найдите в этом массиве минимальный элемент m и максимальный элемент M. Получите в порядке возрастания все целые числа из интервала (m; M).
5. Даны две последовательности: А размером n и B размером m (m < n). В каждой из них члены различны. Верно ли, что все члены второй последовательности входят в первую последовательность?
6. В массиве целых чисел найдите сумму трех минимальных чисел массива.
7. Даны два упорядоченных массива А и В. Объедините их в один упорядоченный массив. Рассмотрите два случая: когда исходные массивы упорядочены одинаково и когда - по-разному. Размеры массивов не совпадают.
8. В одномерном массиве все отрицательные элементы поместите в начало массива, а все положительные - в конец с сохранением порядка их следования. Дополнительный массив использовать не разрешается.
9. Дан массив целых чисел. Определите, если в массиве простые числа. Если да, то выведите номера этих чисел.
10. Дана последовательность целых чисел. Найдите количество различных чисел в этой последовательности.
11. Вставьте последний элемент массива после первого отрицательного элемента этого же массива.
12. Дан одномерный массив. Найдите максимальный элемент среди отрицательных элементов одномерного массива. Вставьте новый элемент с произвольным значением после максимального элемента (или после всех максимальных элементов, если их несколько).
13. Замените все отрицательные элементы массива средним значением положительных элементов этого же массива.
14. Дан одномерный массив. Найдите максимальную сумму трех идущих подряд элементов массива.
15. В заданном массиве замените нулями все отрицательные элементы, непосредственно предшествующие его максимальному элементу.
16. Вставьте в заданный упорядоченный массив новое значение с сохранением его упорядоченности.
17. Дан произвольный массив целых чисел. Удалите из массива все одинаковые значения, оставив их первые вхождения. Например, из массива (1, -3, 5, 1, 5. 4, 4, 10) должен получиться массив (1, -3, 5, 4, 10).
|
| < Предыдущая | Следующая > |
|---|