حساب التعقيد بالنسبة خوارزمية العودية مع متعلق العلاقات

Question

كتبت البرنامج مؤخرا استنادا إلى خوارزمية العودية, حل عدد من الطرق بلاط 3xn المجلس مع 2x1 الدومينو:

F(n) = F(n-2) + 2*G(n-1)

G(n) = G(n-2) + F(n-1)

F(0) = 1, F(1) = 0, G(0) = 0, G(1) = 1

حاولت لحساب تعقيد باستخدام أساليب أعرف مثل العودية شجرة والتوسع ، ولكن لم يسفر أي منها عن أي إجابة.في الواقع لم أكن قد تأتي عبر مثل هذه الإعادة ، حيث العلاقات معقدين

أنا باستخدام أساليب خاطئة ، أو ربما باستخدام الأساليب في الطريق الخطأ ؟ وإذا كان الأمر كذلك, يمكن لأي شخص أن نقدم حلا ؟

Answer 1

دعونا نلاحظ أن $F(n) = G(n+1) - G(n-1)$.لذلك $$ ز(ن+1)-G(n-1) = G(n-1) - G(n-3) + 2G(n-1) ، $$ مما يعني أن $$ ز(ن+1) = 4G(n-1) - G(n-3).$$

وبالمثل ، $G(n) = (F(n+1)-F(n-1))/2$, وهكذا $$ (F(n+1)-F(n-1))/2 = (F(n-1)-F(n-3))/2 + F(n-1) ، $$ مما يعني أن $$ F(n+1) = 4F(n-1) - F(n-3).$$ هذه هي بالضبط نفس تكرار ذلك ، ولو مع مختلف القيم الأولية.

بسيطة الاستقراء يدل على أن $F(n) = 0$ غريبة $n$ في حين $G(n) = 0$ حتى $n$ (هذا أيضا يتبع من المعنى الدلالي).

باستخدام تكرار بسهولة نحصل على ذلك حتى $n$, $$ F(n) = (1/2 + 1/2\sqrt{3})(2 + \sqrt{3})^{n/2} + (1/2 - 1/2\sqrt{3})(2 - \sqrt{3})^{n/2}.$$ دعونا التعليق أن هذا التسلسل هو A001835.

وبالمثل ، بالنسبة الغريب $n$, $$ غرام(ن) = (1/2 + 1/\sqrt{3})(2 + \sqrt{3})^{(n-1)/2} + (1/2 - 1/\sqrt{3})(2 - \sqrt{3})^{(n-1)/2}.$$ هذا التسلسل هو A001353.

---

بدلا من ذلك, يمكن أن نلاحظ أن $$ \begin{pmatrix} F(n) \\ ز(ن+1) \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 1 & 3 \end{pmatrix} \begin{pmatrix} F(n-2) \\ ز(ن-1) \end{pmatrix} $$ ويترتب على ذلك أن $$ \begin{pmatrix} و(2m) \\ ز(2m+1) \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 1 & 3 \end{pmatrix}^m \begin{pmatrix} 1 \\ 1 \end{pmatrix} $$ إن القيم الذاتية للمصفوفة $2 \pm \sqrt{3}$, و لذلك نحن أدت إلى الصيغ كما سبق.