Блок схема заполнения массива

Все, что необходимо начинающему и опытному программисту


Главная страница
Библиотека (скачать книги)
Скачать софт
Введение в программирование
Стандарты для C++
Уроки по C#
Уроки по Python
HTML
Веб-дизайн
Ассемблер в среде Windows
ActiveX
Javascript
Общее о Линукс
Линукс — подробно
Линукс — новое
Delphi
Паскаль для начинающих
Турбопаскаль
Новости
Партнеры
Наши предложения
Архив новостей

Массивы — структурированный тип данных

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

А вот указывать для каждой ячейки отдельное имя — неудобно. Как быть?

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

Хранение однотипных данных в виде таблицы

Массив — это совокупность однотипных данных, хранящихся в последовательных ячейках памяти и имеющих общее имя. Ячейки называются элементами массива. Все элементы пронумерованы по порядку, и этот номер называется индексом элемента массива.

Все элементы массива имеют один и тот же тип. Сам массив при этом имеет имя — одно для всех элементов. Для обращения к конкретному элементу массива необходимо указать имя массива и (в квадратных скобках) индекс элемента.

Простейший вид массива — одномерный массив (рис. 8.1).

Рис. 8.1. Условное изображение одномерного массива в виде строки

А — имя массива, числа в клетках таблицы — элементы массива.
Рассмотрим запись А[3] = -8.

В этой записи:
А — имя массива,
3 — номер элемента массива (индекс),
А[3] — обозначение 3-го элемента массива,
-8 — значение 3-го элемента массива.

Основные действия по работе с массивами

Нам предстоит научиться выполнять ряд наиболее распространенных действий с массивами:

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

Описание массива на языке Паскаль

Здесь — это тип данных, который имеет каждый элемент массива, а — границы изменения индекса.

Например:
var A: array [1..10] of integer;

Здесь тип индекса — интервальный, изменяется в интервале от 1 до 10, тип данных (элементов массива) — целый.

Заполнение массива случайными числами и вывод массива на экран

Рассмотрим задачу, в которой требуется с помощью датчика случайных чисел создать одномерный массив и вывести его на экран. Блок-схема алгоритма показана на рис. 8.2.

Рис. 8.2. Блок-схема алгоритма заполнения одномерного массива случайными числами и вывода массива на экран

Пример 8.1.
Основные действия по работе с массивами

В данном примере мы заполнили массив случайными числами от 0 до 99. Это обеспечила нам функция random(100).
А если нам нужно получить случайные числа в другом диапазоне — например, не от нуля? Расчет нужно сделать такой: функция random(N) выдаст N различных чисел от 0 до N — 1. Если нам нужно, чтобы наименьшим числом диапазона было К, значит, необходимо прибавить это К к random(N). Наибольшее число, которое будет выдавать в этом случае формула random(N) + К, будет наибольшим числом диапазона.

Пусть, например, нам требуются случайные числа в диапазоне -100. +100. Считаем, сколько различных чисел в этом диапазоне: 100 положительных, 100 отрицательных и ноль. Итого 201.
Формула тут проста: вычесть из большего меньшее и прибавить 1.
Значит, N = 201, а К = -100.
То есть получаем формулу random(201) -100.

К сожалению, в таком виде формула работать не будет — при запуске программа «вылетит» с сообщением об ошибке. Это от «излишнего ума», который проявляет здесь среда Паскаль. Дело в том, что Паскаль считает тип этого выражения по функции random. А она имеет
тип word . Иными словами, беззнаковый. При попытке вычесть 100 из числа, меньшего 100, получаем отрицательный результат, что Паскаль не устраивает. Самый простой способ обойти эту напасть — паменять местами уменьшаемое (random) и вычитаемое, то есть написать: -100 + random(201). Тогда Паскаль будет считать тип этого выражения как integer по первому числу (-100), и оишбки не возникнет.

Задание 8.1.
Оформите эту программу так, чтобы задание массива и вывод его элементов на экран выполнялись в одном цикле. Вам понадобится составной оператор для тела цикла begin . end.

Задание 8.2.
Добавьте в программу задания 8.1 новый цикл вывода элементов массива в обратном порядке (начиная с последнего). Попробуйте выполнить то же задание без введения нового цикла.

Массив — это множество ячеек памяти. Поэтому любое действие с массивом заключаемся в том, чтобы перебрать все эти ячейки или, по крайней мере, какую-то их часть. Это значит, что любое действие с массивами должно содержать в себе цикл, в котором перебираются элементы массива. Если вы пишете программу с массивом и не написали цикла (for, while или repeat) — значит, вы ошиблись.

Читайте также:  Crysis где взять атомную пушку

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

Применение массивов при описании алгоритмов решения практических задач позволяет:

1. записать коротким алгоритмом работу с большим объемом информации;

2. расширить область применимости алгоритма.

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

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

При работе с массивами, каждому массиву дается имя. Работа с массивом – это работа с элементами массива. Элементу массива дается имя, соответствующее имени массива, и указывается в квадратных или круглых скобках порядковый номер этого элемента в массиве.

Очевидно, чтобы задать массив (таблицу), необходимо:

1. указать, что однотипные объекты объединены в массив (таблицу);

2. указать имя массива (таблицы), начальный и конечный порядковые номера индексов его (её) элементов;

3. указать тип значений элементов массива (таблицы).

При описании массива после имени массива будем в круглых (квадратных) скобках указывать начальный и конечный номера каждого индекса элементов массива через двоеточие. Если массив многомерный, то описание начального и конечного номеров каждого индекса элементов массива разделим запятой. Например, А(1:50) – массив, элементы которого: А(1), А(2), … , А(50); В(1:2,1:3) – массив, элементы которого: .

Пример 1. Одномерный массив Осадки (1:365) – количество осадков в течение года.

Дни года
Осадки в мм

Пример 2. Двумерный массив Расписание (1:4,1:2) – расписание уроков на 2 дня в 4 классе общеобразовательной школы.

Дни недели Номер урока Понедельник Вторник
Математика Русский язык
Русский язык Математика
Природоведение История
Физкультура Рисование

Массивы имеют размер и размерность. Размер массива – это количество элементов в данном массиве, размерностьколичество индексов, необходимых для однозначного определения места фиксированного элемента массива. Массив примера 1 имеет размерность, равную 1 (одномерный), размер – 365. Массив примера 2 имеет размерность равную 2 (двумерный), размер 2∙4=8. Элемент массива называется переменной с индексом, переменная без индекса – простой переменной. Над элементами массива можно производить те операции, которые допустимы для базового типа.

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

Пример 3. Пусть массив A – одномерный массив, имеющий 4 элемента целого типа – integer: -12, 0, 41, -131.

направление изменения индекса

1 2 3 4

-12 -131

Пример 4. Массив Q – двумерный массив, имеющий 3 строки и 4 столбца – 12 элементов вещественного типа – real:

.

направление изменения второго индекса

1 2 3 4

12,5 -18,34
-17 2,4 5,121
-45,41 -28

направление

индекса

Задача 21. Произведение элементов массива. Составьте блок-схему алгоритма нахождения произведения вещественных чисел

Решение. Смотри блок-схему алгоритма (задача 21), использована циклическая структура «while P do S».

Произведение можно находить так:

В блок-схеме вместо этой цепочки операторов запишем оператор П:=П×а(k), где k изменяется от 1 до n; k – параметр цикла. Чтобы значение первого произведения было равно a1, следует положить начальное значение П равным 1. Операторы 5-6 составляют тело цикла.

Задача 22. Произведение матриц. Составьте блок-схему нахождения произведения матрицы А на матрицу В:

, .

Решение. Смотри блок-схемы 1-3 алгоритма (задача 22).

Смотри блок-схему 1 (задача 22). Произведение матрицы А на матрицу В есть матрица-столбец; обозначим ее С.

, где , i=1,2,…,m.

Функциональный блок, вычисляющий величину c(i), обозначим S1. Смотри блок-схему 2 (задача 22).

Получать элементы c(i) при фиксированном i можно так: c(i) = c(i)+a(i,j)∙b(j), где 1£j£n, а начальное значение c(i) равно 0.

Очевидно, что функциональный блок S1 будет содержать циклическую структуру, например, структуру «repeat S until P».

Подставив детализацию блока S1 (блок-схема 2 (задача 22)) в блок-схему 1 (задача 22), получим одну циклическую структуру внутри другой, вложенные циклы – блок-схема 3(задача 22).

Задача 23. Положительные числа. Дана числовая последователь­ность a1, a2, … , an. Определите, есть ли среди ai, 1£i£n положительные числа, если да, то переменной K присвойте значение 1, в противном случае – значение 0. Составьте блок-схему алгоритма решения поставленной задачи.

Читайте также:  Что такое автосинхронизация в смартфоне

Решение. Смотри блок-схему алгоритма (задача 23).

Блок-схема алгоритма(задача 23): Блок-схема алгоритма (задача 24):

Поскольку положительный элемент может оказаться на i-ом месте, где i 0 – истинно, K получит значение 1. Проверка окончания организована так, что выход из цикла произойдёт или при i>n (положительного элемента нет), K = 0, или при i>n и K = 1 (этот элемент – последний в массиве), или при i

Задача 24.Поиск буквы. Пусть w – слово, состоящее из n букв русского алфавита: w(1), w(2), … , w(n); v – буква, относительно которой требуется установить, входит ли она в слово. Если входит, то укажите номер позиции первого вхождения буквы в слово. Составьте блок-схему алгоритма решения поставленной задачи.

Решение. Смотри блок-схему алгоритма (задача 24).

Будем просматривать последовательно все буквы данного слова. Для реализации этого используем цикл с постусловием. Если буква v не входит в слово, то выход из цикла осуществляется при i>n, где i – номер рассматриваемой буквы. Значение переменной K в этом случае равно 0. Если буква v входит в слово, выход из цикла может быть осуществлен раньше, чем i станет больше n, при K<> 0, где K – номер позиции первого вхождения буквы v в слово w.

Задача 25.Количество положительных элементов. Дана последовательность чисел a1, a2, … , an. Присвойте переменной m номер K-го положительного элемента этой последовательности. Если в последовательности положительных элементов меньше K, то переменной m присвойте значение 0. Составьте блок-схему алгоритма решения поставленной задачи.

Решение. Смотри блок-схему алгоритма (задача 25).

Подсчет количества положительных элементов массива организуем с помощью цикла с постусловием. Если положительных элементов нет или их меньше, чем K, выход из цикла осуществим при i>n, m присвоим значение 0. При l = K, где l – число положительных элементов, также реализуем выход из цикла. При этом i получит уже следующее значение. Значит, номер K-го положительного элемента на единицу меньше i.

Задача 26.Сдвиг в массиве. Переставьте вещественные элементы массива A(1:n) таким образом, чтобы они шли в следующем порядке: А(n), А(1), А(2), … , A(n-2), A(n-1), т.е. в массиве произведите сдвиг элементов на одну позицию вправо. Составьте блок-схему алгоритма решения поставленной задачи.

Решение. Смотри блок-схему алгоритма (задача 26).

Блок-схема алгоритма (задача 25): Блок-схема алгоритма (задача 26):

Задача 27.Максимальные элементы массива. Дана последовательность чисел a1, a2, … , an. Найдите количество максимальных элемен­тов последовательности и их номера. Составьте блок-схему решения поставленной задачи.

Решение. Смотри блок-схемы 1-2 алгоритма (задача 27).

В блок-схеме1 алгоритма (задача 27) первый цикл организуем для определения максимального элемента, значение которого присваивается переменной b. Начальное значение b положим равным a1. Второй цикл считает K – количество одинаковых максимальных элементов. Переменная M(K) принимает значение индекса встретившегося максимального элемента. M(K) – числовая последовательность, членами которой являются эти индексы.

Блок-схема1 алгоритма (задача 27): Блок-схема2 алгоритма (задача 27):

Блок-схема2 алгоритма (задача 27) предполагает в одном цикле на i-ом шаге определение максимального элемента из i рассмотренных, подсчет количества таких элементов и фиксирование их номеров. Если на (i+1)-ом шаге встречается больший элемент, то операторы b:=ai, K:=1, mK:=i зададут новые начальные значения переменных b, K, mK, и все вычисления будут проведены относительно нового большего элемента.

Задача 28. Дружественные числа.Дружественными числами называются два натуральных числа, таких, что каждое из них равно сумме всех натуральных делителей другого, исключая само это другое число. Числа 220 и 284 являются дружественными числами, так как сумма делителей числа 220 – это 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284, а сумма делителей числа 284 – это 1 + 2 + 4 + 71 + 142 = 220. Составьте блок-схему алгоритма нахождения дружественных чисел на отрезке [2;n].

Решение. Смотри блок-схему алгоритма (задача 28).

Блок-схема алгоритма (задача 28):

Суммы делителей чисел от 2 до n организуем в виде массива Делитель(2:n), где Делитель(k) – текущая сумма делителей числа k. Вычислим суммы делителей всех чисел от 2 до n, затем попарно сравним эти суммы, если суммы делителей чисел k и s, принадлежащих [2;n], равны, то числа k и s – дружественные, их необходимо вывести.

Некоторые пары дружественных чисел:220 и 284, 1184 и 1210, 2620 и 2924, 5020 и 5564, 6232 и 6368 и т.д.

Задача 29.Группировка. Дан массив A(1:n), элементы которого отличны от нуля. Расположите их в таком порядке, чтобы первыми были все положительные элементы, а затем – все отрицательные, причем порядок следования как положительных, так и отрицательных элементов должен сохраняться. При решении задачи нельзя заводить новую таблицу. Составьте блок-схему алгоритма решения поставленной задачи.

Решение. Смотри блок-схемы 1-2 алгоритма (задача 29).

Для решения поставленной задачи будем перебирать элементы массива с первого по n-ый. Если A(i)>0, никаких изменений в массиве не производим, увеличиваем i на единицу и переходим к исследованию следующего элемента. Если же A(i)

Дата добавления: 2015-01-26 ; просмотров: 40334 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Пример 1. Дан массиваиз 20 элементов. Вычислить сумму положительных и количество неположительных элементов массива. Начиная с этого примера, с целью улучшения наглядности, характеристики данных будем представлять в виде таблицы:

Читайте также:  The saboteur 2 дата выхода 2018

Таблица 6. Состав данных примера 1.

одномерный массив из 20 элементов

сумма положительных элементов массива

количество неположительных элементов

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

Алгоритм состоит из ввода исходных данных, цикла, в котором накапливаются sиk, и вывода результатов. Цикл управляется переменнойi, которая изменяется от 0 до 19. Перед циклом накапливаемым переменным присваиваются начальные значения (нулевые, так как прибавление нуля не изменяет сумму). Основной частью тела цикла является ветвление. Блок-схема алгоритма приведена на рис. 9. Далее приведена Паскаль-программа.

Var a:array[1..20] of real; s:real; k,i:integer;

writeln(‘Введите массив из 20 элементов’);

for i:=1 to 20 do

for i:=1 to 20 do

Пример 2. Дан массиваизNэлементов (N10). Вычислить произведение элементов массива, меньших заданного значенияс.

Таблица 7. Состав данных примера 2.

число элементов массива

одномерный массив из 10 элементов

произведение элементов массива, удовлетворяющих условию

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

количество элементов, удовлетворяющих условию

Обратите внимание, что структура массива апредполагает отведение пода десяти ячеек памяти. В программе описывается массиваиздесятиэлементов, a используются лишь первые N них. Пользователь данной программы должен помнить, что вводимое значение числа элементов массива должно находиться в интервале 1N10. Проверка корректности введенного значения N, несомненно, улучшила бы надежность программы; с целью упрощения программы мы не делаем такой проверки. Для устранения необходимости распределения памяти под массив «по максимуму» в любом алгоритмическом языке , требующем компиляции, следует использовать операторы динамического распределения памяти, но этот материал выходит за границы данного пособия.

Блок-схема алгоритма приведена на рис. 10. Алгоритм не сильно отличается от рассмотренного в примере 1. Остановимся на различиях. Для накапливания произведения необходимо перед циклом переменной р присвоить начальное значение 1 (умножение на 1 не изменяет произведение). Переменнаяkнужна для выявления ситуации отсутствия элементов, меньших заданного значения; развилка после цикла позволяет обнаружить эту ситуацию.

Далее приведена программа.

Type mas=array[1..10] of real;

используя описание a:array[1..10] of real>

writeln ( ‘Введите c, N’); readln(c,N);

writeln ( ‘Введите массив из ‘, N, ‘ элементов’);

число элементов массива

одномерный массив из 10 элементов

минимальный элемент массива

номер минимального элемента

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

Блок-схема алгоритма приведена на рис. 11. В начале каждого выполнения цикла min– это минимальное значение среди (i-1) первых элементов массива. Это значениеminсравнивается с а[i] и в результате определяется минимум из первыхiэлементов массива; при изменении текущего минимального значения запоминается номер элемента, на котором достигается текущий минимум (операторk:=i).

Если минимальное (одинаковое) значение имеют несколько элементов массива, то предложенный алгоритм выдаст наименьший из их индексов; при нестрогом неравенстве (a[i]min) будет выдаваться наибольший номер. В ситуации, когда надо определить номера всех элементов, имеющих минимальное значение, алгоритм должен иметь два цикла обработки: в первом цикле должен определяться минимум, а во втором по сравнениюmin=a[i] находиться номера элементов.

Var a:array[1..10] of real;

writeln( ‘Введите число элементов массива,N

число строк матрицы

двумерный массив размером 5*5

счетчик строк матрицы

сумма элементов i-ой строки

число строк с положи­тельной суммой эле­ментов

счетчик столбцов матрицы

Обратим внимание, что считая s простой переменноймы предполагаем, что значения сумм всех строк должны последовательно записываться в одну ячейку памяти. В этом случаев одном цикле по строкам мы должны вычислить сумму элементов строки s, вывести s и сравнить ее с нулем для вычисления k. Можно было объявить s как одномерный массив (число его элементов равно числу строк матрицы); тогда алгоритм обработки мог бы состоятьиз двух последовательных циклов по строкам:в первом из них вычислялись бы все элементы массива s и накапливалось значение k, а во втором производился бы вывод значений элементов массива s.

Таким образом, этот несложный пример иллюстрирует два очень важных положения:

выбор структуры данных (простая переменная или массив) может быть неоднозначен;

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

Блок-схема алгоритма приведена на рис. 12,а. Обратите внимание на нумерацию блоков. Нумерация нужна для сложных блок-схем, которые не умещаются на одной странице или некоторые блоки которых отображают обобщенное действие и подлежат последующей детализации. Нумерация не обязательно производится подряд, некоторые блоки могут не иметь номеров. Для рассматриваемой блок-схемы является обобщенным блок 6, его содержание раскрыто на рис.12,б. Обратите внимание на значки, с помощью которых показывается связь между исходной и подчиненной блок-схемами. Подставив в исходную блок-схему вместо блока 6 его расшифровку, получим детальный алгоритм решения задачи (см. рис.12,в).

Разработанный алгоритм имеет кратный (вложенный) цикл: тело цикла, управляемого параметром i — этот цикл называетсявнешним, — содержит цикл, управляемый параметром j,внутренний цикл.Представленная конструкция также называетсяциклом кратности (вложенности) 2. Заметим, что внешний цикл (с параметром i) обеспечивает переход от строки к строке матрицы, внутренний цикл (с параметром j) обеспечивает движение по строке (т. е. переход от столбца к столбцу при фиксированном значении i).

Оцените статью
Добавить комментарий

Adblock
detector