- •Предисловие
- •Основные навыки и умения
- •Логическая культура: знание логики, логическая интуиция.
- •Языковые знания и умения.
- •Поисковые знания и умения.
- •Алгоритмические навыки и умения.
- •Общие подходы к построению алгоритмов
- •Тестирование и сопровождение программ
- •Обязательный минимум содержания среднего (полного) общего образования
- •Технология обработки текстовой информации
- •Введение в информатику
- •Системы счисления
- •Перевод из десятичной системы счисления
- •Перевод в десятичную систему счисления
- •Перевод чисел из двоичной системы счисления в восьмеричную, шестнадцатеричную системы и обратно
- •Выполнение арифметических операций в позиционных системах счисления
- •Элементы математической логики
- •Логические законы
- •Алгоритм и его свойства
- •Исполнители. Компьютер - универсальный исполнитель
- •Работа компьютера
- •Turbo pascal - исполнитель паскаль-программ
- •Конструкции Паскаля
- •Типы данных
- •Целый тип данных
- •Вещественный тип данных
- •Символьный тип данных
- •Логический тип данных
- •Выражения
- •Операторы ввода-вывода
- •Оператор присваивания
- •Общий вид программы на Паскале
- •Условный оператор
- •If логическое_выражение then оператор1 else оператор2;
- •If логическое_выражение then оператор1;
- •Операторы цикла
- •Построение линейных алгоритмов
- •Построение ветвящихся алгоритмов
- •Построенние циклических алгоритмов
- •Нахождение суммы
- •Вложенные циклы
- •Переборный метод решения задач
- •Численные методы
- •Метод итераций
- •Метод половинного деления
- •Вычисление определенного интеграла методом трапеций
- •Случайные числа
- •Метод Монте-Карло (метод статистических испытаний)
- •Массивы Одномерные массивы
- •Перебор элементов массива
- •Перебор подмассивов
- •Классы задач по обработке массивов
- •Задачи первого класса
- •Задачи второго класса
- •Задачи третьего класса
- •Задачи четвертого класса
- •Сортировка массивов
- •Сортировка вставками
- •Сортировка пузырьком (обменом)
- •Сортировка выбором
- •Сортировка фон Неймана (слиянием)
- •Двумерные массивы
- •Обработка строк
- •Процедуры и функции
- •Рекурсия
- •Работа с графикой
- •Классы программного обеспечения
- •Компиляция и интерпретация
- •Текстовый редактор
- •Электронные таблицы
- •Системы управления базами данных (субд)
- •Пример решения экзаменационного билета
- •Контрольные работы
- •Контрольная работа №1
- •Контрольная работа № 2
- •Контрольная работа № 3
- •Контрольная работа № 4
- •Контрольная работа № 5
- •Библиографический список
Перебор подмассивов
Часто возникают задачи, когда для заданного элемента массива нужно перебрать оставшиеся элементы. Например, для каждого элемента перебрать все ему предшествующие или последующие элементы, перебрать элементы от заданного до первого элемента, удовлетворяющего некоторому условию. Для перебора каждого подмассива можно использовать рассмотренные ранее схемы. Это приводит к необходимости вводить такое количество индексов, каково количество обрабатываемых подмассивов. Рассмотрим примеры.
Пример 1. Для каждого элемента массива просмотрите все его последующие элементы. Здесь возможно несколько вариантов.
Вариант 1. Массив просматривается по одному элементу слева направо. Подмассив просматриваем по одному тоже слева направо.
Обозначим i - индекс массива, а j - индекс подмассива, тогда схема может быть такой:
for i:=1 to n-1 do {у последнего элемента нет последующего}
for j:=i+1 to n do
{обработка a[j]};
Вариант 2. Подмассив просматриваем справа налево.
for i:=1 to n-1 do
begin j:=n;
while j>i do
begin {обработка a[j]};
j:=j-1
end;
end;
Также могут быть использованы схемы перебора парами, соседями и т.д.
Пример 2. Для каждого элемента просмотрите все ему предшествующие. Пусть также i - индекс массива, а j - индекс подмассива.
Вариант 1. Основной массив просматривается слева направо, подмассив просматривается также слева направо.
for i:=2 to n do {у первого элемента нет предыдущего}
for j:=1 to i-1 do
{обработка a[j]};
Вариант 2. Основной массив просматривается слева направо, а подмассив - справа налево.
for i:=2 to n do
begin j:=i-1;
while j>0 do
begin {обработка a[j]};
j:=j-1
end;
end;
Вариант 3. Основной массив просматривается справа налево, а подмассив - слева направо.
i:=n;
while i>1 do
begin for j:=1 to i-1 do {обработка a[j]};
i:=i-1
end;
Вариант 4. Основной массив просматривается справа налево и подмассив - справа налево.
i:=n;
while i>1 do
begin j:=i-1;
while j>0 do
begin {обработка a[j]};
j:=j-1
end;
i:=i-1
end;
Классы задач по обработке массивов
Перечисленные ниже классы задач относятся как к одномерным, так и к двумерным массивам.
Классы задач:
1) однотипная обработка всех или указанных элементов массива;
2) задачи, в результате решений которых изменяется структура (порядок следования элементов) массива;
3) обработка нескольких массивов одновременно. Сюда же относятся задачи, когда по-разному обрабатываются подмассивы одного и того же массива;
4) поисковые задачи для массивов.
Задачи первого класса
Решение задач первого класса сводится к установлению того, как обрабатывается каждый элемент массива или указанные элементы. Затем выбирается подходящая схема перебора элементов, в которую вставляются операторы обработки элементов массива.
Пример 1. Найдите среднее арифметическое элементов массива.
Решение. Задача сводится к отысканию суммы, для чего вводится дополнительная переменная S, в которой накапливается сумма путем прибавления очередного элемента массива, т.е. S := S + a[i]. При этом можно использовать любую линейную схему перебора с единичным шагом. После нахождения суммы необходимо ее поделить на количество элементов, получим среднее арифметическое.
const nn = 30;
var a: array [1..nn] of integer;
i, n, S: integer;
begin
write (‘задайте количество элементов массива’);
readln (n);
for i := 1 to n do
read (a[i]);
S := 0;
for i := 1 to n do
S := S + a[i];
write (‘среднее арифметическое равно ’, S/n)
end.
Пример 2. Определите количество четных элементов массива с нечетными порядковыми номерами.
Решение. Сначала надо определить условие, по которому будут отбираться элементы массива. Это должны быть четные элементы (делятся на 2 без остатка) a[i] mod 2 = 0 и имеющие нечетные порядковые номера (номер элемента совпадает с его индексом) i mod 2<>0. Поскольку нас интересуют элементы, удовлетворяющие обоим условиям, соединены эти условия будут оператором and. Выполнение этого условия должно проверяться для всех элементов массива, т.е. используется любая из схем перебора по одному, и в случае выполнения условия счетчик элементов должен увеличиваться на 1.
const nn = 30;
var a: array [1..nn] of integer;
i, n, S: integer; {S - счетчик элементов}
begin
write (‘задайте количество элементов массива’);
readln (n);
for i := 1 to n do
read (a[i]);
S := 0;
for i := 1 to n do
if (a[i] mod 2 = 0) and (i mod 2 <> 0) then S := S +1;
writeln (‘S= ‘, S)
end.
Пример 3. Найдите максимальный (минимальный) элемент массива.
Решение этой задачи можно организовать, используя алгоритм, предложенный при изучении циклов, а именно: считаем кандидатом на максимальный (минимальный) первый элемент массива, затем в цикле сравниваем очередной элемент массива с кандидатом на максимальный (минимальный), если очередной элемент больше (меньше) кандидата, то меняем значение кандидата на значение данного элемента массива.
const n = 30;
var a: array [1..n] of integer;
i, max: integer;
begin
for i := 1 to n do
read (a[i]);
max := a[1];
for i := 2 to n do
if a[i] > max then max := a[i];
writeln (‘максимальный элемент массива равен ’, max)
end.
Во втором варианте решения этой задачи запоминается не значение максимального элемента, а его порядковый номер (индекс), по которому элемент однозначно определяется, а значит, можно будет определить и величину максимального элемента.
const n = 30;
var a: array [1..n] of integer;
i, imax: integer;
begin
for i := 1 to n do
read (a[i]);
imax := 1;
for i := 2 to n do
if a[i] > a[imax] then imax := i;
writeln (i:2,‘-ый элемент массива - максимальный, его величина равна ’, a[imax]);
end.
Упражнения.
1. Установите, какую задачу решает приведенный ниже фрагмент программы. Перепишите его с использованием оператора while.
s := 1; max := a[1];
for i := n downto 2 do
if max < a[i]
then begin max := a[i]; s := 1 end
else if max = a[i]
then s := s + 1;
2. В городе N закусочных. Известны расстояния от каждой закусочной до цетра города. Нужно указать пару закусочных, расположенных дальше всего друг от друга, если переходы от закусочной к закусочной осуществляются через центр.
3. Последовательность определяется по следующим правилам: a0 = 9;
ak+1 = 3ak4 + 4ak3 для любого k > 0. Заданы номера элементов этой последовательности i и j. Определите в записи какого элемента входит больше цифр девять.
4. В одномерном массиве целых чисел найдите максимальный среди элементов, являющихся четными, и минимальный среди элементов, кратных А.
5. Автомат, приклеивающий этикетки, работает со светлыми, зелеными и темными бутылками, в которые наливаются светлые и темные жидкости. Темные бутылки с темной жидкостью автомат разбивает. Сколько бутылок из 1997 штук разобьет автомат? Вид бутылки и жидкости в ней задается случайным числом.
6. В массиве хранятся натуральные числа из интервала от 10 до 50, сформированные случайным образом. Выведите его на экран построчно, где каждая строка содержит столько звездочек, каково значение соответствующего элемента массива.
7. В одномерном массиве хранятся случайные натуральные числа от -10 до 37. Напечатайте содержимое соответствующего элемента массива в виде столбца звездочек вверх (в случае положительного элемента) или вниз (в случае отрицательного элемента) от базовой строки. Например, для А = {-2, 3, 2, -3, 4, -2} получим:
|
1 |
2 |
3 |
4 |
5 |
6 |
начало листа |
|
|
|
|
* |
|
|
|
* |
|
|
* |
|
|
|
* |
* |
|
* |
|
|
|
* |
* |
|
* |
|
базовая точка |
- |
- |
- |
- |
- |
- |
|
* |
|
|
* |
|
* |
|
* |
|
|
* |
|
* |
|
|
|
|
* |
|
|