ПОИСК И ЗАМЕЩЕНИЕ В ГНЕЗДОВЫХ МАССИВАХ

Полный текст

Ранее нами был предложен ряд рекурсивных алгоритмов для простого и обоб- щенного поиска и замещения элементов в гнездовых матрицах [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.

Об авторах

С Г Григорьев

Московский городской педагогический университет

Шереметьевская ул., 29, Москва, Россия, 127521

А Р Есаян

Тульский государственный педагогический университет им. Л.Н. Толстого

пр. Ленина, 125, Тула, Россия, 300026

Список литературы