Кучи Пелла, точно так же, как кучи Фибоначчи

Question

Есть ли какая-нибудь куча, основанная на последовательности Пелла (или числе Пелла) вместо числа Фибоначчи (например, кучи Фибоначчи)?

Answer 1

Стоит отметить, что куча Фибоначчи на самом деле не "основана" на числе Фибоначчи (ее структура совсем не выглядит так, как будто она связана с числами Фибоначчи); это анализ кучи Фибоначчи, где появляются числа Фибоначчи. Вы используете последовательность Фибоначчи, чтобы связать число деревьев в куче из n элементов со значением, связанным с n-м числом Фибоначчи, тем самым демонстрируя, что поведение некоторых операций в худшем случае не может быть хуже, чем O(log n).

Что касается вашего вопроса о числах Пелла, я не знаю ни о каких структурах данных, которые полагаются на последовательность (я фактически не встречал эту последовательность раньше!). Последовательность Фибоначчи возникает так много вместо других подобных рекуррентных последовательностей из-за множества интересных свойств последовательности, которые не обязательно верны для других рекуррентных отношений; Я написал об этом в своем ответе на этот вопрос. Я бы предположил, что числа Пелла могут быть использованы в некоторых структурах данных или анализах, но структура, необходимая для удовлетворения рекуррентного отношения, кажется, не возникает ни в каких структурах данных или алгоритмах, с которыми я сталкивался.

РЕДАКТИРОВАТЬ: Я нашел интересную статью с использованием чисел Пелла в анализе некоторых последовательностей значений, которые вы можете найти здесь.

Надеюсь это поможет!

Answer 2

# Pell number using python without any functions
import sys

num = int(input("Enter a positive number: "))
if num <= 0:
  sys.exit("invalid input please try again")
a = 0
b = 1
c = 0
if num == 1:
  print("Pell number is {}".format(a))
elif num == 2:
  print("Pell number is {}".format(b))
elif num >= 3:
  counter = 3
while (counter <= num):
  answer =  a + (b*2)
  a = b
  b = answer
  counter +=1
print("Pell number is {}".format(answer))