Я ломал голову, пытаясь придумать рекурсивный способ построить следующую матрицу в 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)
Любые указатели на то, как это сделать? Я никогда не имел дело с рекурсией.
если вы погуглите рекурсию python, один из первых результатов будет таким: realpython.com/python-thinking-recursively/…, который описывает, как сделать рекурсию в python
Спасибо. Я уже нашел этот сайт, но эти примеры кажутся тривиальными по сравнению с построением этой матрицы. Интересно, как вы создаете Tn и как вы анализируете Tn+1.
Сделать это несложно, но нужно быть осторожным со значением нуля в рекурсии. Это не совсем точно для больших значений 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, которая делает этот фрагмент таким красивым! Спасибо за сравнение+редактирование.
что ты пробовал? ваш вопрос в его нынешнем виде не указывает, что вы пытались и почему это не удалось.