علاقة التكرار لعدد "المراجع" إلى وظيفتين متكررتين بشكل متبادل

Question

كنت ذاهبا من خلال قسم البرمجة الديناميكية من مقدمة إلى الخوارزميات (الطبعة 2) من قبل كورمن إت.آل.حيث صادفت علاقات التكرار التالية في سياق جدولة خط التجميع

(ملاحظة:جدولة خط التجميع أو البرمجة الديناميكية غير مطلوبة للإجابة على السؤال ، فهي فقط للحصول على معلومات بحيث تساعد في ربط السياق).

---

$(1),(2),(3)$ هي ثلاث علاقات كما هو موضح.

f و_ {1} [ي] = \ابدأ {الحالات} ه_1 + أ_{1 ، 1} و \ رباعية \ نص{إذا } ي = 1\\ \ دقيقة (و_1 [ي-1] + أ_{1 ، ي} ، و_2 [ي-1] + ر_{2 ، ي-1} + أ_{1 ، ي}) و \ رباعية \ نص{إذا } ي \ جي كيو 2\\ \ نهاية{الحالات} \ العلامة 1 $ $

متناظرة,

f و_ {2} [ي] = \ابدأ {الحالات} ه_2 + أ_{2 ، 1} و \ رباعية \ نص{إذا } ي = 1\\ \ دقيقة (و_2 [ي-1] + أ_{2 ، ي} ، و_1 [ي-1] + ر_{1 ، ي-1} + أ_{2 ، ي}) و \ رباعية \ نص{إذا } ي \ جي كيو 2\\ \ نهاية{الحالات} \ العلامة 2 2

(أين e أنا ، أ_{أنا ، ي} ، ر_{2 ، ي-1}} هي ثوابت ل i أنا=1 ، 2$ و j ي=1,2,3,...، ن n)

f و ^ \نجمة = \دقيقة (و_1[ن]+س_1 ، و_2[ن]+س_2)\العلامة 3 $ $

---

يحاول النص العثور على علاقة التكرار لعدد المرات f أنا [ي]$ (i أنا=1 ، 2$ و j ي=1,2,3,...، ن n) تتم الإشارة إليه إذا كتبنا رمزا متكررا متبادلا لـ f إف_1 [ي]] و f و_2 [ي]].دعونا r ر_ي (ي)$ تشير إلى عدد المرات f أنا [ي]$ المشار إليها.

يقولون ذلك,

من عند $(3)$,

r ص_1(ن)=ص_2(ن)=1.\ العلامة 4 $ $

من عند $(1)$ و $(2)$,

r ر_1(ي)=ر_2(ي)=ر_1(ي+1)+ر_2(ي+1)\علامة 5 tag

---

لم أستطع أن أفهم تماما كيف أن العلاقات $(4)$ و $(5)$ يتم الحصول عليها من العلاقات الثلاثة المقابلة.(مباشرة دون أي دليل, هل هو تافهة جدا?)

اعتقدت أنني يمكن أن تجعل من حدسي أنه لا يوجد سوى مكان واحد حيث f إف_1 [ن]] و f و_2 [ن]] تسمى ، والتي هي في f و ^ \ نجمة star, ، لذلك ربما في $(4)$ نحصل على العلاقة المطلوبة.

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

[ملاحظة:ومع ذلك ، يجب أن يكون البديل للتحريض الرياضي أكثر فائدة لأنه طريقة كتاب طبخ ميكانيكية دون إعطاء الكثير من التبصر في المشكلة (ولكن إذا لم يكن هناك مخرج آخر ، فسيتم تقدير الحث الرياضي إذا كان بإمكاني الحصول على الحدس وراء الدليل)].

Answer 1

يبدو أنك مرهق بعد رحلة طويلة ومتعبة قمت بها لفهم إعداد جدولة خط التجميع ، والخطوة 1 على هيكل أسرع طريقة عبر المصنع والخطوة 2 على حل متكرر.

من السهل فهم الصيغة (4) و (5).

عندما نقوم ببرمجة حل العودية باستخدام الصيغة (1) و (2) و (3) ، يتم تحويل الجانب الأيسر من كل صيغة إلى توقيع طريقة التنفيذ الخاصة به بينما يتم تحويل الجانب الأيمن إلى جسم الطريقة.

على سبيل المثال ، يتم تحويل (3) إلى رمز بايثون زائف

def f_star(n):
    return min(f_1(n) + x_1, f_2(n) + x_2)

لذلك ، عندما f و ^ \ نجمة star يشار إليه ، أي عندما f_star يسمى, f إف_1 [ن]] و f و_2 [ن]] سيتم الرجوع إليها ، أي., f_1(n) و f_2(n) سيتم استدعاؤها ، حيث f_1(.) و f_2(.) سيتم شرحه أدناه.وبما أننا سوف ندعو f_star(n) مرة واحدة ، وهو ما يكفي للحصول على قيمة f و ^ \ نجمة star, ، نحصل على الصيغة (4).

يتم تحويل الصيغة (1) إلى رمز بايثون زائف

def f_1(j):
    if j == 1:
        return e[1] + a[1][1]
    else:
        return min(f_1(j - 1) + a[1][j], f_2(j - 1) + t[2][j - 1] + a[1][j])

لذلك كلما f إف_1 [ي]] يشار إليه ، أي عندما f و_1 (ي)$ يسمى, f إف-1 [ي-1]] سيتم الرجوع إليها بالضبط واحد ، أي., f_1(j-1) سيتم استدعاؤه مرة واحدة بالضبط.

وبالمثل ، كلما f و_2 [ي]] المشار إليها, f إف-1 [ي-1]] سيتم الرجوع إليها مرة واحدة بالضبط.(يمكنك كتابة الدالة f_2(j) صراحة نفسك للتحقق من ذلك.)

لاحظ أن أي إشارة إلى f إف-1 [ي-1]] يجب إحضارها إما عن طريق الإشارة إلى f إف_1 [ي]] أو إشارة إلى f و_2 [ي]].لذلك لدينا r ر_1(ي-1) = ر_1(ي) + ر_2(ي).$$

وبالمثل أو عن طريق التناظر ، لدينا أيضا r ر_2(ي-1) = ر_1(ي) + ر_2(ي).$$

استبدال $j$ بواسطة j ي + 1 1, ، نحصل على الصيغة (5).