Программирование. Обработка последовательностей - Обработка информации - ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ

После изучения данного раздела вы сможете написать программу, обрабатывающую последовательность целых чисел.

Несмотря на то, что никакой новой теории здесь не рассматривается, мы постараемся создать у вас понимание того, как нужно писать подобные программы и из каких соображений это делается.

Разбор типовых задач

Подсчёт элементов последовательности

Задача 1. Напишите программу, которая:

- вводит с клавиатуры натуральное число N. После этого вводит ещё N целых чисел.

- выводит на экран количество положительных чисел среди введённых чисел.

Пример ввода	Пример вывода
5	2
5 -4 0 1 -3
3	0
-4 0 -18
3	3
5 4 7

Решение

Будем придумывать программу последовательно. Какие для программы понадобятся переменные, будет понятно после того, как мы придумаем алгоритм.

Программа должна ввести с клавиатуры число N. Это просто и понятно:

Теперь нужно ввести с клавиатуры ещё N целых чисел. Количество чисел заранее неизвестно. Поэтому мы не можем просто завести нужное число переменных и ввести их одним read, перечислив, например, через запятую. Необходимо использовать цикл.

К моменту ввода этих N чисел известно, сколько раз цикл должен выполниться — N. Поэтому используем цикл for. Для работы цикла for требуется пемеренная-счётчик цикла. Например, назовём её i. Её значение будет меняться от 1 до N (самый простой способ сделать так, чтобы цикл выполнился N раз). То есть:

Мы используем обозначение переменной N с большой буквы. Язык Паскаль не различает заглавные и маленькие буквы. Можно было бы написать эту переменную как п. Но по условию она называется N. Чтобы программа была понятнее, используем именно такое обозначение — с большой буквы N.

Требуется ввести с клавиатуры N целых чисел. Делаем это в цикле, который выполняется N раз. Значит, на каждом шаге цикла нужно вводить по одному числу. Используем для этого переменную а.

Получаем:

Однако, такой цикл только вводит с клавиатуры числа одно за другим, каждый раз в одну и ту же переменную. То есть, после ввода одного числа оно тут же пропадает и в переменную попадает следующее число. Это не совсем то, что нам нужно. Мы должны успевать анализировать каждое вводимое число на то, является ли оно положительным (ведь необходимо посчитать количество положительных введённых чисел). Следовательно, каждое вводимое число проверим на положительность. То есть, на каждом шаге цикла нужно не только вводить число (read (а)), но и проверять условие. Тело цикла будет состоять не из одной команды, а, по меньшей мере, из двух. Чтобы написать такое на языке Паскаль, нужно использовать операторную скобку:

После ввода числа будем проверять его на положительность:

Пора подумать, что делать, когда мы обнаружили положительное число. Чтобы посчитать количество положительных чисел, используем счётчик. Принцип его работы такой же, как загибание пальцев на руках, когда вы хотите что-то посчитать. При обнаружении нужного предмета, загибаем на руках один палец. При обнаружении следующего — ещё один. То есть, количество загнутых пальцев становится каждый раз на 1 больше. Так и работает счётчик.

Вы можете возразить — у нас уже есть один счётчик! Это счётчик цикла for.

Верно. Но счётчик цикла for нужен для обеспечения работы цикла for. Нам же нужен счётчик для подсчёта положительных элементов. Это должна быть отдельная переменная. При нахождении каждого положительного числа эта переменная будет увеличиваться на 1. Назовём этот счётчик буквой к. Тогда, увеличение переменной на 1: k := k + 1. То есть:

В приведённом фрагменте программы отсутствует одна очень важная вещь — задание начального значения счётчика к! Когда программа обнаружит первое по счёту положительное число, она должна будет выполнить команду “k := k + 1”, т. е. взять текущее значение переменной к, прибавить к нему 1 и сделать результат сложения новым значением переменной k. Но к этому моменту переменная к ничему не равна! Это ошибка. Обязательно перед циклом нужно задавать начальное значение для подобных переменных.

В нашем случае до начала цикла мы ещё не ввели ни одного элемента последовательности и, соответственно, не нашли ни одного положительного среди них. Значит, количество найденных положительных элементов перед началом цикла должно быть равно нулю:

Это действие необходимо выполнить перед циклом.

Программа почти готова. Осталось только не забыть вывести на экран ответ:

Теперь самое время уточнить, что для работы программы все использованные переменные должны быть описаны в разделе var. Вспоминаем, какие переменные мы использовали: N — количество вводимых элементов, i — счётчик цикла for, а — вводимый и проверяемый элемент последовательности, k — счётчик количества положительных элементов. Получаем все вместе:

Очень важное (и часто забываемое) правило: перед началом цикла обязательно нужно задать начальные значения для всех переменных, которые накапливаются в цикле или с которыми в цикле происходят сравнения!

Поиск максимума (минимума) последовательности

Задача 1. Напишите программу, которая:

- вводит в клавиатуры натуральное число N. После этого вводит ещё N целых чисел;

- выводит на экран максимальное среди введённых чисел.

Пример ввода	Пример вывода
5	2
5 -4 0 1 -3
3	0
-4 0 -18
3	3
5 4 7

Решение

Для нахождения максимума последовательности воспользуемся такой технологией.

Заведём отдельную переменную, в которой будем хранить значение текущего максимума. То есть, на каждом шаге цикла в этой переменной будет храниться самое большое значение среди всех значений, встретившихся к текущему моменту.

На каждом шаге цикла сравниваем текущий элемент последовательности (введённое с клавиатуры число) со значением текущего максимума. Если окажется, что только что введённое число лучше (больше) текущего максимума, то это число положим новым текущим значением максимума. К моменту окончания цикла значение, лежащее в текущем максимуме будет максимальным значением элементов последовательности.

В этом алгоритме пока отсутствует один важный момент — неизвестно, какое начальное значение нужно положить в текущий максимум (перед циклом), чтобы с ним можно было сравнивать все элементы последовательности!?

Ответ на этот вопрос зависит от условия задачи. Если в задаче нам известно ограничение на диапазон значений элементов последовательности, то в качестве начального значения максимума нужно взять значение, выходящее (в меньшую сторону) за указанный диапазон.

Если же такое ограничение не известно, в качестве начального значения максимума нужно взять первый элемент последовательности. Так как начальное значение нужно задавать перед циклом, для обеспечения этой технологии необходимо перед циклом отдельно ввести с клавиатуры значение первого элемента и положить его в качестве начального значения максимума. Затем запустить цикл, который начинается уже не с 1-го элемента, а со второго.

Представленный нами алгоритм не будет работать, если требуется найти максимум с условием (например, максимальный отрицательный элемент последовательности), но при этом не задано ограничение на диапазон значений элементов последовательности. В этом случае нужно сначала найти первый элемент, удовлетворяющий условию, принять его значение в качестве начального значения максимума, а затем уже, начиная со следующего элемента, искать максимум с условием. Однако, такую задачу обычно не задают учащимся на данном этапе обучения.

В условии нашей задаче не задано ограничение на диапазон возможных значений элементов массива, поэтому воспользуемся второй технологией — возьмём в качестве начального значения максимума первый элемент последовательности.

Приступим к написанию программы.

Для хранения текущего значения максимума используем переменную mах. Остальные переменные возьмём из тех же соображений, что и при решении задачи о подсчёте элементов последовательности: N — количество вводимых чисел (длина последовательности), i — счётчик цикла for, а — вводимое в цикле число (текущий элемент последовательности).

Перед циклом побеспокоимся о том, чтобы начальное значение максимума было равно первому элементу последовательности.

Для этого введём первый элемент последовательности и положим его значение в шах:

Можно сократить эти две команды до одной:

В данном случае вводимое число сразу попадает в переменную mах.

Так как первый элемент последовательности уже ввели и обработали, цикл for будет теперь начинаться с двух:

В цикле нужно будет вводить числа и анализировать их. То есть, выполнять более одного оператора. Значит, нужно не забыть использовать операторную скобку (begin-end). Проверяем введённое число (а), не является ли оно больше, чем текущее значение mах:

Если оказывается, что введённое число а больше текущего значения mах, то число а записываем в качестве нового значения max:

После окончания цикла выводим ответ на экран.

Все вместе:

Благодаря чему эта программа ищет именно наибольшее значение последовательности, а не наименьшее? Благодаря тому, что мы назвали переменную именем max? Конечно, нет. Мы использовали такое имя, чтобы программа была понятнее. Поиск именно максимума происходит из-за знака, стоящего в условном операторе if. Там проверяется, не является ли введённая переменная а больше текущего максимума.

Если в задаче потребуется искать наименьшее значение последовательности вместо наибольшего, то нужно просто поменять знак сравнения с “больше” на “меньше”. А для понятности программы желательно, кроме этого, ещё переименовать переменную шах в переменную min.

Задача 2. Напишите программу, которая в последовательности натуральных чисел определяет минимальное число, оканчивающееся на 4. Программа получает на вход количество чисел в последовательности, а затем сами числа.

В последовательности всегда имеется число, оканчивающееся на 4.

Количество чисел не превышает 1000. Введённые числа не превышают 30 000.

Программа должна вывести одно число — минимальное число, оканчивающееся на 4.

Пример ввода	Пример вывода
3	14
24
14
34
3	14
85
14
24
3	14
14
24
8

Решение

За основу алгоритма возьмём алгоритм нахождения максимума, рассмотренный нами выше. Только при сравнении с текущим значением будем, проверять условие не “больше”, а “меньше”.

В данной задаче требуется найти не просто минимальное число последовательности, а минимальное число с условием (число должно оканчиваться на 4). Значит, при вводе очередного числа нужно не только сравнивать его с максимумом, а и не забывать проверять, что это число подходит под условие (оканчивается на 4).

Очень важное обстоятельство, которое необходимо помнить при поиске максимума с условием — ни в коем случае нельзя принимать значение первого элемента последовательности в качестве начального значения максимума! Потому что, если первый элемент не удовлетворяет условию, но при этом является, например, наибольшим элементом последовательности, то такая программа найдёт именно первый элемент в качестве искомого, что неверно.

Например, в данной задаче для входных данных:

3

56 14 24

такая программа возьмёт в качестве начального значения максимума число 56. При сравнении с ним числа 14 и 24 (оканчивающиеся на 4) не будут больше 56, и поэтому не будут найдены.

Однако, в задаче задано ограничение на диапазон возможных значений элементов последовательности: известно, что введённые числа — натуральные и не превышают 30 000.

Значит, в качестве начального значения максимума можно взять значение, выходящее за допустимый диапазон значений элементов.

Так как мы должны найти минимум, нужно брать значение, выходящее за диапазон значений сверху, т. е. такое значение, которое гарантированно больше значения любого элемента последовательности. Для того, чтобы при сравнении начального значения минимума с любым подходящим под условие элементом последовательности, условие “меньше” обязательно выполнилось и в качестве нового значения минимума с этого момента можно было взять текущий, подходящий под условие, элемент. Таким значением в нашем случае можно взять число 30 001. Оно как раз больше любого элемента последовательности.

В результате, перед циклом в качестве начального значения минимума возьмём 30 001:

Так как в качестве начального значения минимума используется просто постоянное значение, а не первый элемент последовательности, то цикл по вводу и проверки элементов нужно запускать с первого элемента до последнего (от 1 до N).

В цикле после ввода очередного элемента не забудем проверить, что элемент оканчивается на 4. Для этого необходимо проверять на равенство четырём последнюю цифру числа. Чтобы извлечь из числа последнюю цифру, нужно найти остаток от деления числа на 10. То есть:

Объединяем эти соображения в одну программу: