План-конспект урока по теме: «Линейные массивы»
Вид занятия: лекция
Тема: Табличные величины.
Цель занятия:
Дидактическая:
овладеть базовыми знаниями по глобальной сети Internet ;
ознакомится с принципами, устройством, организацией работы в этой сети;
сформировать представление о ресурсах Internet;
обобщить и закрепить знания по новому материалу в конце лекции.
Воспитательная: формировать ответственное
Методы: лекция, беседа
Материально-техническое оснащение и дидактические методы: IBM совместимый компьютер, имеющий модем, для подключение к Internet через телефонную линию.
1. Вводно-мотивационный этап:
цели:
образовательная: Сформировать представление у учащихся о понятии достижимых целях. Рассмотреть понятие исполнителя, различные примеры
развивающая: Формирование приемов логического и алгоритмического мышления, развитие познавательного интереса к предмету, развитие умения планировать свою деятельность;
воспитательная: Воспитание аккуратности, точности.
3. Ядро содержания обучения: алфавит, основные понятия языка программирования.
4. Предварительная подготовка учащихся: изученный материал на предыдущих уроках информатики.
5. Предварительная подготовка учителя: изучение материала урока, написание конспекта, разработка мет.пособий.
6. Дидактические основания урока:
методы обучения: объяснительно-иллюстративный, эвристический;
тип урока: комбинированный;
формы учебной работы учащихся: фронтальная работа, работа в парах.
7. Средства обучения:
информационные: для учащихся — Гейн А.Г. «ОИВТ», учителя — Гейн «ОИВТ», Семакин «Базовый курс 7-8», Макарова Н.В. «Информатика 7-9»
технические и программные средства — «Кенгуренок», среда языка Бейсик.
8. План урока:
- 1. Орг. Момент (1-2 мин)
- 2. Актуализация опорных знаний (5 мин)
- 3. Объяснение нового материала (35 мин)
- 4. Решение задач (35)
- 5. Итог урока (3 мин).
9. Содержателъно-деятелъностный компонент (ход урока).
При решении задач человек часто использует таблицы: для записи вход данных, получения справочной информации и т.д. Таблицам присваивают имена, а каждый элемент имеет свой адрес. Поэтому любые данные можно найти в таблице, зная ее имя и индексы исковых элементов. Чажще всего используют линейные и прямоугольные таблицы.
Таблицы с одним индексом называются линейными, Значения, которые образовывают лин таблицу, при записи на бумаге располагают в виде строки или столбца. Каждому элементу таблицы соответствует его порядковый номер. Таблица — это упорядоченная последовательность переменных одного типа, которым дано одно общее имя. Элементы таблицы размещаются в последовательно расположенных ячейках. В языках программирования для работы с табличными величинами используют массивы.
Массив (таблица) — это упорядоченный набор фиксированног кол-ва однотипных элементов. Все элементы массива имеют порядковый номер(индекс). Благодаря этой нумерации можно выделить любой элемент массива и производить с ним операции, как с простым значением базового типа. Элементы массива еще называют индексированными переменными, в отличие от простых переменных.
Основные операции над массивами определены на уровне элементов. Операции над элементами массивов определяются типом элементов.
Работа с массивом состоит из 3 этапов:
1. Введение данных в массив.
2. Обработка данных согласно условию конкретной задачи
3. Вывод результатов или измененного массива.
В языке Паскаль для использования массивов в программе необходимо описать их в разделе описаний в произвольном порядке.
Массив — это упорядоченная структура однотипных данных, хранящая их последовательно. Доступ к элементу массива осуществляется через его индекс. Массивы описываются следующим образом:
Имя типа = ARRAY [ диапазоны индексов ] OF тип элемента массива;
В качестве типа для элементов массива можно использовать любые типы Турбо Паскаля кроме файловых. Диапазоны индексов представляют собой один или несколько диапазонов, перечисленные через запятую. В качестве диапазонов индексов нельзя использовать диапазоны с базовым типом Longint.
ПРИМЕР: Три способа описания одного и того же типа массива:
type {1} M1 = array [0..5] of integer;
M2 = array [char] of M1;
M3 = array [-2..2] of M2;
{2} M3 = array [-2..2] of array [char] of array [0..5] of integer;
{3} M3 = array [-2..2,char,0..5] of integer;
var A:M3;
{Обращаться к элементам массива можно следующим образом:}
begin
read(A[-1,’a’,3]);
read(A[1][‘x’][0]);
A[1][‘c’,1]:=100;
end.
Глубина вложенности, т.е. количество индексов, при определении массивов не ограничена. Играет роль только суммарный объем данных в программе. В стандартном режиме работы Турбо Паскаля этот объем ограничен размерами сегмента, т.е. 64 килобайта. Целиком над массивами допускается применение только операции присваивания массивов (подмассивов) одинаковых типов. Остальные операции должны выполняться поэлементно.
ПРИМЕР: Вычисление значения многочлена степени N, коэффициенты которого находятся в массиве A в точке X по схеме Горнера.
Pn(x) = A[0]*X^n + A[1]*X^(n-1) + … + A[n-1]*X + A[n] =
= (…((A[0]*X + A[1])*X + A[2])*X + … + A[n-1])*X + A[n].
program Scheme_Gorner;
type Mas = array[0..100] of integer;
var A:Mas; i,j,n:integer; x,p:real;
begin
write(‘степень многочлена = ‘); read(n);
writeln(‘введите целые коэффициенты : ‘);
for i:=0 to n do read(A[i]);
write(‘значение X = ‘); read(x);
p:=0;
for i:=0 to n do p:=p*x+A[i];
writeln(‘Pn(X) = ‘,p);
end.
Линейные массивы
Массивы представляют собой ограниченную упорядоченную совокупность однотипных величин. Каждая отдельная величина называется компонентой массива. Тип компонент может быть любым, принятым в языке ПАСКАЛЬ, кроме файлового типа. Тип компонент называется базовым типом.
Вся совокупность компонент определяется одним именем. Для обозначения отдельных компонент используется конструкция, называемая переменной с индексом или с индексами:
A[5] S[k+1] B[3,5].
В качестве индекса может быть использовано выражение. Тип индексов может быть только интервальным или перечисляемым. Действительный и целый типы недопустимы. Индексы интервального типа, для которого базовым является целый тип, могут принимать отрицательные, нулевое и положительные значения.{}
В операторной части программы один массив может быть присвоен другому, если их типы идентичны, например:
R1:=Z.
Для ввода или вывода массива в список ввода или вывода помещается переменная с индексом, а операторы ввода или вывода выполняются в цикле.
{}
Первый индекс определяет номер строки, второй — номер столбца. Двумерные массивы хранятся в памяти ЭВМ по строкам. Инициализация массивов (присвоение начальных значений всем компонентам массивов) осуществляется двумя способами.
Первый способ — с использованием типизированных констант, например:
type Dim10= Array[1..10] of Real;
const
raM10: Dim10 = ( 0, 2.1, 4, 5.65, 6.1, 6.7, 7.2, 8, 8.7, 9.3 );
При инициализации двумерных массивов значения компонент каждого из входящих в него одномерных массивов записывается в скобках:
type Dim3x2= Array[1..3,1..2] of Integer;
const
iaM3x2: Dim3x2= ( (1, 2)
(3, 4)
(5, 6) );
Второй способ инициализации — использование разновидности процедуры FillChar:
FillChar( var V; NBytes: Word; B: Byte );
Эта процедура заполняет участок памяти однобайтовым значением. Например, для обнуления массива A[1..10] of Real можно записать:
FillChar(A, 40, 0);
или
FillChar(A, SizeOf(A), 0)
Массивы |
| До сих пор мы рассматривали переменные, которые имели только одно значение, могли содержать в себе только одну величину определенного типа. Исключением являлись лишь строковые переменные, которые представляют собой совокупность данных символьного типа, но и при этом мы говорили о строке, как об отдельной величине. Вы знаете, что компьютер предназначен в основном для облегчения работы человека с большими информационными объемами. Как же, используя только переменные известных вам типов, сохранить в памяти и обработать данные, содержащие десяток, сотню, тысячу чисел или, к примеру, строк? А ведь такие задачи встречаются в любой области знания. Конечно, можно завести столько переменных, сколько данных, можно даже занести в них значения, но только представьте, какой величины будет текст такой программы, сколько времени потребуется для его составления, как много места для возможных ошибок? Естественно, об этом задумывались и авторы языков программирования. Поэтому во всех существующих языках имеются типы переменных, отвечающие за хранение больших массивов данных. В языке Паскаль они так и называются: «массивы».Массивом будем называть упорядоченную последовательность данных одного типа, объединенных под одним именем. Кстати, под это определение подходит множество объектов из реального мира: словарь (последовательность слов), мультфильм (последовательность картинок) и т. д. Проще всего представить себе массив в виде таблицы, где каждая величина находится в собственной ячейке. Положение ячейки в таблице должно однозначно определяться набором координат (индексов). Самой простой является линейная таблица, в которой для точного указания на элемент данных достаточно знания только одного числа (индекса). Мы с вами пока будем заниматься только линейными массивами, так как более сложные структуры строятся на их основе. Описание типа линейного массива выглядит так: В качестве индексов могут выступать переменные любых порядковых типов. При указании диапазона начальный индекс не должен превышать конечный. Тип элементов массива может быть любым (стандартным или описанным ранее). Описать переменную-массив можно и сразу (без предварительного описания типа) в разделе описания переменных: Примеры описания массивов: S, BB : Array [1..40] Of Real; Теперь переменные S, BB и T представляют собой массивы из сорока вещественных чисел; массив N имеет индексы символьного типа и целочисленные элементы; массив R может хранить в себе 41 число типа Word. Единственным действием, которое возможно произвести с массивом целиком — присваивание. Для данного примера описания впоследствии допустима следующая запись: Однако, присваивать можно только массивы одинаковых типов. Даже массиву T присвоить массив S нельзя, хотя, казалось бы, их описания совпадают, произведены они в различных записях раздела описания. Никаких других операций с массивами целиком произвести невозможно, но с элементами массивов можно работать точно также, как с простыми переменными соответствующего типа. Обращение к отдельному элементу массива производится при помощи указания имени всего массива и в квадратных скобках — индекса конкретного элемента. Например: Фундаментальное отличие компонента массива от простой переменной состоит в том, что для элемента массива в квадратных скобках может стоять не только непосредственное значение индекса, но и выражение, приводящее к значению индексного типа. Таким образом реализуется косвенная адресация: Такая организация работы с такой структурой данных, как массив, позволяет использовать цикл для заполнения, обработки и распечатки его содержимого. Если вы помните, с такой формой организации данных мы встречались, когда изучали строковые переменные. Действительно, переменные типа String очень близки по своим свойствам массивам типа Char. Отличия в следующем: строковые переменные можно было вводить с клавиатуры и распечатывать на экране (с обычным массивом это не проходит); длина строковой переменной была ограничена 255 символами (255 B), а для размера массива критическим объемом информации является 64 KB. Теперь рассмотрим несколько способов заполнения массивов и вывода их содержимого на экран. В основном мы будем пользоваться числовыми типами компонент, но приведенные примеры будут справедливы и для других типов (если они допускают указанные действия). Program M1; A[1]:=7; {Заполняем массив значениями (отдельно каждый компонент)} End. Как бы ни был примитивен приведенный пример, он все же иллюстрирует возможность непосредственного обращения к каждому элементу массива отдельно. Правда, никакого преимущества массива перед несколькими простыми переменными здесь не видно. Поэтому — другой способ: Program M2; A : Array [1..20] Of Integer; Begin For I:=1 To 20 Do {Организуем цикл с параметром I по всем возможным} End. Эта программа вводит с клавиатуры 20 целых чисел, а затем распечатывает их в обратном порядке. Теперь попробуйте написать такую же программу, но без использования структуры массива. Во сколько раз она станет длиннее? Кстати, введение язык Паскаль цикла с параметром было обусловлено во многом необходимостью обработки информационных последовательностей, т. е. массивов. Следующая программа заполняет массив значениям квадратов индексов элементов: Program M3; A : Array [1..N] Of Integer; Begin For I:=1 To N Do End. В дальнейшем для учебных целей мы будем использовать массивы, заданные с помощью генератора случайных чисел. В языке Паскаль случайные числа формирует функция Random. Числа получаются дробными, равномерно расположенными в интервале от 0 до 1. Выражение, дающее целое случайное число в интервале [-50,50] будет выглядеть так: Зададим и распечатаем случайный массив из сорока целых чисел: Program M4; A : Array [1..N] Of Integer; Begin For I:=1 To N Do A[I]:= Trunc(Random*101)-50 End End. С обработкой линейных массивов связано множество задач. Их мы рассмотрим на практических занятиях. |
Двумерные и многомерные массивы |
| Представьте себе таблицу, состоящую из нескольких строк. Каждая строка состоит из нескольких ячеек. Тогда для точного определения положения ячейки нам потребуется знать не одно число (как в случае таблицы линейной), а два: номер строки и номер столбца. Структура данных в языке Паскаль для хранения такой таблицы называется двумерным массивом. Описать такой массив можно двумя способами: I. Var A : Array [1..20] Of Array [1..30] Of Integer; II. Var A : Array [1..20,1..30] Of Integer; В обоих случаях описан двумерный массив, соответствующий таблице, состоящей из 20 строк и 30 столбцов. Приведенные описания совершенно равноправны.Отдельный элемент двумерного массива адресуется, естественно, двумя индексами. Например, ячейка, находящаяся в 5-й строке и 6-м столбце будет называться A[5][6] или A[5,6]. Для иллюстрации способов работы с двумерными массивами решим задачу: «Задать и распечатать массив 10X10, состоящий из целых случайных чисел в интервале [1,100]. Найти сумму элементов, лежащих выше главной диагонали.» При отсчете, начиная с левого верхнего угла таблицы, главной будем считать диагональ из левого верхнего угла таблицы в правый нижний. При этом получается, что элементы, лежащие на главной диагонали будут иметь одинаковые индексы, а для элементов выше главной диагонали номер столбца будет всегда превышать номер строки. Договоримся также сначала указывать номер строки, а затем — номер столбца. Program M5; A : Array[1..10,1..10] Of Integer; Begin S:=0; A[I,K]:=Trunc(Random*100)+1; End; End. Если модель данных в какой-либо задаче не может свестись к линейной или плоской таблице, то могут использоваться массивы произвольной размерности. N-мерный массив характеризуется N индексами. Формат описания такого типа данных: <Имя типа>=Array[<диапазон индекса1>,<диапазон индекса2>,… Отдельный элемент именуется так: |
Алгоритмы сортировки таблиц имеют большое прикладное значение: в жизни встреч. Задачи, треб. Упорядочевания данных для удобства работы с ними. По этой причине для решения задачи сортировки с помощью компьютера было придумано много разл. Алгоритмов.
Метод пузырька. Он получил свое название потому, что при его использовании некоторые из сортируемых элементов как бы всплывают в списке данных,. Подобно воздушному пузырьку в стакане воды. Программа, работающая по принципу пузырька, просматривает список от начала до конца, сравнивая вначале первый и второй элементы, затем второй и третий и т. Д. Если порядок следования двух элементов от-но друг друга оказывается неправильным, то они меняются местами. После того, кА программа доходит до конца списка, она вновь возвращается к его началу и повторяет такую процедуру до тех пор, пока все элементы не займут правильные места.
Метод корзин. При его использовании элементы раскладываются, но воображаемым коробкам. Например, если мы делаем сортировку в алфавитном порядке, то для каждой буквы можно назначить свою отдельную корзину. Затем каждая корзина делится на подкорзины, а содержащиеся в ней элементы сортируются так, чтобы каждый попал в свою подкорзину.
При решении различных задач очень часто используются таблицы — как форма представления информации, более удобная для восприятия. Поэтому обработка табличных величин часто используется при составлении различных алгоритмов.
(1 votes, average: 5,00 out of 5)