Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

Лабораторная работа 7 Часть 1

Работа добавлена на сайт samzan.ru: 2016-03-30


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

Часть 1. Одномерные массивы

Цель работы. Получение практических навыков при работе со сложными типами данных – векторами

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

Общая форма описания переменной:

var<имя>:array |<тип-индексов>| of<тип-элементов>

Выбор отдельной компоненты одномерного массива осуществляется указанием идентификатора массива, за которым в квадратных скобках следует индексное выражение. Индексное выражение должно давать значение, лежащие в диапазоне, определяемом типом индекса. Например: M[1],M[2],…,M[n].

Для организации автоматического ввода случайных значений следует воспользоваться функцией random(n). Эта функция возвращает случайное число из диапазона от 0 до n–1. Для этого необходимо в основной программе инициализировать датчик случайных чисел командой randomize.

Формат вызова функций Random:

random(m), где m – значение, указывающее на правую границу диапазона выдаваемых значений.

Например, требуется заполнить одномерную таблицу размерностью 10, числами на диапазоне от 0 до 10.

program vector_full;

  const n=10;

  type vector=array[1…n] of integer;

  var v:vector;

  procedure enter(var vect: vector);

      var i: integer;

      begin

        for i: =1 to n do

        vect[i]:=random(11);

      end;

   begin

     randomize;

      enter(v);

   end.

Задание. По заданному условию сформировать одномерный массив (вектор), вывести на печать и произвести операции по обработке полученных компонент массива. Для всех вариантов исходными данными являются одномерный массив, элементы которого задаются с помощью датчика случайных чисел от – 50 до +50, и целое положительное число К.

Вариант 1. Определить число элементов массива, больших К.

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

Вариант 3. Найти произведение двух соседних элементов массива, наиболее близкое по модулю к К.

Вариант 4. Вычислить произведение последних K элементов массива.

Вариант 5. Найти сумму элементов массива с нечетными индексами, по модулю меньших К.

Вариант 6. Вычислить максимальную разность между К и суммой двух соседних элементов массива.

Вариант 7. Определить число элементов массива с четными индексами, по модулю не меньших К.

Вариант 8. Найти сумму тех элементов массива с нечетными индексами, каждый из которых по модулю меньше К.

Вариант 9. Найти разность между К и суммой всех положительных элементов массива с четными индексами.

Вариант 10. Определить индекс элемента массива, наиболее близкого к К.

Вариант 11. Определить число элементов массива, меньших К.

Вариант 12. Вычислить сумму последних К элементов массива с четными индексами.

Вариант 13. Найти произведение двух соседних элементов массива, наиболее удаленное по модулю от К.

Вариант 14. Найти произведение модулей первых К элементов массива.

Вариант 15. Найти сумму элементов массива с четными индексами, значение которых превышает К.

Вариант 16. Вычислить минимальную разность между К и суммой модулей двух соседних элементов массива.

Вариант 17. Определить индекс элемента массива, наиболее отдаленного от К.

Вариант 18. Найти сумму трех соседних элементов массива наиболее отдаленную от К.

Вариант 19. Найти разность между К и суммой всех положительных элементов массива с четными индексами.

Вариант 20. Найти сумму тех элементов массива с четными индексами, каждый из которых по модулю не превосходит К.

Часть 2. Сортировка одномерных массивов

Цель работы. Научиться использовать различные алгоритмы упорядочивания.

Рассмотрим массив целых или действительных чисел А1,…,Аn. Пусть требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по возрастанию А1< А2<…< Аn . Эта задача называется задачей сортировки или упорядочение массива. Для решения этой задачи можно воспользоваться следующими алгоритмами (другие варианты упорядочения, например, по убыванию А1> А2>…> Аn,  различаются незначительно):

Сортировка обменами I (метод пузырька)

Последовательно просматриваются элементы массива, если встречается неупорядоченная пара Аk>Ak-1, то элементы этой пары меняются местами; просмотр продолжается до Аn. В результате первого просмотра наибольший элемент оказывается на первом месте. Второй просмотр начинается с первого элемента и заканчивается элементом Аn-1. алгоритм заканчивается, когда в просмотре участвуют только два первых элемента.

Сортировка обменами II

Последовательно просматриваются элементы массива, если встречается неупорядоченная пара Аk>Ak-1, то элементы меняются местами; после чего просмотр начинается с начала массива. Алгоритм заканчивается, когда в результате очередного просмотра не удается найти упорядоченной пары.

Сортировка выбором

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

Сортировка простыми вставками

Применяется в этом случае, когда часть массива уже упорядочена. Просматриваются последовательно А2,…,An и каждый новый элемент Ai вставлять на подходящее место в уже упорядоченную совокупность A1Ai-1. Это место определяется последовательным сравнением Ai с упорядоченными элементами A1Ai-1.

Сортировка бинарными вставками

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

«Быстрая» сортировка (алгоритм Хоара)

Выбрать «средний» элемент массива. Затем переставить остальные элементы таким образом, чтобы слева от выбранного элемента оказались все элементы меньшие его, а справа – все элементы больше его. Тем самым выбранный элемент окажется «на своем месте». После чего следует рекурсивно применить данный алгоритм к частям массива справа и слева от очередного среднего.

Сортировка слияниями (алгоритм фон Неймана)

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

Рисунок 1. Пример сортировки фон Неймана

Задание. Для всех вариантов исходными данными являются одномерный массив, элементы которого задаются с помощью датчика случайных чисел от – 50 до +50. Варианты 1, 2, 3 4 и 5 используют сортировку простыми вставками, варианты 6, 7, 8, 9 и 10 сортировку обменами I, варианты 11, 12, 13, 14 и 15 – сортировку выбором, варианты 16, 17, 18, 19 и 20 – сортировку обменами II. Желающие получить повышенный балл могут использовать сортировку бинарными вставками, «быструю сортировку» или сортировку фон-Неймана.

Вариант 1, 6, 11, 16. Даны целые числа al,...,an. Получить в порядке возрастания различные числа из этого массива.

Вариант 2, 7, 12, 17. Даны целые числа al,...,an. Упорядочить массив по возрастанию. Удалить из массива элемент с номером k, затем вставить число b так, чтобы упорядоченность не нарушалась. Числа k и b вводятся с клавиатуры.

Вариант 3, 8, 13, 18. Даны целые числа al,...,an. Получить в порядке убывания различные числа из этого массива.

Вариант 4, 9, 14, 19. Даны целые числа al,...,an. Упорядочить массив по убыванию. Удалить из массива элемент с номером k, затем вставить число b так, чтобы упорядоченность не нарушалась. Числа k и b вводятся с клавиатуры.

Вариант 5, 10, 15, 20. В массиве al,...,an переставить числа таким образом, чтобы вначале шли элементы большие al, упорядоченные по возрастанию, затем сам элемент al, затем элементы меньшие al, упорядоченные по убыванию.




1. Инновационный менеджмент
2. Понятие и сущность мерчандайзинга
3. бюджетной политики как процессы первоначального разграничения и последующего распределения налоговых дох
4. следственные связи
5. Юриспруденция Новосибирск 2008Кафедра трудового и земельного права И
6. Cистемы пожарной сигнализации
7. РЕФЕРАТ дисертації на здобуття наукового ступеня кандидата історичних наук
8. Персональный компьютер, его состав и назначение
9. Моя любовь во мне она никуда не исчезает меняются только объекты
10. Проблема метода в бихевиоризме
11. это элемент прецедента
12. Правовая охрана фирменных наименований Фирменное наименование коммерческой организации ~ это наименован
13. Організація та методика бухгалтерського обліку і аналізу основних засобів
14. Nturedly begn hunting bout for them but they were nowhere to be seeneverything seemed to hve chnged since her swim in the pool nd the gret hll with the glss tble nd the little door hd vnished co
15. Лекция 18 Гломерулонефрит Гломерулонефрит приобретенное полиэтиологическое заболевание почек для к
16. Мировоззрение. Мирие ~ совть взглядов оценок принципов определяющих самое общее видение понимание мира
17. планы для Вас Московский государственный инженернофизический институт
18. Проектирование индивидуального провода
19. 20 Бухгалтерский учет Ярцева ауд
20. 35 мин. Часть В. Проводится на производственной практике