§13. Вложенные циклы
Для решения задачи достаточно часто требуется использовать две и более циклические конструкции, одна из которых расположена внутри другой (других). Такие конструкции называют вложенными циклами. Какие именно циклы при этом используются, роли не играет, они могут быть организованы посредством любых рассмотренных ранее операторов (For, While, Repeat ... Until).
Задача : Сколько можно купить быков, коров и телят, если бык стоит 10 рублей, корова - 5 рублей, теленок - полтинник (0,5 рубля), при условии, что на 100 рублей надо купить 100 голов скота.
Решение : Обозначим через b- количество быков, k - количество коров, t - количество телят. После этого можно записать два уравнения:
10b+5k+0,5t=100 и b+k+t=100
Преобразуем их :
20b+10k+t=200 и b+k+t=100
На 100 рублей можно купить :
не более 10 быков, т.е. 0<=b<=10;
не более 20 коров, т.е. 0<=k<=20;
не более 200 телят, т.е. 0<=t<=200;
Таким образом получаем :
Program skot;
Var b,k,t : integer;
Begin
For b:=0 to 10 do
For k:=0 to 20 do
For t:=0 to 200 do
if (20*b+10*k+t=200) and (b+k+t=100) then
writeln(‘быков ‘,b,‘ коров ’,k,’ телят ’,t);
end.
Условие будет проверятся 11*21*201=46431 раз. Но задачу можно сократить на один цикл если количество телят вычислять по формуле :
t=100-(b+k)
§14. Одномерные массивы Работа с элементами
Одномерный массив - это фиксированное количество элементов одного типа, объединенных одним именем. Каждый элемент имеет свой номер- индекс. Обращение к элементам массива осуществляется с помощью указания имени массива и номера элементов.
Пусть для решения требуется массив из 30 целых чисел.
Var mas: array [1..30] of integer;
Способы задания значений элементов массива
Оператор присваивания.
А[1]:=3;
А[2]:=4;
........
или
B[1]:=’Иванов’;
B[2]:=’Петров’;
........
Такой способ задания значений используется, если массив небольшой.
2) Оператором ввода с клавиатуры.
For i:=1 to 10 do
begin
Writeln(‘введите ’,i,’-ый элемент массива’);
Readln(a[i]);
{в качестве индекса используется параметр цикла }
end;
Этот способ задания значений также используется для небольших массивов.
3) Заполнение массива с использованием генератора случайных чисел.
.......
RANDOMIZE;
For i:=1 to 10 do
a[i]:=Random(x);
…....
{массив заполнится целыми числами в диапазоне от 0 до Х}
4) Заполнение по формуле.
Каждый элемент массива должен быть рассчитан по формуле (например ai=sin i - cos i)
for i:=1 to 10 do
a[i]:=sin(i)-cos(i);
Вывод массива.
For i:=1 to 10 do writeln(a[i]);
Вывод пятого элемента массива записывается так : write(a[5]);
Алгоритмы работы с массивами
1) Сумма элементов массива.
Program symma;
var a: array [1..10] of integer;
i, s : integer;
begin
s:=0;
for i:=1 to 10 do
begin
readln(a[i]);
s:=s+a[i];
end;
writeln (‘Сумма= ’,s);
еnd.
2) Сумма положительных чисел.
Program symma2;
var a: array [1..10] of integer;
i, s : integer;
begin
s:=0;
for i:=1 to 10 do
begin
readln(a[i]);
if a[i]>0 then s:=s+a[i];
end;
writeln (‘Сумма положительных чисел = ’,s);
еnd.
3) Сумма и количество положительных чисел.
Program symma-kol;
var a: array [1..10] of integer;
i, s,k : integer;
begin
s:=0; k:=0;
for i:=1 to 10 do
if a[i]>0 then begin k:=k+1; s:=s+a[i]; end;
writeln (‘Сумма ’,s, ‘ количество’, k);
еnd.
4) Поиск заданного элемента в массиве.
Найти элементы массива большие числа 5.
Program elem;
var a: array [1..10] of integer;
i : integer;
begin
for i:=1 to 10 do
if a[i]>5 then writeln(a[i]);
еnd.
5) Поиск наибольшего (наименьшего) элемента в массиве.
Program mm;
var a: array [1..10] of integer;
i, max, min : integer;
begin
for i:=1 to 10 do readln(a[i]);
max:=a[1]; min:=a[1];
for i:=1 to 10 do
begin
if a[i]>max Then max:=a[i];
if a[i]<min Then min:=a[i];
end;
writeln (‘ max=’,max,’ min=’, min);
еnd.
6) Упорядочение массива
Упорядочение (сортировка) - это расположение значений элементов массива в порядке возрастания или убывания их значений.
Сортировка простым выбором.
Рассмотрим идею этого метода на примере. Пусть исходный массив А состоит из 10 элементов : 5 13 7 9 1 8 16 4 10 2.
После сортировки массив : 1 2 4 5 7 8 9 10 13 16
Максимальный элемент текущей части массива заключен в кружок, а элемент, с которым происходит обмен, в квадратик. Скобкой помечена рассматриваемая часть массива.
5
13 7 9 1 8 16 4 10 2
5
13 7 9 1 8 2 4 10 16
2 шаг. Рассмотрим часть массива, исключая последний элемент. Максимальный элемент этой части - 13, он стоит на втором месте. Поменяем его местами с последним элементом этой части - с числом 10.
И т.д.
Фрагмент программы :
for i:=n downto 2 do
begin {цикл по длине рассматриваемой части массива}
maxi:=i;
for j:=1 to i-1 do if a[j]>a[maxi] then maxi:=j;
if maxi<>i then begin {перестановка элементов}
k:=a[i]; a[i]:=a[maxi]; a[maxi]:=k
end;
end;
«Пузырьковый метод»
Массив просматривают слева направо. Каждый предыдущий элемент сравнивается с последующим. Если предыдущий элемент больше последующего, то предыдущий и последующий элементы меняются местами.
Program sort1;
const n=10;
label metka;
var a: array [1..n] of integer;
i, c, k : integer;
begin
for i:=1 to n do readln(a[i]);
metka: k=0; {счетчик перестанокок}
for i:=1 to n-1 do
if a[i]>a[i+1] then begin c:=a[i];
a[i]:=a[i+1];
a[i+1]:=c;
k:=1;
end;
if k=1 then goto metka
else writeln(‘упорядочен‘);
for i:=1 to n do writeln(a[i]);
еnd.
Тоже самое, но с использованием вложенных циклов
Program sort2;
const n=10;
var a: array [1..n] of integer;
i, k, c : integer;
begin
for i:=1 to n do readln(a[i]);
for i:=1 to n-1 do
for k:=1 to n-i do
if a[k]>a[k+1] then begin c:=a[k];
a[k]:=a[k+1];
a[k+1]:=c;
end;
for i:=1 to n do writeln(a[i]);
еnd.