السلاسل العودية (البحث عن أفضل حل)

كثيرا ما تمر معنا السلاسل العودية في البرمجة والتي تكون من الشكل التالي

C0 F(n) + C1 F(n-1) + ...... + Ck F(n-k) = 0

ولعل أشهر سلسلة عودية التي يعرفها معظمنا هي متسلسلة فيبوناتشي F(n) = F(n-1) + F(n-2) والتي تشتهر بتطبيقاتها العديدة في الرياضيات .
كثير من المبرمجين يقومون باستخدام العودية بشكل مباشر في البرمجة لإيجاد الناتج من أجل الحد n وهذه الخوارزمية من أبطأ الخوارزميات في إيجاد التوابع العودية .
وإذا ما بحثنا في كتب الرياضيات عن حلول مباشرة للمعادلة العودية سنجد حلولا رياضية تتعلق بشكل مباشر بالحد n والتي تكون على الأغلب من الشكل :

F(n) = A₁R₁^{^n} + A₂ R₂^{^n}  + ....... + A_k R^{^n}

هذه الحلول هي حلول مباشرة ، ولكنها غير عمليه بتاتا فهي فاشلة إذا كانت n كبيرة جدا ولأن الحدود A_i و R_i غالبا ما تكون أعداد كسرية وهذا ما يؤدي بدوره إلى كثير من الضياعات عند تخزين الأعداد والعمليات الرياضية عليها.
 

الحل من أجل سلسلة فيبوناتشي :

إن أفضل خوارزمية متبعة في هذ المجال هي خوارزمية الحل عن طريق المصفوفات ، حيت يمكننا كتابة السلسلة العودية بالشكل المصفوفي  X_i+1 = M X_i . حيث M هي مصفوفة الأمثال .... يصبح علينا الآن فقط إيجاد المصفوفة M

المصفوفة على الطرف اليساري من المعادلة هي مصفوفة X_i+1 أما المصفوفة اليمينية فهي مصفوفة X_i  وتكونا من الحجم K * 1. أما مصفوفة الأمثال M فهي من الحجم K*K
 

لنأخد سلسلة فيبوناتشي مثالا : F(n) = F(n-1) + F(n-2)

| f(n) |  = M x | f(n-1)   || f(n-1) |        | f(n-2) |

نعلم أن المصفوفة M من الحجم 2*2
 

| f(n) | = | a b | x | f(n-1)  |
| f(n-1) |   | c d |   | f(n-2)|

حيث F(n) = a*F(n-1) + b*F(n-2)       و    F(n-1) = c*F(n-1) +d*F(n-2) 
 

وبالتالي نجد أن :

| f(n) | = | 1 1 | x | f(n-1)  |
| f(n-1) |   | 1 0 |   | f(n-2)|

عند تعويض n = 2 في المعادلة السابقة نحصل على الشكل التالي :
 

| f(2) | = | 1 1 | x | 1 || f(1) |   | 1 0 |   | 0 |

لك ماذا لو أردنا الحل من أجل n=k مثلا ، عندها نقول

X₂ = M X₁
 

نضرب الطرفين ب M

M * X₂ = M * M X₁
X₃ = M^2 X₁

..

..
X_k+1 = M^k X₁

M^2 = {{2,1} , {1,0}} => F(3) = 2

حسنا ماذا لو كانت المتسلسلة على الشكل التالي : f(n) = a*f(n-1) + b*f(n-2) + c*f(n-3) عندها :

| f(n+1) | = | a b c | x |   f(n) |
| f(n)   |   | 1 0 0 |   | f(n-1) |
| f(n-1) |   | 0 1 0 |   | f(n-2) |

ماذا لو كانت تتعلق بثابت : f(n) = a*f(n-1) + b*f(n-2) + c عندها نضيف الثابت إلى طرفي المعادلة العودية وذلك لتعلق جميع الحدود بنفس الثابت

| f(n+1) | = | a b 1 | x |   f(n) |
| f(n)   |   | 1 0 0 |   | f(n-1) |
| c    |   | 0 0 1 |   |     c    |

ماذا لو كانت تتعلق بمتسلسلة أخرى g(n) = a*g(n-1) + b*g(n-2) + c*f(n) حيث f(n) = d*f(n-1) + e*f(n-2) عندها

| g(n+1) |   | a b c 0 |   |   g(n) |
| g(n)   | = | 1 0 0 0 | x | g(n-1) |
| f(n+2) |   | 0 0 d e |   | f(n+1) |
| f(n+1) |   | 0 0 1 0 |   |   f(n) |

يفضل استعمال خوارزمية التقسيم والجمع لإيجاد M^k

أرجو أن تكونوا قد استفدتم من هذه المعلومات والسلام عليكم ورحمة الله وبركاته