10 классы_информатика
Скачать:
| Вложение | Размер |
|---|---|
 programmirovanie_massivov.docx | 138.58 КБ |
| sortirovka_massivov.docx | 20.26 КБ |
Предварительный просмотр:
Программирование массивов.
Каждая ячейка содержит элемент массива. Элементы нумеруются по порядку, но необязательно начиная с единицы. Порядковый номер элемента массива называется индексом этого элемента. Индексы элементов массива обычно целые числа.
Существуют различные виды массивов по размерности, в школьном курсе вы познакомитесь с двумя – одномерными и двумерными.
Массив состоящий из нескольких строк одинаковой длины называется двумерным или прямоугольным.
Массив состоящий из одной строки называется одномерным или линейным.
5.1. Характеристики массива
Массив имеет следующие характеристики:
имя - название массива;
индекс - номер элемента в массиве;
элемент - каждое значение в массиве;
размер - количество элементов в массиве.
5.1.1. Описание линейных массивов на языке Pascal
Массив задаётся в разделе Var. Формат описания:
(где array и of – ключевые слова, размер: [n1 . . n2 ], n1- номер первого элемента, n2-номер последнего элемента массива)
Пример: spisok: array [1..5] of string; (массив с именем spisok состоит из 5 элементов строкового типа).
5.1.2. Способы заполнения массивов
В большинстве случаев для обработки массивов используются циклы. В цикле имеется возможность поочередно перебрать все элементы массива
Заполнение массива можно производить:
- с клавиатуры;
- через датчик случайных чисел;
- через оператор присваивания (по формуле)
Способ 1c клавиатуры | Ввод: For i:=1 to n do readln(a[i]); | Вывод: For i:=1 to n do writeln(a[i]); |
Способ 2 Через датчик или генератор случайных чисел RANDOM(i). | Ввод: For i:=1 to n do readln(a[i]); | Вывод: For i:=1 to n do writeln(a[i]); |
Если требуется, чтобы значения элементов массива выбирались из определенного интервала [a,b], то a+Random(b-a+1); | ||
Способ 3 через оператор присваивания (по формуле) | For i:=1 to n do а[i]:=i*4; | |
Рассмотрим несколько способов заполнения массивов и вывода их содержимого на экран.
СПОСОБ1 Program M1; Var A : Array [1..20] Of Integer; Begin A[1]:=7; {Заполняем массив значениями (отдельно каждый компонент)} A[2]:=32; A[3]:=-70; .............. {Трудоемкая задача?} A[20]:=56; Writeln(A[1],A[2],A[3], ?,A[20]) End. Как бы ни был примитивен приведенный пример, он все же иллюстрирует возможность непосредственного обращения к каждому элементу массива отдельно. Правда, никакого преимущества массива перед несколькими простыми переменными здесь не видно. | СПОСОБ 2 Program M2; Var A : Array [1..20] Of Integer; I : Integer; Begin For I:=1 To 20 Do {Организуем цикл с параметром I по всем возможным} Readln(A[I]); {значениям индексов и вводим A[I] с клавиатуры } For I:=20 Downto 1 Do {Распечатываем массив в обратном порядке} Write(A[I],' '); End. Эта программа вводит с клавиатуры 20 целых чисел, а затем распечатывает их в обратном порядке. Теперь попробуйте написать такую же программу, но без использования структуры массива. Во сколько раз она станет длиннее? Кстати, введение в язык Паскаль цикла с параметром было обусловлено во многом необходимостью обработки информационных последовательностей, т. е. массивов. |
Для ввода больших массивов удобно пользоваться генератором случайных число.
5.1.3. Генератор случайных чисел
В языке программирования Паскаль для генерации случайных чисел в заданных диапазонах используется функция random. Перед ее использованием обычно выполняется процедура инициализации датчика случайных чисел - randomize; иначе программа всегда будет выдавать один и тот же результат. Randomize задает начальное значение последовательности, от которого вычисляются все последующие. При каждом запуске программы это значение будет разным, а значит и результат работы функции random будет различным.
Функция random генерирует случайное число в диапазоне от 0 (включительно) до единицы. Если в скобках указан аргумент, то от 0 до значения указанного в скобках (не включая само значение). Так выражение random (10), говорит о том, что будет получено любое число в диапазоне [0, 10). Если требуется получать значения в каком-либо другом диапазоне (не от нуля), то прибегают к математической хитрости. Например, чтобы получить случайное число от -100 до 100 достаточно записать такое выражение: random (200) – 100.
В результате, сначала будет получено число из диапазона [0, 199], а затем из него будет вычтена сотня. И если случайное число было меньше 100, то результат выражения будет отрицательным.
СПОСОБ 3 | |
В примере программы сначала с помощью процедуры randomize инициализируется датчик случайных чисел. Далее переменной n присваивается случайное значение в диапазоне [5, 12). Значение переменной n используется для определения количества итераций цикла for. В цикле for генерируются случайные числа в диапазоне [0, 50) и выводятся на экран. | var n, i, x: integer; begin randomize; n := random (7) + 5; for i := 1 to n do begin x := random (100) - 50; write (x:5) end; readln; end. |
Выполнить практическую работу № 8.
Если в описании массива заданы два индекса, то это двумерный массив. Такой массив соответствует понятию прямоугольной таблицы (матрицы). Чтобы определенным образом задать какую-либо ячейку двумерной таблицы, нужно указать номер строки и номер столбца.
Формат описания:
где n1 и n2 – начальное и конечное значения первого индекса;
m1, m2 – начальное и конечное значения второго индекса.
Для ввода и для вывода двумерных массивов используются вложенные циклы:
For i:=l to 5 do
For j:=l to 5 do Read(Matrix[i,j]);
Здесь i u j - счетчики целочисленного типа, объявляемые в разделе var. Алгоритм имеет вид:
При использовании вложенных циклов последовательно идет работа с элементами первой строки, потом второй, третьей, четвертой, пятой. Вывод матрицы на экран:
For i:=1 to 5 do begin
For j: =1 to 5 do
Write(Matrix[i j],' ');
WriteLn;
End.
Выполните практическую работу № 9.
Практика по теме «Программирование массивов»
Практическая работа № 8. Обработка одномерного массива в программе.
Основные задачи по работе с одномерными массивами:
- Нахождение минимального (максимального) элемента массива;
- Нахождение суммы (произведения) элементов массива;
- Нахождение количества элементов массива по определенному условию;
- Упорядочивание элементов массива по убыванию (возрастанию).
Решение задач основных типов.
Пример 1. Нахождение наибольшего элемента в массиве, Известно, что 16 детишек ясельной группы разобрали все кубики. Определить у какого ребенка наибольшее количество кубиков.
Для описания списка количества кубиков у детишек воспользуемся типом массива KUB, для задания количества кубиков каждого из ребенка – переменной SOTR. Количество кубиков вводиться с клавиатуры.
Текст программы к приведенному примеру:
Program pr1; sort=KUB; Begin | кубиков ’, i,’ –го ребенка, шт.’); if max кубиков=’,max:10:2,’ шт.’); |
К данной программе составить блок-схему. | |
В этой программе реализован следующий алгоритм. В начальный момент предполагается, что наибольшее количество кубиков у первого из ребят. Далее эта величина сравнивается с количеством кубиков остальных ребят, и, если найдется количество, превосходящее, чем предполагаемый максимум, то переменной Мах присваивается это значение.
Аналогично может быть найден и наименьший элемент в массиве. Для этого достаточно заменить в изложенной программе условие max
Пример 2. Дан одномерный массив. Найти количество элементов массива, равных заданному k.
Program pr_3; Const m=100; Var mas: array [1..m] of integer; I, k, n, kol: integer; Begin Write(‘введите размерность массива n=’); read(n); Writeln; Writeln(‘введите значение к=’); read (k); kol:=0; Randomize; For i:=1 to n do begin | Mas[i]:=random(i); Write (mas[i], ‘ ‘); If mas[i]=k then kol:=kol+1; End; Writeln; Writeln; Writeln (‘количество элементов, равных ‘, k,’ равно ‘, kol); Readkey; Readln; End. |
К данной программе составить блок-схему. | |
Пример 3. Дан одномерный массив. Упорядочить его элементы в порядке возрастания. {Сортировка массива выбором (в порядке возрастания). Идея решения: пусть часть массива (по K-й элемент включительно) отсортирована. Нужно найти в неотсортированной части массива минимальный элемент и поменять местами с (K+1)-м}
Program Sortirovka; | For I := 1 To N - 1 Do |
Контрольный пример: N = 10; элементы массива - 1, 2, 2, 2, -1, 1, 0, 14, 5, 3. К данной программе составить блок-схему. | |
Задания
1. Необходимо задать массив размерностью 5, заполнить массив случайными числами в интервале [-1,1] и вывести элементы на экран: определить три позиции для вывода каждого элемента.
2.Вычислить и распечатать первые 20 чисел Фибоначчи.
3 Дан массив из 10 целочисленных элементов. Найти количество отрицательных и вывести количество на экран.
4. Найти минимальное и максимальное из n введенных чисел (массива) и их индексы.
5. Дано целое число N и набор из N целых чисел. Вывести в том же порядке все четные числа из данного набора и количество K таких чисел.
Вопросы:
- Дайте определение массива.
- Какие массивы называются линейными и прямоугольными?
- Что такое индекс массива, размерность массива?
- Как описать одномерный массив в программе?
Предварительный просмотр:
Сортировка массивов
Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке.
Вообще говоря, это большая и сложная тема, в которой известно много различных алгоритмов. Критерии оценки эффективности этих алгоритмов могут включать следующие параметры:
- количество шагов алгоритма, необходимых для упорядочения;
- количество сравнений элементов;
- количество перестановок, выполняемых при сортировке.
Мы рассмотрим только одну простейшую схему сортировки - Метод "пузырька".
"Пузырьковая" сортировка- простой, не оптимальный, но самый понятный алгоритм. Представьте, что мы построились случайным образом в шеренгу и нам надо перестроиться по росту, меняя пары людей между собой.
Пойдем вдоль шеренги и найдем самого высокого(сортировка по убыванию) и поменяем его с первым. потом пойдем от второго , найдем самого высокого среди оставшихся и тоже поменяем. Можете потренироваться на людях или предметах чтобы было понятно.:)
В итоге наша шеренга буде такой, о которой мечтает физрук на уроке физкультуры.
Что нужно знать для того, чтобы закодить сортировку?
1. как поменять местами 2 переменных через третью.
2. Как работает цикл
3. как ввести и вывести массив данных
Метод "пузырька"
По-видимому, самым простым методом сортировки является так называемый метод "пузырька". Чтобы уяснить его идею, представьте , что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:
- если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;
- при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .
В результате наибольший элемент оказывается в самом верху массива.
Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е на вторую сверху позицию, и т.д.
Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j-го прохода не проверяются элементы, стоящие на позициях выше j.
Сортировка по возрастанию
var
i,j,c:integer;
mas:array[1..10] of integer;
begin
{заполнение массива случайными числами}
for i:=1 to 10 do mas[i]:=random(100);
{сортировака массива}
for i:=1 to 10 do
for j:=1 to 10 do
if mas[i]>mas[j] then
begin
c:=mas[i];
mas[i]:=mas[j];
mas[j]:=c;
end;
{вывод массива}
for i:=1 to 10 do write(mas[i], ' ');
end.
К данной программе составить блок-схему, выполнить программу на компьютере результат записать в тетрадь
Задание .
1.Выполнить сортировку данного массива по убыванию.
2. Выполнить сортировку только четных элементов массива (нечетные элементы остаются на своих местах)