algoritması - bir fonksiyonu aşağıdaki işlevi vardır, belirli bir değer

Question

döndürür için bir giriş aranması:

F(0) = 0 
F(1) = 1 
F(2) = 2 
F(2*n) = F(n) + F(n+1) + n , n > 1 
F(2*n+1) = F(n-1) + F(n) + 1, n >= 1 

bir numara n < 10^25 verildi ve bir değer a gibi F(a)=n var göstermek zorunda am. fonksiyonu nasıl tanımlandığını Çünkü F(a)=F(b)=n where a < b gibi bir n böyle orada mevcut olabilir ve bu durumda ben geri dönmelidir b değil a

Ne var bugüne kadar geçerli:

• Biz içine bu fonksiyonu bölebilirsiniz iki katı monoton seri, biri F (2 * n) ve bir tanesi F (2 * n + 1) için ve logaritmik zamanda belirtilen değeri bulabilir, bu yüzden bu bulgu az ya da çok yapılır.
• Ben de F(2*n) >= F(2*n+1) for any n tespit ettik, bu yüzden ilk F (2 * n) bu uygulamayı arayın ve onu orada bulamazlarsa, ben (* 2 n + 1) F
• sorunu arama fonksiyon değerini hesaplar. 10^7'ye kadar olan bazı çılgın hafızalarda ve tekrar tekrar gerilemeye rağmen, 10^12'nin üzerindeki değerler makul bir sürede hesaplanamamıştır.

Ben aslında tüm anladım gerek öğrenmek açısından algoritma var, ama yeterince hızlı F (n) hesaplamak mümkün değil.

Answer 1

Memoisasyonu, hedef değere kadar tamamen kullanın, örn. Python:

class Memoize: 
    def __init__(self, fn): 
     self.fn = fn 
     self.memo = {} 
    def __call__(self, *args): 
     if not self.memo.has_key(args): 
      self.memo[args] = self.fn(*args) 
     return self.memo[args] 

@Memoize 
def R(n): 
    if n<=1: return 1 
    if n==2: return 2 
    n,rem = divmod(n,2) 
    if rem: 
     return R(n)+R(n-1)+1 
    return R(n)+R(n+1)+n 

Bu, 10 ** 25 cevabını anında hesaplar.

özyineleme doğası çoğu değerleri kullanmak en bunun abcdef'ait bir ikili sayı sadece gerekecektir için anlamına gelir çünkü bu işler nedeni: Her adımda

abcdef 
abcde-1,abcde,abcde+1 
abcd-2,abcd-1,abcd,abcd+1,abcd+2 
abc-2,abc-1,abc,abc+1,abc+2 
ab-2,ab-1,ab,ab+1,ab+2 
a-2,a-1,a,a+1,a+2 

sen 1 yukarı veya aşağı hareket edebilir ama aynı zamanda sayıyı 2'ye bölersiniz, böylece orijinal numaradan en fazla uzaklaşabilirsiniz. Bu nedenle, alınan kod sadece en fazla 5 * log_2 (n) değerlendirmesinde kullanılacaktır.