Структурированные типы данных. Массивы. Вспомогательные алгоритмы.

Группа Т(О), ТГ(О), С(О)–24-02, 2025 год

Занятие по рабочей программе №6

Дисциплина: ОД.08 «Информатика»

Раздел 3. Информационное моделирование.

Тема: Структурированные типы данных. Массивы. Вспомогательные алгоритмы.

1. Цель занятия:

   1. Дидактическая:

• сформулировать представление студентов о Структурированных типах данных;

• выяснить различные подходы к этапам моделирования;

• определение Вспомогательный алгоритм;

• систематизировать и объяснить сущность работы с массивами данных;

• углубить и закрепить знания по дисциплине «Информатика».

Воспитательная:

• развивать коммуникативные способности;

• развивать аналитические способности;

• развивать творческий подход к процессу обучения.

• воспитывать самостоятельность, дисциплинированность;

• стимулировать студентов к изучению дисциплины;

• побуждать к формированию активной жизненной позиции;

• прививать уважение и любовь к будущей профессии.

Вид занятия: лекция.

Тип занятия: обобщение и систематизация знаний.

Форма проведения занятия: репродуктивная и эвристическая беседа.

Междисциплинарные связи:

Обеспечивающие Математика, Охрана труда, Безопасность жизнедеятельности.

Обеспечиваемые

Информационные технологии в профессиональной деятельности, и др.

Методическое обеспечение: опорный конспект.

Литература:

1. Информатика. 10 класс : учебник для общеобразоват. организаций: базовый и углубленный уровни / [А.Г.Гейн , А.Б Ливчак, А.И. Сенокосов, Н.А. Юнерман]. – 4-е изд. – М. : Просвещение, 2018. – 272 с. : ил. – ISBN 978-5-09-058130-1

2. Зимин, В. П.  Информатика. Лабораторный практикум в 2 ч. Часть 1 : учебное пособие для среднего профессионального образования / В. П. Зимин. — 2-е изд., испр. и доп. — Москва : Издательство Юрайт, 2023. — 126 с. — (Профессиональное образование). — ISBN 978-5-534-11851-3. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/514893

ХОД ЗАНЯТИЯ

1. Ознакомление с темой, целью и планом занятия.

Тема: Структурированные типы данных. Массивы. Вспомогательные алгоритмы.

ПЛАН

1. Структурированные данные и алгоритмы их обработки.

2. Массивы.

3. Вспомогательные алгоритмы и процедуры.

1. Изложение и изучение нового материала.

ЛИТЕРАТУРА: [2], стр.

1. Структурированные данные и алгоритмы их обработки

Для повышения производительности и качества работы необхо­димо иметь данные, максимально приближенные к реальным анало­гам. Тип данных, позволяющий хранить вместе под одним именем несколько переменных, называется структурированным. Каждый язык программирования имеет свои структурированные типы. Рас­смотрим структуру, объединяющую элементы одного типа данных – массив.

Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой адресуются (раз­личаются) порядковыми номерами (индексами). В качестве иллюст­рации можно представить шкаф, содержащий множество пронуме­рованных ящиков (совокупность – «Ящик № 1», «Ящик № 2», «Ящик № 3» и т.д.; «Ящик» – общее имя всех ее элементов). Доступ к со­держимому конкретного ящика (элементу массива) осуществляется после выбора ящика по его номеру (индексу). Элементы массива в памяти компьютера хранятся по соседству, одиночные элементы про­стого типа такого расположения данных в памяти не предполагают. Массивы различаются количеством индексов, определяющих их эле­менты.

Одномерный массив (шкаф ящиков в один ряд) предполагает на­личие у каждого элемента только одного индекса. Примерами одно­мерных массивов служат арифметическая (а_i) и геометрическая (b_i) последовательности, определяющие конечные ряды чисел. Количе­ство элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скоб­ках, рядом с его именем. Например, если сказано: «задан массив А(10)», это означает, что даны элементы: a₁, a₂, ... , а₁₀. Рассмотрим алгоритмы обработки элементов одномерных массивов.

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

Рассмотрим двумерный массив (шкаф с множеством ящиков, положение которых определяется двумя коорди­натами – по горизонтали и по вертикали). В математике двумерный массив (таблица чисел) называется матрицей. Каждый ее элемент имеет два индекса а_ij, первый индекс i определяет номер строки, в которой на­ходится элемент (координата по горизонтали), а второй, j – номер столбца (координата по вертикали). Двумерный массив характеризу­ется двумя размерностями N и М, определяющими число строк и столбцов соответственно.

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

На рис.1 представлен алгоритм ввода матрицы A(N на М).

Разберем примеры алгоритма на псевдокоде:

Дан массив целых чисел {A_i}, где i=1,2,3,…,M. Пусть M равно 15. Программа вычисляет произведение сумм некоторых элементов этого массива. В программе введены следующие константы: G=1; W=12; T=8; L=15. Рис.1.

Для удобства пояснений, запишем псевдокод с номерами строк:

1 ПРОГРАММА 15;

2   ФУНКЦИЯ SUMMA(I1,I2);

3   НАЧАТЬ ФУНКЦИЮ

4     ||S:=0; 5     ||НЦ ДЛЯ I:=I1 ДО I2

6     ||||S:=S + A[I]

7     ||КЦ;

8     ||SUMMA:=S

9   КОНЕЦ ФУНКЦИИ;

10 НАЧАТЬ ПРОГРАММУ

11 ||ПИСАТЬ ('ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:' );

12 ||НЦ ДЛЯ J:=1 ДО M

13 ||||ЧИТАТЬ (A[J]);

14 ||КЦ;

15 ||P:=SUMMA (G, W)*SUMMA(T, L);

16 ||ПИСАТЬ ('ПРОИЗВЕДЕНИЕ РАВНО:', P)

17 КОНЕЦ ПРОГРАММЫ.

В строке 1 записано название программы – «Программа 15».

В строке 2 описан заголовок функции Summa. Как видно из заголовка в функцию передается 2 формальных параметра – I1 и I2. Само тело функции записано в строках с 3 по 9. Проанализируем тело функции.

В строке 4 переменной S присваивается начальное значение равное 0.

В строках с 5 по 7 записан цикл. Количество повторений цикла известно – оно равно I2-I1. В теле цикла (строка 6) производится прибавление к прежнему значению переменной S элемента под номером I массива из A.

После цикла, в строке 8 записан результат, который будет выдавать функция (это называется – возвращать результат) – результат равен значению переменной S.

Например, если I1=1, I2=1, A[1]=1, A[2]=2, A[3]=4, то выполнение тела функции будет происходить следующим образом:

Шаг 1: 4     ||S:=0;

Шаг 2: 5     ||НЦ ДЛЯ I:=1 ДО 3

Шаг 3: 6     ||||S:=0 + A[1]=0+1=1

Шаг 4: увеличение счетчика цикла: I=I+1=1+1=2

Шаг 5: возврат на начало цикла (строка 5) Шаг 6: 6     ||||S:=1 + A[2]=1+2=3

Шаг 7: увеличение счетчика цикла: I=I+1=2+1=3

Шаг 8: возврат на начало цикла (строка 5) Шаг 9: 6     ||||S:=3 + A[3]=3+3=6

Шаг 10: увеличение счетчика цикла: I=I+1=3+1=4

Шаг 11: возврат на начало цикла (строка 5)

Шаг 12: поскольку значение счетчика цикла больше чем заданный предел (I2=3) то происходит выход из цикла и переход на сроку за циклом

Шаг 13: 8     ||SUMMA:=S=6

Шаг 14: завершение функции

Итак, функция производит суммирование всех элементов массива A, начиная с элемента с номером I1 и заканчивая номером I2. Математически, это записывается:

В строке 10 начинается выполнение программы.

В строке 11 на экран выводится надпись «ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:».

В строках с 12 по 14 записан цикл, в котором последовательно вводятся элементы массива A.

В строке 15 вызывается функция SUMMA с фактическими параметрами G и W и еще раз с фактическими параметрами T и L. Результат перемножается и присваивается переменной P.

В строке 16 на экран выводится надпись «ПРОИЗВЕДЕНИЕ РАВНО» и после нее значение переменной P.

Итак, программа выполняется следующим образом:

Шаг 1: на экран пишется «ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:» (строка 10)

Шаг 2: в цикле вводятся элементы массива A (строки 12-14, количество повторений цикла М-1)

Шаг 3: выполняется вызов функции SUMMA (строка 15)

Шаг 4: выполняется тело функции SUMMA (строки 2-9. При этом вместо I1 подставляется G, а вместо I2 подставляется W. Результат:  )

Шаг 5: выполняется тело функции SUMMA (строки 2-9. При этом вместо I1 подставляется T, а вместо I2 подставляется L. Результат:  )

Шаг 6: переменной P присваивается произведение результатов вызовов функций SUMMA (строка 15. Результат:  )

Шаг 7: на экран выводится «ПРОИЗВЕДЕНИЕ РАВНО:» (строка 16)

Шаг 8: на экран выводится значение переменной P (строка 16)

Шаг 9: выполнение программы завершается (строка 17)

2. Массивы

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

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

• ряд;

• таблица;

• матрица;

• вектор.

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

2.1. Разновидности.

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

1. Одномерные. Индекс будет всего один.

2. Двумерные. «Адресов обращения» два.

3. Три и более. Встречаются на практике крайне редко.

Огромную роль играет форма (или структура). Она представлена сведениями о количестве размерностей и размере (протяженности) массива по каждой размерностей. Может выступать в виде самостоятельного одномерного массива.

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

Также есть гетерогенные массивы - хранящие в разных элементах информацию совершенно разных типов. В языках разработки принято выделять специфические массивные виды:

• ассоциативные;

• деревья отрезков;

• разреженные;

• параллельные;

• V-списки.

Одномерные массивы обладают нестрогим соответствием векторам, а двумерные – матрицам. Это - самые распространенные варианты. Именно с ними предстоит работать далее.

2.2. Индексы - общие понятия.

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

• с отчетом с нуля;

• отсчет начинается с единички;

• отсчет от специфического значения, которое заранее задается разработчиком.

Первый вариант предусматривается преимущественно в низкоуровневых языках разработки, но и в ЯП высокого уровня тоже встречается. Пример – СИ-семейство. В некоторых языках разработки допускается определение диапазона индексов в виде произвольного диапазона значений любого типа данных, приводимого к целому. Это – набор перечислений, целых, а также символов. Логический тип данных тут тоже применяется. Такой вариант актуален для Модула-2, Ада и Паскаль.

2.3. Несколько слов о динамическом типе.

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

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

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

1. Описание динамического массива. На уровне языка оно может быть представлено синтаксической конструкцией. В случае с библиотеками – библиотечным типом данных, значение которого устанавливается стандартным образом. При создании (описании) динамического «упорядоченного множества» нужно указать его начальный размер. Это требование не является обязательным.

2. Операции определения текущего размера динамического массива.

3. Изменение размеров заданного «упорядоченного множества».

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

2.4. Одномерный массив.

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

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

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

• имеющиеся значения (их нужно предварительно задать);

• индексы элементов.

Начальный индекс зависит от выбранного языка программирования. В Pascal можно задавать его произвольно. Согласно действующим правилам разработки лучше начинать с единицы. Это упростит дальнейшую работу с рассматриваемым компонентом. Итоговый (конечный) индекс будет определяться в соответствии с имеющейся задачей. Численно он соответствует размеру заданного множества, которое отражает количество содержащихся в нем элементов.

В основном работать предстоит с числовыми массивами. Они включают в себя вещественные и целые значения. Пример – цепочка 1 2 3 4 5 6 7 8 9. Это – не только множество, но и массив.

Рис.2. Пример соответствующего одномерного компонента.

3. Вспомогательные алгоритмы и процедуры

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

В качестве примера рассмотрим следующую задачу: требуется составить алгоритм вычисления степенной функции с целым показателем у = хk, где k — целое число, х ≠ 0. В алгебре такая функция определена следующим образом:

Для данной задачи в качестве подзадачи можно рассматривать возведение числа в целую положительную степень.

Учитывая, что 1/х-n = (1/х) -n , запишем основной алгоритм решения этой задачи.

Здесь дважды присутствует команда обращения к вспомогательному алгоритму с именем СТЕПЕНЬ. Это алгоритм возведения вещественного основания в целую положительную степень путем его многократного перемножения. Величины, стоящие в скобках в команде обращения к вспомогательному алгоритму, называются фактическими параметрами.

В учебном алгоритмическом языке вспомогательные алгоритмы оформляются в виде процедур. Запишем на алгоритмическом языке процедуру СТЕПЕНЬ.

Заголовок вспомогательного алгоритма начинается со слова «процедура», после которого следует имя процедуры и в скобках — список формальных параметров. В этом списке перечисляются переменные-аргументы и переменные-результаты с указанием их типов. Здесь а и k — формальные параметры-аргументы, z — параметр-результат. Следовательно, процедура степень производит вычисления по формуле z = аk. В основном алгоритме «Степенная функция» обращение к процедуре производится путем указания ее имени с последующим в скобках списком фактических параметров. Между формальными и фактическими параметрами процедуры должны выполняться следующие правила соответствия:

• по количеству (сколько формальных, столько и фактических параметров);

• по последовательности (первому формальному соответствует первый фактический параметр,

• второму — второй и т.д.);

• по типам (типы соответствующих формальных и фактических параметров должны совпадать).

Фактические параметры-аргументы могут быть выражениями соответствующего типа. Обращение к процедуре инициирует следующие действия:

1. Значения параметров-аргументов присваиваются соответствующим формальным параметрам.

2. Выполняется тело процедуры (команды внутри процедуры).

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

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

Использование процедур позволяет строить сложные алгоритмы методом последовательной детализации.

Кон­троль­ные во­про­сы

1. Структурированные типы данных, примеры.

2. Как описываются массивы?

3. Что такое размер массива?

4. Какие операции допустимы для массивов?

5. Какие способы задания значений элементам массива вы знаете?

6. Как можно вывести массив?

7. Какие операции допустимы для элементов массива вещественных чисел?

8. Что такое Вспомогательный алгоритм?

ДОМАШНЕЕ ЗАДАНИЕ

1. Составить конспект лекции.

2. Ответить письменно на контрольные вопросы.

Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы.

Основные источники:

1. Информатика. 10 класс : учебник для общеобразоват. организаций: базовый и углубленный уровни / [А.Г.Гейн , А.Б Ливчак, А.И. Сенокосов, Н.А. Юнерман]. – 4-е изд. – М. : Просвещение, 2018. – 272 с. : ил. – ISBN 978-5-09-058130-1

2. Информатика. 11 класс : учебник для общеобразоват. организаций: базовый и углубленный уровни / [А.Г.Гейн, А.И. Сенокосов]. – 6-е изд. – М. : Просвещение, 2019. – 336 с. : ил. – ISBN 978-5-09-072326-8.

Электронные источники:

1. Зимин, В. П.  Информатика. Лабораторный практикум в 2 ч. Часть 1 : учебное пособие для среднего профессионального образования / В. П. Зимин. — 2-е изд., испр. и доп. — Москва : Издательство Юрайт, 2023. — 126 с. — (Профессиональное образование). — ISBN 978-5-534-11851-3. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/514893

2. Зимин, В. П.  Информатика. Лабораторный практикум в 2 ч. Часть 2 : учебное пособие для среднего профессионального образования / В. П. Зимин. — 2-е изд. — Москва : Издательство Юрайт, 2023. — 153 с. — (Профессиональное образование). — ISBN 978-5-534-11854-4. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/514918

3. Мойзес, О. Е. Информатика. Углубленный курс : учебное пособие для среднего профессионального образования / О. Е. Мойзес, Е. А. Кузьменко. — Москва: Издательство Юрайт, 2020. — 164 с. — (Профессиональное образование). — ISBN 978-5-534-07980-7. — Текст : электронный // ЭБС Юрайт [сайт]. — URL: https://urait.ru/bcode/455803 .

4. Советов, Б. Я. Информационные технологии : учебник для среднего профессионального образования / Б. Я. Советов, В. В. Цехановский. — 7-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2020. — 327 с. — (Профессиональное образование). — ISBN 978-5-534-06399-8. — Текст: электронный // ЭБС Юрайт [сайт]. — URL: https://urait.ru/bcode/450686 .

5. Новожилов, О. П. Информатика в 2 ч. Часть 1 : учебник для среднего профессионального образования / О. П. Новожилов. — 3-е изд., перераб. и доп. — Москва: Издательство Юрайт, 2020. — 320 с. — (Профессиональное образование). — ISBN 978-5-534-06372-1. — Текст : электронный // ЭБС Юрайт [сайт]. — URL: https://urait.ru/bcode/448995 .

6. Новожилов, О. П. Информатика в 2 ч. Часть 2 : учебник для среднего профессионального образования / О. П. Новожилов. — 3-е изд., перераб. и доп. — Москва: Издательство Юрайт, 2020. — 302 с. — (Профессиональное образование). — ISBN 978-5-534-06374-5. — Текст : электронный // ЭБС Юрайт [сайт]. — URL: https://urait.ru/bcode/448996

7. Гаврилов, М. В. Информатика и информационные технологии : учебник для среднего профессионального образования / М. В. Гаврилов, В. А. Климов. — 4-е изд., перераб. и доп. — Москва: Издательство Юрайт, 2020. — 383 с. — (Профессиональное образование). — ISBN 978-5-534-03051-8. — Текст: электронный // ЭБС Юрайт [сайт]. — URL: https://urait.ru/bcode/449286

Дополнительные источники:

1. Филимонова, Е. В. Информатика и информационные технологии в профессиональной деятельности: учебник / Е. В. Филимонова. – Москва: Юстиция, 2019. – 213 с. – (Среднее профессиональное образование). - ISBN 978-5-4365-2703-1.

2. Цветкова М.С., Информатика. Практикум для профессий и специальностей естественно-научного и гуманитарного профилей: : учеб. пособие для студентов учреждений сред. проф. образования / М.С. Цветкова, И.Ю. Хлобыстова. - 5-е изд., стер. - М. : Издательский центр "Академия", 2019. - 240 с. ISBN 978-5-4468-7901-4

Электронные источники:

1. Гаврилов, М. В.  Информатика и информационные технологии : учебник для среднего профессионального образования / М. В. Гаврилов, В. А. Климов. — 4-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2021. — 383 с. — (Профессиональное образование). — ISBN 978-5-534-03051-8. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/469424

2. Акопов, А. С.  Компьютерное моделирование : учебник и практикум для среднего профессионального образования / А. С. Акопов. — Москва : Издательство Юрайт, 2023. — 389 с. — (Профессиональное образование). — ISBN 978-5-534-10712-8. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/517999

3. Демин, А. Ю.  Информатика. Лабораторный практикум : учебное пособие для среднего профессионального образования / А. Ю. Демин, В. А. Дорофеев. — Москва : Издательство Юрайт, 2023. — 133 с. — (Профессиональное образование). — ISBN 978-5-534-07984-5. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/516857

Преподаватель: Владимир Александрович Волков