Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Уфимский государственный нефтяной технический университет»

Кафедра «Вычислительная техника и инженерная кибернетика»

ОТЧЁТ

По домашнему заданию №1

по информатике

“Обработка одномерных массивов данных”

Вариант № 143

Выполнил: ст. гр.

Факультет:

Проверил: .

Уфа, 2011

Постановка задачи

Разработать программу получения и обработки одномерного массива, состоящую из 4 частей.

Часть 1. Вычислить значения 31 элементов одномерного целочисленного массива r в интервале (-7,8) с использованием генератора случайных чисел.

Для получения целого случайного числа x на отрезке [a, b] в языке Паскале используется следующий оператор:

x := a + ROUND((b-a)*RANDOM (100)/100).

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

Часть 2. Вычислить произведение четных по номеру элементов третьей четверти массива.

Произведение ненулевых элементов заданного массива A = {a₁, a₂, a₃, …, a_n} вычисляется по формуле

Часть 3. Определить наименьший элемент среди принадлежащих отрезку [a/2;b/2] элементов второй половины массива.

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

Часть 4. Упорядочить нечётные по значению элементы второй четверти массива по убыванию квадратов.

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

Для проверки правильности упорядочения всего массива или его части выводить все его элементы.

Обязательные требования к программе.

1. Программу разработать для решения задачи в общем виде, для произвольных значений исходных данных: количества элементов n (2<=n<=100) и отрезка [a, b] (b>=a).

2. Решение каждой части в программе реализовать в виде процедуры.

3. Предусмотреть 3 варианта исполнения программы:

Тестовый расчёт

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

Решение задачи для новой последовательности случайных значений элементов массива при новом запуске программы (c Randomize).

1. Анализ задачи.

Исходными данными являются значения количества элементов в массиве n и отрезок [a, b].

Порядок решения задачи: сначала нужно получить одномерный маасив (часть 1), затем можно вычислить параметр массива (часть 2) или найти нужный элемент (часть 3). Упорядочение массива (часть 4) нужно выполнить в последнюю очередь, так как перестановка элементов массива при упорядочении может повлиять на вычисление параметра массива и определение нужного элемента.

Для лучшего понимания задачи, выявления её особенностей выполним тестовый расчёт.

Возьмём любые исходные данные, например n=17, а =-3, в = 4. Запишем 17 случайных целых чисел от -3 до 4 – это значения элементов массива R для тестового расчёта.

1, 0, -3, 2, 1, -3, 4, 3, 2, 3, 0, 4, 0, -2, -1, -1, 1

Для вычисления произведения сначала нужно выделить в общем виде номера элементов третьей четверти. Номер первого элемента третьей четверти вычисляется по формуле [n/2]+1 (квадратные скобки обозначают операцию выделения целой части значения выражения. Использование данной операции при определении номеров элементов в большинстве случаев позволяет равномерно разделить массив на части): [17/2] + 1 = [8,5] + 1 = 8 + 1 = 9. Номер последнего элемента: [3*n/4]= [17*3/4] = 12

Запишем элементы третьей четверти:

x₉ x₁₀ x₁₁ x₁₂

2 3 0 4

Выделим подчёркиванием нужные элементы: чётные по номеру, ненулевые значения.

Нужных элементов к = 2, их произведение 4*3= 12.

При вычислении произведения могут возникнуть следующие проблемы:

1. Не будет нужных элементов ( к = 0 ), например, если все чётные по номеру элементы равны 0. В этом случае нужно принять P = 0.

- произведение нужных элементов.

Для определения наименьшего элемента сначала выделим элементы второй половины массива: номер первого элемента второй половины [n/2] + 1 = [17/2]+1 = [8,5] + 1 = 8 + 1 = 9, номер последнего n = 17.

Запишем элементы второй половины массива:

x₉ x₁₀ x₁₁ x₁₂ x₁₃ x₁₄ x₁₅ x₁₆ x₁₇

2 3 0 4 0 -2 -1 -1 1

Выделим подчёркиванием нужные элементы: принадлежащие отрезку [a/2,b/2] для a = -3, b = 4. Нужных элементов 5, наименьшее значение равно -1, такое значение имеют два элемента: x_{15 =} -1 и x₁₆ =-1.

При решении данной задачи могут быть следующие ситуации:

1. Не будет нужных элементов;

2. Будет единственный элемент с наименьшим значением;

3. Будет множество элементов с наименьшим значением (в пределе все нужные элементы в рассматриваемой части имеют одинаковое значение).

При выборочном упорядочивании элементов массива сначала выделим нужную часть массива. Первый элемент второй четверти массива имеет номер [n/4] + 1 = [17/4] +1 = [4,25] +1 = 4 + 1 = 5, последний элемент имеет номер [n/2] = [17/2] = [17/2] = [8,5] = 8.

Запишем элементы второй четверти

Элементы x₅ x₆ x₇ x₈

Значения элементов 1 -3 4 3

Выделим подчёркиванием нечётные элементы.

Упорядоченные элементы 3 -3 4 1

.

2. Алгоритм решения задачи

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

1. Основной алгоритм.

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

1. Необходимо задачу решать в общем виде, для любых допустимых значений исходных данных.

2. Предусмотреть возможность выполнения 3 вариантов расчёта. Введём вспомогательную переменную Vr для управления вариантом расчёта: если Vr =0 – тестовый расчёт, Vr = 1 – без Randomize, любое другое значение Vr – расчёт с Randomize.

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

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

3.1 Основной алгоритм

3.2 Алгоритм получения элементов вектора

1

Vr – вариант расчёта

n – количество элементов

a – нижняя граница

b – верхняя граница

2

нет

3

да

4

5

6

R(1:n) - вектор

3.3 Алгоритм вычисления произведения

1

n, R(1:n)

2

3

4

нет

да

5

6

нет

да

7

8

P

3.4 Алгоритм определения минимального по модулю элемента среди принадлежащих [a/2,b/2] элементов второй половины массива

1

Part_3

2

3

нет

7

нет

4

да

да

нет

5

M>R_i

да

6

8

9

13

нет

10

да

11

12

3.5 Упорядочение массива

4. Таблицы переменных задачи

Таблица переменных основного алгоритма

Смысл переменных		Обозначение			Тип переменной		Примечания
		в алгоритме		в программе
Исходные данные: Вариант расчёта Размер массива Наименьшее значение элемента Наибольшее значение элемента	Vr n a b		Vr n a b	Целый Целый Целый Целый		VrÎZ 1< n <100 a Î[-32761; 32767] b Î[-32761; 32767] a <=b
Промежуточные данные: Номер элемента массива	i		i	Целый		i=
Результаты: Произведение вектор	P R		P R	Веществ. Одномерный массив		PÎR

Таблица переменных алгоритма получения вектора (Part_1)

Смысл переменных		Обозначение			Тип переменной		Примечания
		в алгоритме		в программе
Входные данные: Вариант расчёта Наименьшее значение элемента Наибольшее значение элемента	Vr n a b		Vr n a b	Целый Целый Целый Целый		VrÎZ 1< n <100 a Î[-32761; 32767] b Î[-32761; 32767] a <=b
Промежуточные данные: Номер элемента массива	i		i	Целый		i=
Выходные данные: Массив	R		R	Одномерный массив		riÎ[a;b]

Таблица переменных алгоритма вычисления произведения (Part_2)

Смысл переменных	Обозначение			Тип переменной		Примечания
	в алгоритме	в программе
Входные данные: Размер массива Массив	n R	n R	Целый Одномерный массив		nÎN riÎ[a;b]
Промежуточные данные: Номер элемента массива Количество нужных элементов	i k	i k	Целый Целый		i= k≥0
Выходные данные: произведения	P	P	Вещественный		PÎ R

Таблица переменных алгоритма определения минимального элемента (Part_3)

Смысл переменных	Обозначение		Тип переменной	Примечания
	в алгоритме	в программе
Входные данные: Размер массива Наименьшее значение элемента Наибольшее значение элемента Массив	n a b R	n a b R	Целый Целый Целый Одномерный массив	nÎN
Промежуточные данные: Номер элемента Результаты: Номер наименьшего элемента Значение наименьшего элемента	i k M	i k M	Целый Целый Целый	i=

Таблица переменных алгоритма упорядочения массива (Part_4)

Смысл переменных	Обозначение			Тип переменной		Примечания
	в алгоритме	в программе
Входные данные: Размер массива Массив	n R	n R	Целый Одномерный массив		1<n<100 RiÎ[a;b]
Промежуточные данные: Номер первого элемента в неупорядоченной части массива Номер следующего элемента в неупорядоченной части массива Номер нужного элемента Буфер обмена	i j k buf	i j k buf	Целый Целый Целый Целый		i= j=
Выходные данные: Вектор	R	R	Одномерный массив