SEARCH AND SUBSTITUTION IN NESTED ARRAYS

Abstract


In this article simple algorithms of the solution of recursive algorithms for the simple and generalized search and replacement of elements are given in nested matrixes. The new tasks connected with nested matrixes with numerical or line elements are stated. For record of algorithms language of the environment of engineering and scientific calculations PTC Mathcad Prime is used. In the course of their decision at students the logical, algorithmic information thinking develops.

Ранее нами был предложен ряд рекурсивных алгоритмов для простого и обоб- щенного поиска и замещения элементов в гнездовых матрицах [1]. В данной ста- тье приведены более простые алгоритмы решения этих же задач, а также рассмо- трен ряд новых задач, связанных с гнездовыми матрицами с числовыми или стро- ковыми элементами. Для записи алгоритмов используется язык среды инженерных и научных вычислений PTC Mathcad Prime.Напомним, что гнездовые матрицы определяются рекурсивно как матрицы, элементами которых могут быть числа, строки и снова матрицы, причем во вло- женных матрицах элементами снова могут быть числа, строки и матрицы. Вот примеры гнездовых матриц:Поскольку матрицы являются двумерными или одномерными массивами, вме- сто слов «матрица», «простая матрица» и «гнездовая матрица» часто используют- ся слова «массив», «простой массив» и «гнездовой массив». При выводе массивы могут представляться или в раскрытом виде, как это показано выше в правых частях присваиваний, или в свернутом виде. В последнем случае виден только верхний уровень вложенности из скалярных или строковых элементов и размеры массивов следующего уровня вложенности в формах [n × m], где n - число строк и m - число столбцов. Если, например, вывести определенные выше значения переменных w1 и w2, а затем свернуть их, то получим:Гнездовой массив удобно интерпретировать деревом, корнем которого явля- ется сам массив, а от него идут дуги к элементам - скалярам, строкам, простым и гнездовым массивам. От вложенных массивов снова идут дуги к их элементам - скалярам, строкам, простым и гнездовым массивам и т. д. Листьями подобного дерева являются скаляры или строки - конечные элементы, не имеющие после- дующих ссылок. Исходя из этого, для гнездовых массивов можно использовать многие термины, применяемые для деревьев, например, «листья», «уровни вло- женности элементов», «высота». Высотой гнездового массива назовем высоту соответствующего ему дерева, т.е. максимальное из количеств дуг на путях от корня до листьев.Поскольку гнездовые массивы определяются рекурсивно, то и наиболее про- стая и эффективная их обработка реализуется рекурсивными алгоритмами [2]. Как объекты хранения данных гнездовые массивы изучены слабо, а встроенных в среду PTC Mathcad Prime средств для работы с ними мало. Ряд рекурсивных функций для работы с гнездовыми массивами предложен в работах [3-6]. В [3; 5] речь идет о функциях общего назначения, а в [4; 6] - о функциях, позволяю- щих проводить «векторные» операции, то есть действия сразу над каждым из эле- ментов массива.Простой поиск и замещение. В этом разделе сформулированы задачи простого поиска и замещения элементов в гнездовых массивах (F, G, H и I). В конце статьи в разделе I приведенного фрагмента mathcad-документа предложены рекурсивные функции для решения указанных задач.Задачи F. Элементы и их позицииF1. Создать функцию, которая по гнездовой матрице ma строит матрицу по- зиций всех элементов ma (кроме ma). Строки матрицы-результата должны иметь вид [ele pos], где ele - элемент ma, pos - позиция элемента ele в ma.F2. Сформировать функцию, обратную к функции, решающей задачу F1. То есть требуется написать функцию, которая результат вычислений по функции для F1 переводит в матрицу ma.Задачи G. Выборки элементов из гнездовой матрицы по их позициямG1. Построить функцию, возвращающую элемент гнездовой матрицы ma из позиции p. (p - простая матрица с двумя столбцами, в строках которой размеще- ны позиции по уровням вложенности).G2. Построить функцию, возвращающую вектор тех элементов гнездовой ма- трицы ma, которые расположены в позициях, указанных компонентами векто- ра vp.В следующих задачах под объектом понимается все то, что может являться элементом гнездовой матрицы, то есть любое число, строка, простой или гнез- довой массив из чисел и (или) строк.Задачи H. Вхождение объекта в гнездовую матрицуH1. Выяснить, сколько раз объект x входит как элемент в гнездовую матрицу ma. При наличии вхождений возвратить матрицу [x n], где n - количество вхож- дений, в противном случае - слово “нет”.H2. Выяснить, входит ли объект x как элемент в гнездовую матрицу ma. Если да, то возвратить вектор позиций вхождения, если нет - слово “нет”.Замечание. Если x = ma, то, вообще говоря, x не имеет позиции в ma. Будем считать, что в этом случае условно p = [“x” “y”].Задачи I. Замещение объектов в гнездовой матрицеI1. Заместить все вхождения объекта x в гнездовую матрицу ma (x  ma) объ- ектами y.I2. Заместить элемент из позиции pos гнездовой матрицы ma объектом y.I3. Пусть vpos - вектор позиций в ma, vy - вектор объектов. Заместить эле- менты гнездовой матрицы ma в позициях vpos соответствующими компонентами vy. Если в vу есть лишние объекты, то они должны игнорироваться. Если в vy не- достает объектов, то вместо них необходимо использовать последнюю компо- ненту vy.Несколько слов относительно функций решения задачи F1. Рекурсивная функ- ция elepos имеет два аргумента ma и p, где ma - гнездовая матрица и p - вспомо- гательный параметр в виде матрицы размером 1 × 2 для формирования позиций элементов при рекурсивных вызовах. Начальное значение для p роли не играет и его можно взять, например, в виде [0 0]. По elepos формируется матрица ot всех элементов ma и их позиций, включая и саму матрицу ma. Причем ma в ma позиции не имеет и включается в результат ot с любой псевдопозицией, например, [“x” “y”]. Однако по условиям задачи ma в ot вообще входить не должна. Поэтому и напи- сана головная программа maelepos, по которой реализуется обращение к elepos и из сформированной матрицы ot удаляется начальная строка с ma. Аргумент maelepos принимает лишь исходную гнездовую матрицу ma. Краткие замечания по функциям, решающим другие задачи, даны на самом фрагменте mathcad- документа.Обобщенный поиск и замещение. В этом разделе сформулированы задачи обоб- щенного поиска и замещения элементов в гнездовых массивах (J, K и L). В кон- це статьи в разделе II приведенного фрагмента mathcad-документа предложены рекурсивные функции для решения указанных задач. Основополагающей из них является функция equG(ma1, ma2), играющая роль оператора «обобщенного ло- гического равенства», т.е. проверяющая, являются ли два гнездовых массива ma1 и ma2 обобщенно равными.Прежде чем формулировать решаемые задачи, нам необходимо ввести понятие обобщенного равенства двух гнездовых массивов A и B. К этому и приступим.Будем считать, что в A или в B могут быть элементы, равные любому другому элементу. Прежде всего, надо условиться об обозначении таких «обобщенных» элементов. Если в A и (или) в B нет специальных элементов NaN (Not а Number), то данный скаляр подходит для наших целей. При наличии в A или в B элементов NaN в качестве обобщенного значения может быть взято любое достаточно боль- шое число или какая-либо строка, которые не встречаются ни в A, ни в B. Будем считать, что для обобщенных значений используется именно скаляр NaN.Определение 1. Два гнездовых массива ma1 и ma2 обобщенно равны, если у них на верхнем уровне вложенности совпадают количества строк и столбцов, а все их соответствующие друг другу элементы равны, причем считается, что при любых a из ma1 и b из ma2: (NaN = b) = 1, (a = NaN) = 1, (NaN = NaN) = 1 (заметьте, что в PTC Mathcad (NaN = NaN) = 0!) [1. С. 465].Определение 2. Пусть объект obj - скаляр, строка, простой или гнездовой мас- сив, ma - простой или гнездовой массив. Говорят, что obj обобщенно входит в ma, если obj обобщенно равно ma или obj обобщенно равно какому-либо элемен- ту ma на любом его уровне вложенности. Поиск обобщенных вхождений obj в ma будем называть обобщенным поиском [1. С. 465].Задача J. Обобщенное равенствоПостроить функцию, проверяющую, являются ли два объекта (числа, строки, простые или гнездовые массивы) обобщенно равными.Задачи K. Обобщенные вхождения объектов в гнездовые массивыK1. Выяснить, сколько раз объект x обобщенно входит в гнездовую матрицу ma. При наличии таких вхождений возвратить матрицу [x n], где n - количество вхождений x в ma, при отсутствии вхождений - слово “нет”.K2. Выяснить, имеются ли обобщенные вхождения объекта в гнездовую ма- трицу ma. Если да, то возвратить вектор позиций вхождения, если нет - слово “нет”.K3. Выяснить, имеются ли обобщенные вхождения объекта в гнездовую ма- трицу ma. Если да, то возвратить матрицу позиций вхождения, строки которой имеют вид [ele pos], где ele - образ x в ma, pos - позиция ele в ma. При отсутствии вхождений должно возвращаться слово “нет”.Задачи L. Замещение объектов в гнездовой матрицеL1. Заменить все обобщенные вхождения объекта x в гнездовой матрице ma(xma) объектами y.L2. Заменить элемент из позиции pos гнездовой матрицы ma объектом y.L3. Пусть vpos - вектор позиций в ma, vy - вектор объектов. Заменить эле- менты гнездовой матрицы ma в позициях vpos соответствующими компонентами vy. Если в vу есть лишние объекты, то они должны игнорироваться, если в vy не- достает объектов, то вместо них необходимо использовать последнюю компо- ненту vy.Замечание. Задачи L2 и L3 связаны с замещением элементов в гнездовых мас- сивах на конкретных позициях. Поскольку такое замещение не опирается на на- личие или отсутствие в массиве элементов NaN, для решения L2 и L3 нет необ- ходимости строить новые функции. Решать их можно ранее созданными функ- циями repo и repov.Фрагмент (1-8)Фрагмент (2-8)*Фрагмент (3-8)Фрагмент (4-8)Фрагмент (5-8)Фрагмент (6-8)Фрагмент (7-8)Фрагмент (8-8)Функции для решения задач F-L. В этом пункте на восьми фрагментах mathcad- документа представлены функции для решения перечисленных ранее задач на простой и обобщенный поиск и замещение. Соответствие имен задач и функций таково: F1 - elepos, maelepos; F2 - resto; G1 - pick, pickv; G2 - pickvr; H1 - in, H2 - inv; I1 - re; I2 - repo, I3 - repov; J - equG, K1 - inG, K2 - invG, K3 - inmG, L1 - reG, L2 - repo, L3 - repov.

S G Grigoriev

Sheremetyevskaya str., 29, Moscow, Russia, 127521

A R Esayan

Tula state pedagogical university of L.N. Tolstoy

Prospekt Lenina, 125, Tula, Russia, 300026

Views

Abstract - 167

PDF (Russian) - 19


Copyright (c) 2016 Григорьев С.Г., Есаян А.Р.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.