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

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

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 – параметр цикла. Чтобы значение первого произведения было равно a₁, следует положить начальное значение П равным 1. Операторы 5-6 составляют тело цикла.

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

, .

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

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

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

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

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

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

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

Задача 23. Положительные числа. Дана числовая последователь­ность a₁, a₂, … , a_n. Определите, есть ли среди a_i, 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.Количество положительных элементов. Дана последовательность чисел a₁, a₂, … , a_n. Присвойте переменной 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.Максимальные элементы массива. Дана последовательность чисел a₁, a₂, … , a_n. Найдите количество максимальных элемен­тов последовательности и их номера. Составьте блок-схему решения поставленной задачи.

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

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

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

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

Задача 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 ; просмотров: 40335 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

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

Таблица 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).

Двумерный массив (матрица) представляет собой таблицу, на пересечении строк и столбцов которой располагаются элементы. Каждый элемент имеет два индекса. Первый индекс обычно обозначается буквой i и указывает номер строки, в которой расположен элемент. Второй индекс обозначается буквой j и указывает номер столбца, в котором расположен элемент (рис 6.1). Размерность двумерного массива задается двумя числами: M – количество строк и N – количество столбцов.

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

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

Ввод двумерного массива (рис. 6.2), также как и одномерного выполняется в два этапа. Вначале вводится размерность массива (блок 1), а затем значения для каждого элемента. Внешний цикл (блок 2) при i =1 «выбирает» 1-ю строку массива. Внутренний цикл (блок 3) перебирает все столбцы массива, т.е. поочередно выбираются элементы A_1,1, А_1,2, А_1,3 и т.д. до конца 1-й строки и вводятся их значения (блок 4). После выхода из внутреннего цикла происходит возврат в блок 2, где выбирается 2-я строка массива, для которой внутренний цикл опять переберет поочередно все элементы A_2,1, А_2,2, А_2,3 и т.д. Таким образом, элементы двумерного массива будут перебираться по строкам.

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

Если в блок-схеме на рис. 6.2. поменять местами параметры внешнего и внутреннего циклов, т.е. внешний цикл сделать по параметру j, а внутренний – по параметру i, то элементы массива будут перебираться по столбцам.

Пример 6.1. Сформировать вектор В размерностью M, каждый элемент которого равен количеству нулевых элементов соответствующей строки матрицы А размерностью M на N.

Как видно из условия количество элементов вектора В равно количеству строк матрицы А. Для решения поставленной задачи необходимо организовать построчный перебор элементов двумерного массива. Внешним должен быть цикл по параметру i, внутренним цикл по параметру j. Это даст возможность после завершения обработки каждой строки формировать элементы одномерного массива В. Блок-схема алгоритма приведена на рис. 6.3.

Блоки 2-5 вводят исходный двумерный массив А, описанным выше способом. Затем организовывается внешний цикл «Для» по параметру i на основе блока модификации (блок 6), который будет одновременно перебирать строки массива А и элементы одномерного массива В. С целью оптимизации алгоритма не вводится отдельная переменная для хранения количества нулевых элементов в каждой строке матрицы. Вместо неё будут использоваться непосредственно элементы массива В.

Для выбранной во внешнем цикле i-й строки обнуляется i-й элемент массива В (блок 7). Затем организовывается внутренний цикл «Для» по параметру j (блок 8), перебирающий столбцы массива А, т.е. элементы i-й строки. Каждый элемент проверяется на равенство нулю (блок 9), и в случае выполнения условия происходит увеличение счетчика нулевых элементов i-й строки, значение которого хранится в элементе B_i (блок 10). После завершения обработки строки (выхода из внутреннего цикла) происходит вывод i-го элемента массива В (блок 11) и переход к следующей строке. Обработав все строки двумерного массива А, алгоритм завершит свою работу.

Пример 6.2. Сформировать вектор В размерностью N, каждый элемент которого равен среднему арифметическому значению элементов соответствующего столбца матрицы А размерностью M на N.

В данном примере количество элементов вектора В равно количеству столбцов матрицы А. Для решения задачи необходимо организовать перебор элементов двумерного массива по столбцам. Внешним должен быть цикл по параметру j, внутренним цикл по параметру i. Это даст возможность после завершения обработки каждого столбца вычислять соответствующие элементы одномерного массива В. Блок-схема алгоритма приведена на рис. 6.4.

Ввод элементов массива А осуществляется построчно (блоки 2-5). Во внешнем цикле по параметру j выбирается столбец массива А (блок 6), для него обнуляется значение суммы, которая будет хранится в соответствующем j-м элементе массива В (блок 7). Внутренний цикл по параметру i (блок 8) выполняет перебор и суммирование всех элементов текущего j-го столбца массива А (блок 9). После завершения работы внутреннего цикла в j-м элементе массива В вычисляется среднее арифметическое значение элементов j-го столбца массива А (блок 10), которое затем выводится (блок 11). На этом заканчивается тело внешнего цикла и происходит переход на его начало, где выбирается следующий столбец матрицы. Обработав все столбцы двумерного массива А, алгоритм завершит свою работу.

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

Пример 6.3. В каждой строке квадратной матрицы А размерностью N на N найти наибольший элемент и поменять его местами с элементом главной диагонали.

Главной диагональю квадратной матрицы называется диагональ, соединяющая верхний левый угол матрицы с правым нижним углом. Для элементов, расположенных на главной диагонали соблюдается соотношение между индексами: i=j. Для элементов расположенных ниже главной диагонали: i > j. Для элементов расположенных выше главной диагонали: i

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась – это был конец пары: "Что-то тут концом пахнет". 8404 – | 8022 – или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

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

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

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 – параметр цикла. Чтобы значение первого произведения было равно a₁, следует положить начальное значение П равным 1. Операторы 5-6 составляют тело цикла.

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

, .

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

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

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

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

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

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

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

Задача 23. Положительные числа. Дана числовая последователь­ность a₁, a₂, … , a_n. Определите, есть ли среди a_i, 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.Количество положительных элементов. Дана последовательность чисел a₁, a₂, … , a_n. Присвойте переменной 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.Максимальные элементы массива. Дана последовательность чисел a₁, a₂, … , a_n. Найдите количество максимальных элемен­тов последовательности и их номера. Составьте блок-схему решения поставленной задачи.

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

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

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

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

Задача 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 ; просмотров: 40335 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

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

Таблица 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).

Двумерный массив (матрица) представляет собой таблицу, на пересечении строк и столбцов которой располагаются элементы. Каждый элемент имеет два индекса. Первый индекс обычно обозначается буквой i и указывает номер строки, в которой расположен элемент. Второй индекс обозначается буквой j и указывает номер столбца, в котором расположен элемент (рис 6.1). Размерность двумерного массива задается двумя числами: M – количество строк и N – количество столбцов.

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

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

Ввод двумерного массива (рис. 6.2), также как и одномерного выполняется в два этапа. Вначале вводится размерность массива (блок 1), а затем значения для каждого элемента. Внешний цикл (блок 2) при i =1 «выбирает» 1-ю строку массива. Внутренний цикл (блок 3) перебирает все столбцы массива, т.е. поочередно выбираются элементы A_1,1, А_1,2, А_1,3 и т.д. до конца 1-й строки и вводятся их значения (блок 4). После выхода из внутреннего цикла происходит возврат в блок 2, где выбирается 2-я строка массива, для которой внутренний цикл опять переберет поочередно все элементы A_2,1, А_2,2, А_2,3 и т.д. Таким образом, элементы двумерного массива будут перебираться по строкам.

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

Если в блок-схеме на рис. 6.2. поменять местами параметры внешнего и внутреннего циклов, т.е. внешний цикл сделать по параметру j, а внутренний – по параметру i, то элементы массива будут перебираться по столбцам.

Пример 6.1. Сформировать вектор В размерностью M, каждый элемент которого равен количеству нулевых элементов соответствующей строки матрицы А размерностью M на N.

Как видно из условия количество элементов вектора В равно количеству строк матрицы А. Для решения поставленной задачи необходимо организовать построчный перебор элементов двумерного массива. Внешним должен быть цикл по параметру i, внутренним цикл по параметру j. Это даст возможность после завершения обработки каждой строки формировать элементы одномерного массива В. Блок-схема алгоритма приведена на рис. 6.3.

Блоки 2-5 вводят исходный двумерный массив А, описанным выше способом. Затем организовывается внешний цикл «Для» по параметру i на основе блока модификации (блок 6), который будет одновременно перебирать строки массива А и элементы одномерного массива В. С целью оптимизации алгоритма не вводится отдельная переменная для хранения количества нулевых элементов в каждой строке матрицы. Вместо неё будут использоваться непосредственно элементы массива В.

Для выбранной во внешнем цикле i-й строки обнуляется i-й элемент массива В (блок 7). Затем организовывается внутренний цикл «Для» по параметру j (блок 8), перебирающий столбцы массива А, т.е. элементы i-й строки. Каждый элемент проверяется на равенство нулю (блок 9), и в случае выполнения условия происходит увеличение счетчика нулевых элементов i-й строки, значение которого хранится в элементе B_i (блок 10). После завершения обработки строки (выхода из внутреннего цикла) происходит вывод i-го элемента массива В (блок 11) и переход к следующей строке. Обработав все строки двумерного массива А, алгоритм завершит свою работу.

Пример 6.2. Сформировать вектор В размерностью N, каждый элемент которого равен среднему арифметическому значению элементов соответствующего столбца матрицы А размерностью M на N.

В данном примере количество элементов вектора В равно количеству столбцов матрицы А. Для решения задачи необходимо организовать перебор элементов двумерного массива по столбцам. Внешним должен быть цикл по параметру j, внутренним цикл по параметру i. Это даст возможность после завершения обработки каждого столбца вычислять соответствующие элементы одномерного массива В. Блок-схема алгоритма приведена на рис. 6.4.

Ввод элементов массива А осуществляется построчно (блоки 2-5). Во внешнем цикле по параметру j выбирается столбец массива А (блок 6), для него обнуляется значение суммы, которая будет хранится в соответствующем j-м элементе массива В (блок 7). Внутренний цикл по параметру i (блок 8) выполняет перебор и суммирование всех элементов текущего j-го столбца массива А (блок 9). После завершения работы внутреннего цикла в j-м элементе массива В вычисляется среднее арифметическое значение элементов j-го столбца массива А (блок 10), которое затем выводится (блок 11). На этом заканчивается тело внешнего цикла и происходит переход на его начало, где выбирается следующий столбец матрицы. Обработав все столбцы двумерного массива А, алгоритм завершит свою работу.

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

Пример 6.3. В каждой строке квадратной матрицы А размерностью N на N найти наибольший элемент и поменять его местами с элементом главной диагонали.

Главной диагональю квадратной матрицы называется диагональ, соединяющая верхний левый угол матрицы с правым нижним углом. Для элементов, расположенных на главной диагонали соблюдается соотношение между индексами: i=j. Для элементов расположенных ниже главной диагонали: i > j. Для элементов расположенных выше главной диагонали: i

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась – это был конец пары: "Что-то тут концом пахнет". 8404 – | 8022 – или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно