Циклический сдвиг элементов массива вправо (влево) на М позиций
При решении задач, в которых необходимо вставить элемент в массив используется циклический сдвиг элементов. В этом алгоритме сначала запоминаем последний элемент, если сдвиг будем делать вправо (первый элемент, если сдвиг влево). Затем сдвигаем элементы, т.е. на n место ставим n-1 элемент, на n-1 ставим n-2, и т.д. на 2-е место ставим 1-й элемент, тем самым как бы освободив первую позицию. Наконец, на первое место записываем последний элемент, который хранится во вспомогательной переменной. Подобные действия повторяются m раз, т.е. число раз, на которое необходимо осуществить сдвиг. Мы рассмотрели циклический сдвиг на m позиций вправо.
Реализация:
{Циклический сдвиг на m позиций вправо}
writeln(‘ Введите число сдвигов’);
readln( m);
for i:=1 to m do
begin
{Запоминаем последний элемент массива}
temp:=a[n];
{Сдвиг элементов массива на одну позицию вправо}
for j:= n downto 2 do a[j]:=a[j-1];
a[1]:= temp
end;
{Печать измененного массива}
for i:=1 to n do writeln(‘a[‘, i, ‘]= ’, a[i]);
Сортировка массива
Df: Под сортировкой будем понимать процесс перестановки объектов заданного массива в определенном порядке. Сортировка выбором. Этот метод основан на поиске элемента. Выбирается элемент с наименьшим ключом и меняется местами с первым элементом. Затем выбирается элемент с наименьшим ключом среди оставшихся n-1 элементов и меняется местами со вторым и т.д. Алгоритм сортировки основан на типовом алгоритме поиска минимума (максимума).
|
|
|
Реализация:
{Сортировка массива по возрастанию методом выбора}
for i:=1 to n-1 do
begin
{ Поиск минимального элемента в части массива от a[i] до a[n]}
n_min:=i;
for j:=i+1 to n do
if a[j]<a[n_min] then n_min:=j;
{ Поменяем местами a[n_min] и a[i] }
temp:=a[i];
a[i]:=a[n_min];
a[n_min]:=temp
end;
{Выведем отсортированный массив}
for i:=1 to n do write(a[i],' ');
Образцы решения задач.
Задача № 1. Задан массив вещественных значений. Найти количество элементов в массиве больших среднего.
Анализ постановки задачи.
Для решения данной задачи необходимо использовать типовые алгоритмы: суммирование элементов массива и подсчет количества элементов массива по ключу.
Входные данные.
Массив вещественных элементов – tp.
Выходные данные.
Количество элементов массива больших среднего – kol_vo (тип - целый).
Промежуточные данные.
Среднее значение элементов массива – sred (тип - вещественный).
Алгоритм.
1. Ввод элементов массива.
2. Найти среднее значение:
§ суммировать все элементы;
§ сумму разделить на количество элементов в массиве.
3. Найти количество элементов в массиве больше среднего.
|
|
|
4. Вывод результата на печать.
Функциональная структура алгоритма
Текст программы
const n=30;
type temp= array[1..n] of real;
var tp : temp;
sred : real;
kol_vo : word;
procedure vvod(var a:temp);
var i : integer;
Begin
for i:=1 to n do {ввод элементов массива}
readln(a[i]);
end;
function summ(var a:temp): real;
var i : integer;
s : real;
Begin
s:=0; {обнуление счетчика}
for i:=1 to n do {суммирование элементов массива}
s:=s+a[i];
summ:=s;
end;
function koll(var a:temp; sr:real):word;
var i : integer;
k : word;
Begin
k:=0; {обнуление счетчика}
for i:=1 to n do {подсчет кол-ва элементов массива > среднего}
if a[i]>sr then k:=k+1;
koll:=k;
end;
Begin
vvod(tp);
sred:=summ(tp)/n;
kol_vo:=koll(tp, sred);
writeln(‘kol= ‘, kol_vo);
end.
Задача № 2. Одномерный массив длиной N<=40 заполнить случайными числами из диапазона [–25..10]. Составить программу определения минимального из элементов, значения которых лежат в диапазоне [х..y].
Анализ постановки задачи.
Для решения данной задачи необходимо использовать типовые алгоритмы: поиск элемента в массиве по ключу (ключ – диапазон [х..y]); поиск минимального элемента в массиве с учетом того, что минимальный должен находиться в диапазоне [х..y].
|
|
|
Входные данные.
Массив целых элементов – tp.
Границы диапазона – x, y (тип - целый).
Выходные данные.
Минимальный элемент в массиве – min (тип - целый).
Промежуточные данные.
Индекс самого первого элемента массива находящегося в диапазоне [х..y] – ind (тип - целый).
Алгоритм.
1. Заполнение массива случайными числами из заданного диапазона.
2. Нахождение первого элемента массива из заданного диапазона.
3. Поиск минимального элемента массива из заданного диапазона.
4. Вывод результата на печать.
Функциональная структура алгоритма
Текст программы
const n=40;
type temp= array[1..n] of integer;
var tp : temp;
x, y, min : integer;
ind : byte;
procedure vvod(var a:temp);
var i : byte;
Begin
randomize;
for i:=1 to n do {заполнение массива случайным числами}
a[i]:=random(36)-25;
end;
procedure poisk (var a : temp; x1, y1: integer; var ind1: byte);
var i : byte;
flag : boolean;
Begin
i:=1;
flag:=true; { поиск самого первого элемента массива входящего в диапазон x..y}
|
|
|
while flag and (i<=n) do
if (a[i]>=x1) and (a[i]<=y1) then flag:=false
else i:=i+1;
ind1:=i;
end;
procedure minum(var a : temp; x1, y1: integer; ind1: byte; var min1: integer);
var i : byte;
Begin
min1:=a[ind1]; {поиск минимального из заданного диапазона }
for i:= ind1+1 to n do
if (a[i]>=x1) and (a[i]<=y1) and (a[i]<min) then min1:=a[i];
end;
Begin
vvod(tp);
writeln(‘введите диапазон x..y ‘);
readln(x, y);
poisk(tp, x, y, ind);
minum(tp, x, y, ind, min);
writeln(‘min= ‘, min);
end.
Задания для самостоятельного решения.
Вариант 1.
1. Одномерный массив А длиной N<=20 заполнить случайными числами из диапазона [–10..55]. Составить программу определения:
· первого максимального элемента массива;
· количество максимальных элементов в массиве;
· всех элементов, кратных 3-м или 5-и.
2. Дан одномерный массив. Переместить нулевые элементы массива в конец, сдвинув остальные элементы влево.
3. Имеются сведения о количестве проданных билетов в 17-ти вагонах поезда. Найти наименее загруженный вагон, учитывая, что количество мест в вагоне зависит от типа вагона: в мягком и купейном вагонах — по 36 мест, а в плацкартном — 46 мест.
Вариант 2.
1. Одномерный массив А длиной N<=50 заполнить случайными числами из диапазона [–5..30]. Составить программу определения:
· последнего максимального элемента;
· на каких позициях находятся максимальные элементы;
· сколько элементов массива превосходят по модулю заданное число M?
2. Дан одномерный массив. Переместить нулевые элементы массива в начало, сдвинув остальные элементы вправо.
3. Даны сведения о двухстах абитуриентах: фамилии и оценки, полученные на трех вступительных экзаменах. Напечатать список будущих студентов при условии, что норма приема — 40 человек, а зачисляются абитуриенты, набравшие наибольшую сумму баллов.
Вариант 3.
1. Одномерный массив А длиной N<=30 заполнить случайными числами из диапазона [-10..60]. Составить программу определения:
· последнего минимального элемента;
· на каких позициях находятся минимальные элементы;
· есть ли в данном массиве два соседних положительных элемента? Найти номера первой пары.
2. Дан одномерный массив. Переместить минимальные элементы в начало, сдвинув остальные элементы вправо.
3. Известно количество денег у каждого из N учеников, а также стоимость 4 комплексных обедов в школьной столовой. Напечатать сколько каких обедов будет куплено и сколько учеников останутся голодными, если каждый ученик выбирает наиболее дорогой обед, который он может купить.
Вариант 4.
1. Одномерный массив А длиной N<=20 заполнить случайными числами из диапазона [–15..80]. Составить программу определения:
· первого минимального элемента массива;
· количества и суммы минимальных элементов;
· есть ли в данном массиве два соседних отрицательных элемента? Найти номера последней пары.
2. Дан одномерный массив. Переместить максимальные элементы в конец, сдвинув остальные элементы влево.
3. Имеются сведения о 40-и регионах страны: название региона и информация об уровне безработицы в регионе. Определите три наиболее благополучных и три неблагополучных района.
Вариант 5.
1. Одномерный массив А длиной N<=20 заполнить случайными числами из диапазона [–15..-5]. Составить программу определения:
· суммы положительных элементов массива;
· количества четных элементов массива;
· минимального из элементов, значения которых лежат в диапазоне [y1..y2].
2. Дан одномерный массив. Переместить максимальные элементы в начало, сдвинув остальные элементы вправо.
3. Имеется информация о 100 предприятиях города в виде: название предприятия, число работающих, прибыль. Определить предприятие с максимальной прибылью с учетом количества работающих на нем людей.
Вариант 6.
1. Одномерный массив А длиной N<=50 заполнить случайными числами из диапазона [–15..20]. Составить программу определения:
· первого отрицательного элемента массива;
· суммы четных элементов массива.
· количества элементов, значения которых лежат в диапазоне [y1..y2].
2. Дан одномерный массив. Переместить минимальные элементы в конец, сдвинув остальные элементы влево.
3. Имеются сведения об обеспеченности жильем N работников предприятия: фамилия работника, количество человек в семье, количество кв. метров жилой площади. Также известно количество K новых квартир, которые получает предприятие. Требуется отпечатать список K работников, претендующих на новое жилье, полагая, что у всех работников разное количество кв. метров на человека.
Вариант 7.
1. Одномерный массив А длиной N<=40 заполнить случайными числами из диапазона [–25..10]. Составить программу определения:
· первого четного элемента массива;
· суммы элементов массива значения, которых лежат в диапазоне [y1..y2];
· количества элементов массива больших заданного значения M.
2. Дан одномерный массив. Переместить четные элементы в конец, сдвинув остальные элементы влево.
3. В конкурсе «Мисс Очаровашка» участвуют 100 девушек. Известен балл, набранный каждой девушкой в ходе первого тура конкурса. Определить десять девушек вышедших во второй тур конкурса.
Вариант 8.
1. Одномерный массив А длиной N<=25 заполнить случайными числами из диапазона [–18..10]. Составить программу определения:
· первого положительного элемента массива;
· максимального среди четных элементов массива;
· количества отрицательных элементов массива значения, которых лежат в диапазоне [y1..y2].
2. Дан одномерный массив. Переместить нечетные элементы в начало, сдвинув остальные элементы вправо.
3. Известно количество голосов, поданных за каждого из 10 кандидатов на пост мэра Челябинска. Выяснить, избран ли мэр, если для избрания требуется набрать более 50 % голосов “за” или какие два кандидата вошли во второй тур (если никто из кандидатов не набрал 50 % голосов).
Вариант 9.
1. Одномерный массив А длиной N<=55 заполнить случайными числами из диапазона [–30..30]. Составить программу:
· определить первый элемент массива кратный 5-и;
· найти среднее значение максимального и минимального элементов массива;
· заменить первые k элементов на противоположные по знаку.
2. Дан одномерный массив. Переместить положительные элементы в конец, сдвинув остальные элементы влево.
3. Известна балансовая стоимость 100 станков завода. Определить десять станков с максимальной балансовой стоимостью, а также вычислить амортизационные отчисления завода, если за каждый станок они составляют 10% его стоимости.
Вариант 10.
1. Одномерный массив А длиной N<=40 заполнить случайными числами из диапазона [–20..50]. Составить программу:
· определить последний положительный элемент массива кратный 3-м;
· заменить максимальный по модулю отрицательный элемент нулем;
· найти все индексы отрицательных элементов массива.
2. Дан одномерный массив. Переместить отрицательные элементы в начало, сдвинув остальные элементы вправо.
3. Руководство ведет каждый месяцам учет расходов фирмы. Получена информация за n месяцев. Расставить данные по расходам в порядке в их возрастания.
Отчет должен содержать:
· Математическую или логическую модель задачи.
· Функциональную структуру алгоритма.
· Программный код задачи.
· Тесты для проверки правильности работы программного кода.
Контрольные вопросы:
1. Дайте определение понятию массив.
2. Назовите и охарактеризуйте свойства массива.
3. Какие типы массивов существуют, и чем они отличаются друг от друга?
4. Что такое логическое и физическое представление массива?
5. Как осуществляется доступ к элементу одномерного массива?
6. Опишите одномерный массив, состоящий из 30 элементов целого типа.
7. Дан массив целых чисел {Xi}=1, 2, -9, 0, -34, 7. Чему будет равно значение k=_____________?
k:=0;
for i:=1 to n do
if (X[i]>0) then k:=k+1;
8. Если элементы массива D[1..7] равны соответственно 4, 0, 7, 5, 6, 2, 4 то значение выражения D[ D[1] ] + D[ D[3] ] равно ...
9. Определите, что будет результатом выполнения фрагмента программы:
k:=1;
for i:=1 to 10 do
if A[i]> A[k] then k:=i;
10. Определите, что будет результатом выполнения фрагмента программы:
s:=0;
for i:=1 to 10 do
if A[i]>s then s:=A[i];
Дата добавления: 2021-03-18; просмотров: 155; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!