написание рекурсивной функции для вычисления нет. графиков - PullRequest
Новая
       27

написание рекурсивной функции для вычисления нет. графиков

0 голосов
/ 21 февраля 2020

Я пытаюсь написать код в python, чтобы вычислить максимальные множества графов, используя эту формулу для n вершин: 2 ** (n (n-1) / 2) (надеюсь, я написал это правильно)

Я пытаюсь сделать это с наименьшей сложностью / длительностью покупки с использованием% от 1000000007 - это рекурсивный правильный путь? или итеративный?

Я читал статью в Википедии, касающуюся экспоненциального возведения в квадрат, но не смог оттуда прыгнуть к моей проблеме: (

после некоторой работы с ручкой, ручкой и бумагой я '' мы обнаружили, что в этом случае n (n-1) / 2 всегда четно - поэтому я удаляю блок, который имеет дело с нечетными n значениями.

Это код, который до сих пор был написан для рекурсии- x для основания (2) и n для количества вершин: 

def graphs_num(x, n):
n = (n*n-n)/2
if n == 0:
    return 0
elif n == 1:
    return 1
else:
    y = graphs_num(x, n/2)
    return y*y

пока нет результатов - можете ли вы помочь, пожалуйста?

2-е редактирование: (я забыл х в последняя строка)

вот код @ ale c: 

def count(n, total=1):
n = (n*n-1)/2
if n < 2:
    return total
total *= 2 ** (n - 1) % 1000000007
return count(x, n-1, total)

count (4)

сейчас я ищу, чтобы x уже был определен как 2- так что единственная потребность входа для функции будет n

1 Ответ

0 голосов
/ 21 февраля 2020

Я не совсем знаком с этой проблемой, но на основе формулы, которую вы дали, это вернет тот же результат при n> = 0 (я предполагаю, что у вас не будет отрицательного числа вершин). 

def count(n, total=1):
    if n < 2:
        return total
    total *= 2 ** (n - 1)
    return count(n-1, total)

>>> count(5)
1024

Редактировать (пояснение):

В основном вы заметите, что значения возрастают в 2 ** n раза. 

>>> [2 ** (n * (n-1) // 2) for n in range(1, 6)]
[1, 2, 8, 64, 1024]

Это может быть проиллюстрировано следующим образом: 

f(1) = 1 = 2**0
f(2) = 2 = 2**1 * 2**0
f(3) = 8 = 2**2 * 2**1 * 2**0
...

И упрощено, чтобы показать, как его можно использовать рекурсивно: 

f(1) = 1 = 2**0
f(2) = 2 = 2**1 * f(1)
f(3) = 8 = 2**2 * f(2)
...

К этому моменту легко заметить, что отношения f(n) = 2**(n-1) * f(n-1). В рекурсивной функции строки под базовым регистром делают именно это: 

total *= 2 ** (n - 1)
return count(n-1, total)

Я умножаю сумму на 2**(n-1) и возвращаюсь к следующему значению для n, не забывая уменьшать на 1. База case гарантирует, что мы опустимся ниже 2 и вернем итог.

Теперь, если вы хотите изменить базу показателя и использовать мод, он будет вести себя соответствующим образом. 

def count(x, n, total=1):
    if n < 2:
        return total
    total *= x ** (n - 1) % 1000000007
    return count(x, n-1, total)

>>> count(2, 3)
8
>>> count(3, 3)
27
...