Разработка алгоритма решения

Лабораторная работа №3

Указатели, массивы

Цель работы

Целью лабораторной работы является получение практических навыков в работе с указателями и с адресной арифметикой в языке C.

Теми для предварительной проработки

• Указатели. Типизированные указатели.
• Указатели и массивы.
• Адресная арифметика.
• Динамическое выделение памяти.
• Функции пользователя

Задания для выполнения

Задание

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

Дополнительные условия:

• размер массива определяется в начале выполнения программы как число в диапазоне 5 - 20;
• в тексте программы запрещается применять операцию индексации.

Варианты индивидуальных заданий

Задание 1

№ варианта	Диапазон значений	Что нужно сделать
	-100 - 100	Заменить все элементы с отрицательным значением на значение минимального не равного 0 положительного элемента
	-50 - 50	Подсчитать количество пар соседних элементов с одинаковыми значениями
	0 - 100	Подсчитать количество участков, которые образуют непрерывные последовательности чисел с неуменьшающимися значениями
	-50 - 50	Подсчитать количество пар соседних элементов, которые имеют противоположные знаки
	-100 - 100	Вывести начальные индексы всех непрерывных последовательностей неотрицательных чисел, длина которых больше 5
	-100 - 100	Найти ту непрерывную последовательность положительных чисел, сумма элементов в которой максимальная
	-100 - 100	Разместить все элементы с положительными значениями в левой части массива, элементы с отрицательными значениями - в правой, а нули - между ними
	-100 - 100	Заменить все элементы с отрицательными значениями средним арифметическим значением всех положительных элементов
	0 - 100	Найти непрерывный участок из 10 элементов, сумма которых максимальна
	0 - 100	Найти значение 3-го по величине элемента и значения всех элементов массива, которые его превышают, заменить на найденное значение
	-50 - 50	Во всех последовательностях отрицательных чисел ограничить значения тех элементов, абсолютное значение которых превышает абсолютное среднее для этой последовательности

Примеры решения задач (вариант 00)

Задание 1

Разработка алгоритма решения.

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

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

Нам необходимо будет вычислять среднее значение последовательности, следовательно - подсчитывать количество элементов в ней. Для этого мы вводим переменную nn - счетчик элементов, нулевое значение этой переменной будет показывать, что у нас нет последовательности для обработки. В начале обработки мы устанавливаем nn=0 (блок 6).

Далее организуем цикл со счетчиком (блок 7), в котором перебираем элементы массива. Для каждого элемента в первую очередь проверяется его знак (блок 8). Если это отрицательный элемент, то это может быть первый или не первый элемент последовательности. Это можно определить, проверяя значение переменной nn: если она 0 - это первый элемент (блок 9). Для первого элемента мы запоминаем в переменной ib индекс начала последовательности, устанавливаем счетчик элементов nn в 1, а в переменную av записываем значение этого элемента (блок 10). Для не первого элемента мы увеличиваем счетчик на 1, а значение элемента суммируем со занчением переменной av (блок 11). Таким образом, переменная av у нас играет роль накопителя суммы элементов последовательности.

Если же очередной элемент последовательности положительный, то возникает вопрос - не является ли этот элемент первым положительным элементом после отрицательной последовательности? Это можно проверить по счетчику nn. Если элемент первый, то значение nn должно быть больше 0 (блок 12). Если нет, то нам необходимо обработать ту отрицательную последовательность, которая только что закончилась. Для обработки мы в первую очередь получаем среднее значение (блок 13). Потом организуем цикл (блок 14) со счетчиком j, который изменяется от ib (индекс начала отрицательной последовательности, который мы сохранили раньше) до i-1 (i - это индекс первого положительного элемента после отрицательной - это индекс первого положительного элемента после отрицательной последовательности, следовательно i-1 - индекс последнего элемента отрицательной последовательности). В каждой итерации этого цикла мы сравниваем j-й элемент массива со средним значением av (блок 15). Если значение элемента меньше среднего (т.е. больше по абсолютному значению), то среднее значение записывается в j-й элемент (блок 16), если же нет - ничего не происходит. По выходу из цикла мы устанавливаем счетчик nn в 0 (блок 17), как признак того, что у нас нет необработанной последовательности. Для не первого положительного элемента нет необходимости что-либо делать.

После выхода из того цикла, который начался в блоке 7, необходимо проверить, не осталась ли у нас необработанная последовательность и, если да, обработать ее. На схеме алгоритма мы показали это одним блоком 18, действия, которые выполняются в этом блоке тождественны действиям, которые детально показаны в блоках 12 - 17.

По окончанию обработки мы выводим массив-результат (блок 19) и заканчиваем программу.

Алгоритм задачи с использованием указателей отличается тем, что в начале выполнения, после инициализации датчика случайных чисел, нужно получить случайное число в диапазоне 50 - 200 (назовем его size) и выделить память для массива целых чисел размером size. (На схеме алгоритма эти действия должны быть вставлены сразу же после блока 2). Перед самым выходом из программы мы должны освободить выделенную память (На схеме алгоритма после блока 19).

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

Ar[i] *(Ar+i)

Это соответствовало бы букве задания, но не духу языка C. Если мы переходим от индексации к адресации, у нас устраняется необходимость в индексах и даже в переменных, которые их представляют. Это приводит к другому способу реализации всех циклов. Если имя массива Ar является указателем на его начало, то вместо цикла, в котором индекс i меняется от 0 до size, мы можем организовать цикл, в котором некоторый текущий указатель Cr меняется от Ar до Ar+size. Также, когда нам нужно запомнить начало отрицательной последовательности, мы можем запоминать не индекс соответствующего элемента, а его адрес - указатель на него.