Рекурсивное построение верхней треугольной матрицы

Я ломал голову, пытаясь придумать рекурсивный способ построить следующую матрицу в python. Это довольно сложная задача без указателей. Может ли кто-нибудь помочь мне?

Рекурсивное построение верхней треугольной матрицы

Рекурсия следующая:

T0 = 1,
Tn+1 = [[Tn, Tn],
        [ 0, Tn]]

Я пробовал много итераций некоторой рекурсивной функции, но я не могу обдумать это.

def T(n, arr):
    n=int(n)
    if n == 0:
        return 1
    else:
        c = 2**(n-1)
        Tn = np.zeros((c,c))
        Tn[np.triu_indices(n=c)] = self.T(n=n-1, arr=arr)
        return Tn
arr = np.zeros((8,8))
T(arr=arr, n=3)

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

Maus 21.05.2019 22:12

Любые указатели на то, как это сделать? Я никогда не имел дело с рекурсией.

Patrickens 21.05.2019 22:32

если вы погуглите рекурсию python, один из первых результатов будет таким: realpython.com/python-thinking-recursively/…, который описывает, как сделать рекурсию в python

Maus 21.05.2019 22:36

Спасибо. Я уже нашел этот сайт, но эти примеры кажутся тривиальными по сравнению с построением этой матрицы. Интересно, как вы создаете Tn и как вы анализируете Tn+1.

Patrickens 21.05.2019 22:38
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
2
4
225
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Сделать это несложно, но нужно быть осторожным со значением нуля в рекурсии. Это не совсем точно для больших значений n:

Tn+1 = [[Tn, Tn],
        [ 0, Tn]]

Поскольку этот ноль может представлять собой блок нулей, например, на второй итерации, у вас есть это:

[1, 1, 1, 1],
[0, 1, 0, 1],
[0, 0, 1, 1],
[0, 0, 0, 1]

Эти четыре нуля в левом нижнем углу представлены одним нулем в формуле. Блок нулей должен быть такой же формы, как блоки вокруг него.

После этого нужно заставить Numpy привести вещи в правильный порядок и форму для вас. numpy.block действительно удобен для этого и делает его довольно простым:

import numpy as np
def makegasket(n):
    if n == 0:
        return np.array([1], dtype=int)
    else:
        node = makegasket(n-1)
        return np.block([[node, node], [np.zeros(node.shape, dtype=int), node]])


makegasket(3)

Результат:

array([[1, 1, 1, 1, 1, 1, 1, 1],
       [0, 1, 0, 1, 0, 1, 0, 1],
       [0, 0, 1, 1, 0, 0, 1, 1],
       [0, 0, 0, 1, 0, 0, 0, 1],
       [0, 0, 0, 0, 1, 1, 1, 1],
       [0, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 1]])

Если вы используете больший n, вам может понравиться matplotlib.pyplot.imshow для отображения:

from matplotlib.pyplot import imshow

# ....

imshow(makegasket(7))

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

def build_matrix(n):
    size = 2**n

    # Depending on the application, even dtype=np.bool might work
    matrix = np.zeros((size, size), dtype=np.int)

    # This is t[0]
    matrix[0, -1] = 1

    for i in range(n):
        k = 2**i
        matrix[:k, -2 * k:-k] = matrix[k:2 * k, -k:] = matrix[:k, -k:]

    return matrix

Просто для удовольствия, вот график временных результатов для этой реализации по сравнению с @Ответ Марка Мейера. Это показывает небольшое преимущество во времени (а также в памяти) при использовании циклического подхода в этом случае:

Оба алгоритма исчерпали память на моей машине около n=15, что не так уж удивительно.

ха-ха, да, я нашел вашу реализацию, но поскольку в документе упоминается рекурсия, я хотел увидеть ее, черт возьми. Я не нашел функцию np.block, которая делает этот фрагмент таким красивым! Спасибо за сравнение+редактирование.

Patrickens 22.05.2019 10:39

Другие вопросы по теме