- •Предисловие
- •Основные навыки и умения
- •Логическая культура: знание логики, логическая интуиция.
- •Языковые знания и умения.
- •Поисковые знания и умения.
- •Алгоритмические навыки и умения.
- •Общие подходы к построению алгоритмов
- •Тестирование и сопровождение программ
- •Обязательный минимум содержания среднего (полного) общего образования
- •Технология обработки текстовой информации
- •Введение в информатику
- •Системы счисления
- •Перевод из десятичной системы счисления
- •Перевод в десятичную систему счисления
- •Перевод чисел из двоичной системы счисления в восьмеричную, шестнадцатеричную системы и обратно
- •Выполнение арифметических операций в позиционных системах счисления
- •Элементы математической логики
- •Логические законы
- •Алгоритм и его свойства
- •Исполнители. Компьютер - универсальный исполнитель
- •Работа компьютера
- •Turbo pascal - исполнитель паскаль-программ
- •Конструкции Паскаля
- •Типы данных
- •Целый тип данных
- •Вещественный тип данных
- •Символьный тип данных
- •Логический тип данных
- •Выражения
- •Операторы ввода-вывода
- •Оператор присваивания
- •Общий вид программы на Паскале
- •Условный оператор
- •If логическое_выражение then оператор1 else оператор2;
- •If логическое_выражение then оператор1;
- •Операторы цикла
- •Построение линейных алгоритмов
- •Построение ветвящихся алгоритмов
- •Построенние циклических алгоритмов
- •Нахождение суммы
- •Вложенные циклы
- •Переборный метод решения задач
- •Численные методы
- •Метод итераций
- •Метод половинного деления
- •Вычисление определенного интеграла методом трапеций
- •Случайные числа
- •Метод Монте-Карло (метод статистических испытаний)
- •Массивы Одномерные массивы
- •Перебор элементов массива
- •Перебор подмассивов
- •Классы задач по обработке массивов
- •Задачи первого класса
- •Задачи второго класса
- •Задачи третьего класса
- •Задачи четвертого класса
- •Сортировка массивов
- •Сортировка вставками
- •Сортировка пузырьком (обменом)
- •Сортировка выбором
- •Сортировка фон Неймана (слиянием)
- •Двумерные массивы
- •Обработка строк
- •Процедуры и функции
- •Рекурсия
- •Работа с графикой
- •Классы программного обеспечения
- •Компиляция и интерпретация
- •Текстовый редактор
- •Электронные таблицы
- •Системы управления базами данных (субд)
- •Пример решения экзаменационного билета
- •Контрольные работы
- •Контрольная работа №1
- •Контрольная работа № 2
- •Контрольная работа № 3
- •Контрольная работа № 4
- •Контрольная работа № 5
- •Библиографический список
Перебор элементов массива
Элементы массива можно обрабатывать, двигаясь от начала массива к его концу или в обратном направлении:
for i := 1 to n do for i := n downto 1 do
{обработка a[i]}; {обработка a[i]};
Можно обрабатывать сразу по два элемента, двигаясь одновременно с обеих сторон:
i := 1; {задание нижней границы индекса}
j := n; {задание верхней границы индекса}
while i <= j do
begin
{обработка a[i] и a[j]};
i := i + 1; {движение слева направо, индекс увеличивается}
j := j - 1 {движение справа налево, индекс уменьшается}
end;
Можно задавать различные линейные схемы перебора элементов массива (с постоянным шагом).
Если необходимо перебирать только четные элементы массива, то это может быть реализовано следующим образом:
Вариант 1.
i:=2; {индекс начинает изменяться с четного числа 2,}
while i<=n do {величина шага, равная двум, обеспечивает}
begin {сохранение четности индекса}
{обработка a[i]}
i:=i+2
end;
Вариант 2.
for i:=1 to n do {внутрь цикла перебора вложен оператор,}
if i mod 2 = 0 {проверяющий четность индекса. Работает эта схема}
then {дольше предыдущей}
{обработка a[i]};
Вариант 3.
for i:=1 to n div 2 do {используется формула четного числа. Поскольку}
{обработка a[2*i]}; {элементов с четным индексом - половина от }
{количества, то переменная цикла i изменяется до}
{ n div 2 }
Упражнение. Внесите изменения в предложенные выше фрагменты, которые необходимы для того, чтобы перебирались:
а) нечетные элементы массива, двигаясь от начала массива;
б) нечетные элементы, двигаясь от конца массива к его началу;
в) нечетные элементы при движении одновременно с начала и конца массива.
Встречаются задачи, когда необходимо организовать нелинейные (с переменным шагом) схемы перебора элементов массива.
Пример. Организуйте перебор элементов массива, индексы которого являются степенями двойки, т.е. 1, 2, 4, 8, 16 и т.д. Предлагается следующее решение этой задачи:
i:=1;
while i<=n do
begin {обработка a[i]};
i:=i*2
end;
Упражнение. Организуйте перебор элементов массива, индексы которого являются:
-
полными квадратами, т.е. 1, 4, 9, 16, 25,...;
-
числами Фибоначчи, т.е. 1, 2, 3, 5, 8, 13,...
Часто формулы, определяющие очередной элемент массива при нелинейной схеме перебора, могут быть достаточно сложными, для реализации которых нужно использовать дополнительные вложенные циклы.
Пример. Организуйте перебор элементов массива, индексами которых являются простые числа.
Решение. Необходимо вспомнить, что простыми называются числа, которые делятся на 1 и на само себя. Организуем внешний цикл, который будет перебирать все индексы массива, а внутренний цикл будет определять, является ли этот индекс простым числом. Для этого будем рассматривать все возможные делители для индекса i из интервала [2; i] (поскольку на 1 делятся все числа) до тех пор, пока индекс не разделится нацело на очередной делитель. Если при этом делитель и i совпадут, следовательно, i - простое число, иначе - нет.
for i := 1 to n do
begin
j := 1; {j - делитель}
repeat
j := j + 1;
until i mod j = 0;
if i = j then {обработка a[i]};
end;