Образцы решения задач.
Задача № 1. Задан массив дробных чисел. Найти количество элементов в массиве больших среднего значения элементов массива.
Постановка задачи.
Для решения данной задачи необходимо использовать типовые алгоритмы: суммирование элементов массива и подсчет количества элементов массива по заданному ключу (среднее значение элементов массива).
Входные данные.
<Всего> элементов в массиве – n (постоянное значение целого типа).
<Массив> значений дробного типа – A (тип – tAr).
Выходные данные.
<Количество> элементов массива больших среднего – kolvo (целое).
Промежуточные данные.
<Среднее> значение элементов массива – sred (всегда дробное).
Алгоритм.
1. Ввод элементов массива.
2. Найти <Среднее> значение элементов массива:
§ Найти <Сумму> элементов массива;
§ <Сумму> разделить на <Всего> элементов в массиве.
3. Найти <Количество> элементов в массиве больше среднего.
4. Вывод <Количество> на печать.
Функциональная структура алгоритма
Текст программы.
Const
n=30; // всего элементов в массиве
Type
tAr= array[1..n] of real; // тип массив из n элементов типа real
Var
A: tAr; // массив значений
sred: real; // среднее значение элементов массива
kolvo: integer; // количество элементов больших среднего значения
procedure vvod(var A: tAr);
{ввод элементов массива
A – формальный параметр типа tAr, водимый массив (не следует путать с глобальной
переменной A: tAr, описанной выше)
}
Var
i: integer;
Begin
for i:=1 to n do
readln(a[i]);
end;
function summ(A: tAr): real;
{алгоритм нахождения суммы элементов массива
A – массив из n значений дробного типа
Возвращаемое значение – сумма всех элементов массива A
}
Var
i: integer; // счетчик цикла
s: real; // сумма значений
Begin
s:=0; // сначала сумма равна 0
for i:=1 to n do // для каждого i от 1 до n (для каждого элемента)
s:=s+A[i]; // добавим i-й элемент к сумме
summ:=s; // возвращаем сумму элементов
end;
function koll(A: tAr; Key: real): integer;
{алгоритм нахождения количества элементов массива удовлетворяющих условию
A – массив из n значений дробного типа
Key – ключ для поиска значения
Возвращаемое значение – количество элементов массива A, больших указанного ключа
}
Var
i, // счетчик цикла
kol // количество элементов, удовлетворяющих условию
: integer;
Begin
kol:=0; // сначала 0
for i:=1 to n do //подсчет кол-ва элементов массива > среднего
if A[i]>Key then // i-й элемент больше ключа
kol:=kol+1; // учли найденный элемент
koll:=kol; // вернули количество найденных элементов
end;
Begin
vvod(A);
sred:=summ(A)/n; // нашли сумму элементов массива A и разделили её на количество элементов
kolvo:=koll(A, sred); // нашли количество элементов массива A больших значения sred
WriteLn(’Количество элементов больших ’, sred, ’ равно ’, kolvo);
end.
Задача № 2. Одномерный массив длиной N=40 элементов заполнить случайными числами из диапазона [–25..10]. Составить программу определения минимального из элементов, значения которых лежат в диапазоне [Mn..Mx].
Постановка задачи.
Для решения данной задачи необходимо использовать типовые алгоритмы: поиск элемента в массиве по ключу (диапазон [Mn..Mx]); поиск минимального элемента в массиве, который должен находиться в диапазоне [Mn..Mx].
Входные данные.
<Всего> элементов в массиве – N (постоянное значение целого типа)
Границы допустимых значений элементов массива (постоянные значения):
<Минимум> значение Low (тип - целое)
<Максимум> значение High (тип - целое)
<Массив> целых элементов – A (тип – tAr).
Ключ для поиска:
<Нижнее> значение Mn (тип - целое).
<Верхнее> значение Mx (тип - целое).
Выходные данные.
Минимальный <Элемент> в массиве – min (тип - целое).
Промежуточные данные.
<Номер> первого элемента массива из диапазона – ind (тип - целое).
Алгоритм.
1. Заполнение <Массива> случайными числами из заданного диапазона [<Минимум>..<Максимум>].
2. Нахождение <Номера> первого элемента массива, соответствующего ключу.
3. Поиск <Элемента> массива из заданного диапазона.
4. Вывод <Элемента> на печать.
Функциональная структура алгоритма
Текст программы.
Сonst
Low=-25; //минимум
High=10; // максимум
n=40; // всего
Type
tAr= array [1..n] of integer; // структура данных – массив из n значений целого типа
Var
A: tAr;
Mn, Mx, min: integer;
ind: integer;
procedure vvod(var A: tAr; L, H: integer);
{алгоритм заполнение массива случайным числами из диапазона [L..H]
A – заполняемый массив
L – минимальное значение элементов массива
H – максимальное значение элементов массива
}
Var
i: integer;
Begin
randomize; // инициализируем генератор случайных чисел
for i:=1 to n do // для каждого элемента
A[i]:=random(abs(L)+abs(H)+1)-L; // генерируем случайное значение и заносим его в элемент
end;
function FirstElement(A: tAr; Min, Max: integer): integer;
{ поиск первого элемента массива входящего в диапазон Min..Max
A – заданный массив
Min – нижняя граница диапазона
Max – верхняя граница диапазона
Возвращаемое значение – номер самого первого элемента или -1, если такого элемента нет
}
Var
i, // счетчик цикла (номер обрабатываемого элемента массива)
First // номер элемента
: integer;
Begin
First:=-1;
for i:=1 to n do
if (A[i]>=Min)and(A[i]<=Max) then // i-й элемент лежит в диапазоне
First:=i; // нашли соответствующий элемент
break // прервали выполнение цикла
End
poisk:=First; // указали возвращаемое значение
end;
functionMinimum(A: tAr; Min, Max, First: integer): integer;
{ поиск минимального элемента входящего в диапазон Min..Max начиная с заданного
A – заданный массив
Min – нижняя граница диапазона
Max – верхняя граница диапазона
First – номер первого элемента, соответствующего ключу
Возвращаемое значение – минимальный элемент из заданного диапазона
}
Var
i: integer; // счетчик цикла (номер элемента массива)
min: integer; // значение минимального элемента
Begin
min:=A[First]; // за минимальный принимаем первый
for i:= First +1 to n do // для каждого элемента
if (A[i]>=Min)and(A[i]<=Max)and// элемент принадлежит диапазону
(A[i]<min) then // элемент меньше ранее найденного значения
min:=A[i]; // запомнили минимальный элемент
Minimum:=min
end;
begin{головной модуль}
// ввод исходных данных
vvod(A, Low, High); // заполнили массив
Write(’Введите диапазон Min и Max ’);
ReadLn(Mn, Mx); // ввели границы диапазона
// обработка
ind:=FirstElement(A, Mn, Mx); // нашли первый элемент
min:=Minimum(A, Mn, Mx, ind); // нашли минимальных элемент
// вывод результатов
WriteLn(’Минимальное значение равно ’, 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];