رقم فيبوناتشي n في الزمن الخطي
https://stackoverflow.com/questions/1525521
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هل هناك أي خوارزمية لحساب رقم فيبوناتشي n في الزمن الخطي الفرعي؟
المحلول
ال nيتم إعطاء رقم فيبوناتشي
f(n) = Floor(phi^n / sqrt(5) + 1/2)
أين
phi = (1 + sqrt(5)) / 2
على افتراض أن العمليات الرياضية البدائية (+, -, * و /) نكون O(1) يمكنك استخدام هذه النتيجة لحساب nرقم فيبوناتشي O(log n) الوقت (O(log n) بسبب التراجع في الصيغة).
في C #:
static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use
const double inverseSqrt5 = 0.44721359549995793928183473374626
const double phi = 1.6180339887498948482045868343656
*/
static int Fibonacci(int n) {
return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}
نصائح أخرى
متابعة من إشارة بيلسي إلى الأس المصفوفة، مثل تلك الخاصة بالمصفوفة
م = [1 1]
[1 0]
ثم
أكذوبة(ن) = من1,2
إن رفع المصفوفات إلى القوى باستخدام الضرب المتكرر ليس فعالاً للغاية.
هناك طريقتان لتأسيس المصفوفات هما فرق تسد الذي ينتج من في يا(لان ن) الخطوات، أو تحليل القيمة الذاتية وهو وقت ثابت، ولكنه قد يؤدي إلى حدوث أخطاء بسبب الدقة المحدودة للفاصلة العائمة.
إذا كنت تريد قيمة محددة أكبر من دقة تطبيق الفاصلة العائمة، فيجب عليك استخدام نهج O ( ln n ) بناءً على هذه العلاقة:
من = (من/2)2 if ن even = م·من-1 if ن is odd
تحليل القيمة الذاتية م يجد مصفوفتين ش و Λ مثل ذلك Λ هو قطري و
م = ش Λ ش-1
من = ( ش Λ ش-1) ن
= ش Λ ش-1 ش Λ ش-1 ش Λ ش-1 ... n times
= ش Λ Λ Λ ... ش-1
= ش Λ ن ش-1
رفع المصفوفة القطرية Λ إلى نالقوة هي مسألة بسيطة تتمثل في رفع كل عنصر فيها Λ إلى نعشر، وهذا يعطي طريقة O(1) للرفع م إلى نالقوة.ومع ذلك، فإن القيم في Λ من غير المحتمل أن تكون أعدادًا صحيحة، لذلك سيحدث بعض الخطأ.
تعريف Λ لمصفوفتنا 2x2 كما
Λ = [ λ1 0 ] = [ 0 λ2 ]
للعثور على كل λ, ، نحن نحل
|م - λأنا| = 0
الذي يعطي
|م - λأنا| = -λ ( 1 - λ ) - 1 λ² - λ - 1 = 0
باستخدام الصيغة التربيعية
λ = ( -b ± √ ( b² - 4ac ) ) / 2a
= ( 1 ± √5 ) / 2
{ λ1, λ2 } = { Φ, 1-Φ } where Φ = ( 1 + √5 ) / 2
إذا كنت قد قرأت إجابة جيسون، يمكنك أن ترى إلى أين سيصل هذا الأمر.
حل للمتجهات الذاتية X1 و X2:
if X1 = [ X1,1, X1,2 ] م.X1 1 = λ1X1 X1,1 + X1,2 = λ1 X1,1 X1,1 = λ1 X1,2 => X1 = [ Φ, 1 ] X2 = [ 1-Φ, 1 ]
هذه النواقل تعطي ش:
ش = [ X1,1, X2,2 ]
[ X1,1, X2,2 ]
= [ Φ, 1-Φ ]
[ 1, 1 ]
قلب ش استخدام
أ = [ a b ]
[ c d ]
=>
أ-1 = ( 1 / |أ| ) [ d -b ]
[ -c a ]
لذا ش-1 اعطي من قبل
ش-1 = ( 1 / ( Φ - ( 1 - Φ ) ) [ 1 Φ-1 ]
[ -1 Φ ]
ش-1 = ( √5 )-1 [ 1 Φ-1 ]
[ -1 Φ ]
الاختيار التعقل:
UΛU-1 = ( √5 )-1 [ Φ 1-Φ ] . [ Φ 0 ] . [ 1 Φ-1 ]
[ 1 1 ] [ 0 1-Φ ] [ -1 Φ ]
let Ψ = 1-Φ, the other eigenvalue
as Φ is a root of λ²-λ-1=0
so -ΨΦ = Φ²-Φ = 1
and Ψ+Φ = 1
UΛU-1 = ( √5 )-1 [ Φ Ψ ] . [ Φ 0 ] . [ 1 -Ψ ]
[ 1 1 ] [ 0 Ψ ] [ -1 Φ ]
= ( √5 )-1 [ Φ Ψ ] . [ Φ -ΨΦ ]
[ 1 1 ] [ -Ψ ΨΦ ]
= ( √5 )-1 [ Φ Ψ ] . [ Φ 1 ]
[ 1 1 ] [ -Ψ -1 ]
= ( √5 )-1 [ Φ²-Ψ² Φ-Ψ ]
[ Φ-Ψ 0 ]
= [ Φ+Ψ 1 ]
[ 1 0 ]
= [ 1 1 ]
[ 1 0 ]
= م
لذا فإن فحص التعقل يظل ساريًا.
الآن لدينا كل ما نحتاج إلى حسابه من1,2:
من = شΛنش-1
= ( √5 )-1 [ Φ Ψ ] . [ Φن 0 ] . [ 1 -Ψ ]
[ 1 1 ] [ 0 Ψن ] [ -1 Φ ]
= ( √5 )-1 [ Φ Ψ ] . [ Φن -ΨΦن ]
[ 1 1 ] [ -Ψن ΨنΦ ]
= ( √5 )-1 [ Φ Ψ ] . [ Φن Φن-1 ]
[ 1 1 ] [ -Ψن -Ψن-1 ] as ΨΦ = -1
= ( √5 )-1 [ Φن+1-Ψن+1 Φن-Ψن ]
[ Φن-Ψن Φن-1-Ψن-1 ]
لذا
أكذوبة(ن) = من1,2
= ( Φن - (1-Φ)ن ) / √5
وهو ما يتفق مع الصيغة الواردة في مكان آخر.
يمكنك استخلاصها من علاقة تكرارية، ولكن في الحوسبة الهندسية والمحاكاة، يعد حساب القيم الذاتية والمتجهات الذاتية للمصفوفات الكبيرة نشاطًا مهمًا، لأنه يوفر الاستقرار والتوافقيات لأنظمة المعادلات، فضلاً عن السماح برفع المصفوفات إلى قوى عالية بكفاءة.
إذا كنت تريد الرقم الدقيق (وهو "برعاية"، بدلا من int / تعويم)، فأنا أخشى ذلك
هذا مستحيل!
كما هو مذكور أعلاه، فإن الصيغة لأرقام فيبوناتشي هي:
FIB N = الكلمة (PHIن/√5 + 1/2)
fib n ~ = phiن/√5
كم عدد الأرقام هو fib n?
numDigits (fib n) = log (fib n) = log (phiن/ 5) = سجل فاين - سجل 5 = n * log phi - log 5
numDigits (fib n) = n * const + const
إنه في(ن)
منذ النتيجة المطلوبة هي في(ن)، لا يمكن حسابها في أقل من في(ن) الوقت.
إذا كنت تريد فقط الأرقام السفلية من الإجابة، فمن الممكن حساب الوقت الخطي الفرعي باستخدام طريقة عرض المصفوفة.
واحدة من تمارين في SICP. هو حول هذا، والذي لديه الجواب الموصوف هنا.
في النمط الضروري، سيبدو البرنامج شيئا
وظيفة فيض(عدد)
أ ← 1
ب ← 0
ب ← 0
س: ← 1
بينما عدد > 0 يفعل
لو حتى في(عدد) ثم
ب ← ب² + س:²
س: ← 2بقي + س:²
عدد ← عدد ÷ 2
آخر
أ ← بات + AQ. + إكسب
ب ← ب + AQ.
عدد ← عدد - 1
إنهاء إذا
النهاية في حين
يعود ب
وظيفة النهاية
يمكنك القيام بذلك عن طريق مضاعفة مصفوفة الأعداد الصحيحة أيضًا.إذا كان لديك المصفوفة
/ 1 1 \
M = | |
\ 1 0 /
ثم (M^n)[1, 2] سيكون مساويا ل nرقم فيبوناتشي، إذا [] هو منخفض مصفوفة و ^ هو الأس المصفوفة.بالنسبة للمصفوفة ذات الحجم الثابت، يمكن إجراء الأس إلى قوة تكاملية موجبة في زمن O(log n) بنفس الطريقة كما هو الحال مع الأعداد الحقيقية.
يحرر: بالطبع، اعتمادًا على نوع الإجابة التي تريدها، قد تتمكن من التخلص من خوارزمية الوقت الثابت.كما تظهر الصيغ الأخرى، فإن nرقم فيبوناتشي ينمو بشكل كبير مع n.حتى مع الأعداد الصحيحة غير الموقعة ذات 64 بت، ستحتاج فقط إلى جدول بحث مكون من 94 إدخالًا لتغطية النطاق بأكمله.
التعديل الثاني: إن إجراء المصفوفة الأسية باستخدام التحلل الذاتي أولاً يعادل تمامًا حل JDunkerly أدناه.القيم الذاتية لهذه المصفوفة هي (1 + sqrt(5))/2 و (1 - sqrt(5))/2.
Wikipedia لديه حل نموذج مغلقhttp://en.wikipedia.org/wiki/fibonacci_number.
أو في C #:
public static int Fibonacci(int N)
{
double sqrt5 = Math.Sqrt(5);
double phi = (1 + sqrt5) / 2.0;
double fn = (Math.Pow(phi, N) - Math.Pow(1 - phi, N)) / sqrt5;
return (int)fn;
}
بالنسبة للكبار حقا، تعمل هذه الوظيفة العودية هذه. يستخدم المعادلات التالية:
F(2n-1) = F(n-1)^2 + F(n)^2
F(2n) = (2*F(n-1) + F(n)) * F(n)
تحتاج إلى مكتبة تتيح لك العمل مع أعداد صحيحة كبيرة. أنا استخدم مكتبة biginteger من https://mattmccutchen.net/bigint/.
ابدأ بمجموعة من أرقام فيبوناتشي. استخدم Fibs [0] = 0، Fibs [1] = 1، fibs [2] = 1، fibs [3] = 2، fibs [4] = 3، إلخ. في هذا المثال، أنا استخدم مجموعة من أول 501 (العد 0). يمكنك العثور على أول 500 أرقام Fibonacci غير صفرية هنا: http://home.hiwaay.net/~jalison/fib500.html.. وبعد يتطلب الأمر تحريرا قليلا لوضعه في التنسيق الصحيح، ولكن هذا ليس صعبا للغاية.
ثم يمكنك العثور على أي رقم فيبوناتشي باستخدام هذه الوظيفة (في ج):
BigUnsigned GetFib(int numfib)
{
int n;
BigUnsigned x, y, fib;
if (numfib < 501) // Just get the Fibonacci number from the fibs array
{
fib=(stringToBigUnsigned(fibs[numfib]));
}
else if (numfib%2) // numfib is odd
{
n=(numfib+1)/2;
x=GetFib(n-1);
y=GetFib(n);
fib=((x*x)+(y*y));
}
else // numfib is even
{
n=numfib/2;
x=GetFib(n-1);
y=GetFib(n);
fib=(((big2*x)+y)*y);
}
return(fib);
}
لقد اختبرت هذا لرقم Fibonacci 25،000 وما شابه ذلك.
إليك إصداري العودية الذي يكرر تسجيل الدخول (n) مرات. أعتقد أنه من الأسهل قراءة في النموذج العريط:
def my_fib(x):
if x < 2:
return x
else:
return my_fib_helper(x)[0]
def my_fib_helper(x):
if x == 1:
return (1, 0)
if x % 2 == 1:
(p,q) = my_fib_helper(x-1)
return (p+q,p)
else:
(p,q) = my_fib_helper(x/2)
return (p*p+2*p*q,p*p+q*q)
إنه يعمل لأنه يمكنك حساب fib(n),fib(n-1) استخدام fib(n-1),fib(n-2) إذا كان n غريبا وإذا كان n حتى، فيمكنك حسابه fib(n),fib(n-1) استخدام fib(n/2),fib(n/2-1).
القضية الأساسية والحالة الفردية بسيطة. لاستخلاص الحال، ابدأ ب A، B، C كقيم فيبوناتشي متتالية (على سبيل المثال، 8،5،3) وكتابتها في مصفوفة، مع A = B + C. تنويه:
[1 1] * [a b] = [a+b a]
[1 0] [b c] [a b]
من ذلك، نرى أن مصفوفة لأرقام Fibonacci الثلاثة الأولى، تايمز مصفوفة لأي أرقام فيبوناتشي ثلاثية متتالية، تساوي التالي. لذلك نحن نعلم أن:
n
[1 1] = [fib(n+1) fib(n) ]
[1 0] [fib(n) fib(n-1)]
لذا:
2n 2
[1 1] = [fib(n+1) fib(n) ]
[1 0] [fib(n) fib(n-1)]
تبسيط الجانب الأيمن يؤدي إلى القضية حتى.
استخدام رديئة
l1 <- (1+sqrt(5))/2
l2 <- (1-sqrt(5))/2
P <- matrix(c(0,1,1,0),nrow=2) #permutation matrix
S <- matrix(c(l1,1,l2,1),nrow=2)
L <- matrix(c(l1,0,0,l2),nrow=2)
C <- c(-1/(l2-l1),1/(l2-l1))
k<-20 ; (S %*% L^k %*% C)[2]
[1] 6765
بصرف النظر عن ضبط الدقيقة من خلال الأساليب الرياضية، فإن أحد أفضل الحل الأمثل (أعتقد) يستخدم القاموس لتجنب الحسابات المتكررة.
import time
_dict = {1:1, 2:1}
def F(n, _dict):
if n in _dict.keys():
return _dict[n]
else:
result = F(n-1, _dict) + F(n-2, _dict)
_dict.update({n:result})
return result
start = time.time()
for n in range(1,100000):
result = F(n, _dict)
finish = time.time()
print(str(finish - start))
نبدأ في قاموس تافهة (أول قيمتين من تسلسل Fibonacci) وإضافة قيم فيبوناتشي باستمرار إلى القاموس.
استغرق الأمر حوالي 0.7 ثانية لأول 100000 قيم فيبوناتشي (Intel Xeon CPU E5-2680 @ 2.70 جيجا هرتز، 16 جيجابايت ذاكرة الوصول العشوائي، نظام التشغيل Windows 10-64 بت)
انظر الفجوة وقهر خوارزمية هنا
يحتوي الرابط على pseudoodocode للأسعار المصفوفة المذكورة في بعض الإجابات الأخرى لهذا السؤال.
الحساب نقطة ثابت غير دقيق. يعطي رمز C # في جيسون إجابة غير صحيحة ل N = 71 (308061521170130 بدلا من 308061521170129) وما بعده.
للحصول على إجابة صحيحة، استخدم نظام جبري حسابي. سيمبي هو مثل هذه المكتبة لبثون. هناك وحدة تحكم تفاعلية في http://live.sympy.org/ وبعد نسخ ولصق هذه الوظيفة
phi = (1 + sqrt(5)) / 2
def f(n):
return floor(phi**n / sqrt(5) + 1/2)
ثم حساب
>>> f(10)
55
>>> f(71)
308061521170129
قد ترغب في محاولة تفتيش phi.
يمكنك استخدام المعادلة الجذور المربعة الغريبة للحصول على إجابة محددة. السبب هو أن $ SQRT (5) $ يقع في النهاية، عليك فقط تتبع المعاملات بتنسيق الضرب الخاص بك.
def rootiply(a1,b1,a2,b2,c):
''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
return a1*a2 + b1*b2*c, a1*b2 + a2*b1
def rootipower(a,b,c,n):
''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
ar,br = 1,0
while n != 0:
if n%2:
ar,br = rootiply(ar,br,a,b,c)
a,b = rootiply(a,b,a,b,c)
n /= 2
return ar,br
def fib(k):
''' the kth fibonacci number'''
a1,b1 = rootipower(1,1,5,k)
a2,b2 = rootipower(1,-1,5,k)
a = a1-a2
b = b1-b2
a,b = rootiply(0,1,a,b,5)
# b should be 0!
assert b == 0
return a/2**k/5
if __name__ == "__main__":
assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
assert fib(10)==55
إليك بطانة واحدة يحسب f (n)، باستخدام أعداد صحيحة الحجم O (n)، في العمليات الحسابية O (Log N):
for i in range(1, 50):
print(i, pow(2<<i, i, (4<<2*i)-(2<<i)-1)//(2<<i))
استخدام أعداد صحيحة الحجم O (N) معقولة، لأن هذا يشبه حجم الجواب.
لفهم ذلك، دع PHI تكون النسبة الذهبية (أكبر حل ل X ^ 2 = x + 1) و f (n) يكون رقم n'th fibonacci، حيث f (0) = 0، f (1) = f (1) = f (1) = f (1) = f (2) = 1
الآن، Phi ^ n = f (n-1) + f (n) phi.
إثبات عن طريق التعريفي: phi ^ 1 = 0 + 1 * phi = f (0) + f (1) phi. وإذا VI ^ n = f (n-1) + f (n) phi، ثم phi ^ (n + 1) = f (n-1) phi + f (n) phi ^ 2 = f (n-1) phi + f (n) (phi + 1) = f (n) + (f (n) + f (n-1)) phi = f (n) + f (n + 1) phi. الخطوة الصعبة الوحيدة في هذا الحساب هي تلك التي تحل محل phi ^ 2 بواسطة (1 + phi)، والتي تتبع لأن PHI هي النسبة الذهبية.
أيضا أرقام النموذج (A + B * PHI)، حيث يتم إغلاق أعداد صحيحة A، B ضجة تحت الضرب.
إثبات: (p0 + p1 * phi) (q0 + q1 * phi) = p0q0 + (p0q1 + q1p0) phi + p1q1 * phi ^ 2 = p0q0 + (p0q1 + q1p0) phi + p1q1 * (phi + 1) = ( P0Q0 + P1Q1) + (P0Q1 + Q1P0 + P1Q1) * PHI.
باستخدام هذا التمثيل، يمكن للمرء أن يحسب Phi ^ n في العمليات العددية O (Log N) باستخدام Opponentiation عن طريق التربيع. ستكون النتيجة F (N-1) + f (n) phi، والتي يمكن للمرء قراءة رقم n'th fibonacci.
def mul(p, q):
return p[0]*q[0]+p[1]*q[1], p[0]*q[1]+p[1]*q[0]+p[1]*q[1]
def pow(p, n):
r=1,0
while n:
if n&1: r=mul(r, p)
p=mul(p, p)
n=n>>1
return r
for i in range(1, 50):
print(i, pow((0, 1), i)[1])
لاحظ أن غالبية هذا التعليمات البرمجية هي وظيفة بأسعار مربعة قياسية.
للوصول إلى الخطوط الجوية الواحدة التي تبدأ هذه الإجابة، يمكن للمرء ملاحظة أن تمثيل PHI بواسطة عدد صحيح كبير بما فيه الكفاية X, ، يمكن للمرء أن يؤدي (a+b*phi)(c+d*phi) كما العملية عدد صحيح (a+bX)(c+dX) modulo (X^2-X-1). وبعد ثم pow وظيفة يمكن استبدالها ببيثون القياسية pow وظيفة (والتي تتضمن مريح حجة ثالثة z الذي يحسب النتيجة modulo z. وبعد ال X المختار هو 2<<i.
