لا فكرة عن كيفية حل تمرين SICP 1.11

Question

تمرين 1.11:

وظيفة f يتم تعريفه من خلال القاعدة f(n) = n لو n < 3 و f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) لو n > 3. اكتب إجراء يحسب f عن طريق عملية عودية. اكتب إجراء يحسب f عن طريق عملية تكرارية.

تنفيذها بشكل متكرر بسيط بما فيه الكفاية. لكنني لم أستطع معرفة كيفية القيام بذلك بشكل تكراري. حاولت المقارنة مع مثال فيبوناتشي المقدم ، لكنني لم أكن أعرف كيفية استخدامه كقياس. لذلك استسلمت (عار علي) و googled من أجل تفسير, ووجدت هذا:

(define (f n)
   (if (< n 3)
       n
       (f-iter 2 1 0 n)))

(define (f-iter a b c count)
   (if (< count 3)
       a
       (f-iter (+ a (* 2 b) (* 3 c))
               a
               b
               (- count 1))))

بعد قراءته ، أفهم الكود وكيف يعمل. لكن ما لا أفهمه هو العملية اللازمة للحصول على التعريف العودية للوظيفة إلى هذا. لا أفهم كيف يمكن أن يتشكل الرمز في رأس شخص ما.

هل يمكن أن تشرح عملية التفكير اللازمة للوصول إلى الحل؟

Answer 1

تحتاج إلى التقاط الدولة في بعض المتراكم وتحديث الحالة في كل تكرار.

إذا كانت لديك خبرة في لغة ضرورية ، تخيل كتابة حلقة الوقت وتتبع المعلومات في المتغيرات أثناء كل تكرار للحلقة. ما هي المتغيرات التي تحتاجها؟ كيف يمكنك تحديثها؟ هذا هو بالضبط ما عليك القيام به لجعل مجموعة من المكالمات التكرارية (التيل) في المخطط.

بمعنى آخر ، قد يساعد ذلك في البدء في التفكير في هذا كحلقة من الوقت بدلاً من التعريف العودية. في النهاية ، ستكون بطلاقة بدرجة كافية مع التحولات التكرارية التي لن تحتاج إلى مساعدة إضافية للبدء.

---

لهذا المثال بالذات ، عليك أن تنظر عن كثب في مكالمات الوظائف الثلاثة ، لأنه ليس من الواضح على الفور كيفية تمثيلها. ومع ذلك ، إليك عملية التفكير المحتملة: (في Python Pseudo-Code للتأكيد على النقص)

كل خطوة متكررة تتتبع ثلاثة أشياء:

f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) 

لذلك أنا بحاجة إلى ثلاث قطع من الدول لتتبع القيم الحالية والأخير والما قبل الأخيرة من f. (إنه، f(n-1), f(n-2) and f(n-3).) اتصل بهم a, b, c. لا بد لي من تحديث هذه القطع داخل كل حلقة:

for _ in 2..n:
    a = NEWVALUE
    b = a
    c = b
return a

إذن ما هو NewValue؟ حسنًا ، الآن لدينا تمثيلات f(n-1), f(n-2) and f(n-3), ، إنها مجرد المعادلة العودية:

for _ in 2..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

الآن كل ما تبقى هو معرفة القيم الأولية لـ a, b and c. لكن هذا سهل ، لأننا نعرف ذلك f(n) = n if n < 3.

if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

لا يزال هذا مختلفًا قليلاً عن النسخة التكرارية المخطط ، لكن آمل أن تتمكن من رؤية عملية التفكير الآن.

Answer 2

أعتقد أنك تسأل كيف يمكن للمرء أن يكتشف الخوارزمية بشكل طبيعي ، خارج "نمط التصميم".

كان من المفيد بالنسبة لي أن أنظر إلى توسيع F (n) في كل قيمة n:

f(0) = 0  |
f(1) = 1  | all known values
f(2) = 2  |

f(3) = f(2) + 2f(1) + 3f(0)
f(4) = f(3) + 2f(2) + 3f(1)
f(5) = f(4) + 2f(3) + 3f(2)
f(6) = f(5) + 2f(4) + 3f(3)

إذا نظرنا عن كثب إلى F (3) ، نرى أنه يمكننا حسابه على الفور من القيم المعروفة. ماذا نحتاج لحساب F (4)؟

نحن بحاجة إلى حساب على الأقل F (3) + [الباقي]. ولكن أثناء حساب F (3) ، نحسب F (2) و F (1) أيضًا ، والذي نحتاج إلى حساب [الباقي] F (4).

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)

لذلك ، لأي رقم n ، يمكنني البدء بحساب F (3) ، وإعادة استخدام القيم التي أستخدمها لحساب F (3) لحساب F (4) ... ويستمر النمط ...

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)
            ↘       ↘
f(5) = f(4) + 2f(3) + 3f(2)

نظرًا لأننا سنعيد استخدامهم ، فإننا نمنحهم اسمًا أ ، ب ، ج. تم وضعه مع الخطوة التي نواجهها ، وتجول من خلال حساب F (5):

  Step 1:    f(3) = f(2) + 2f(1) + 3f(0) or f(3) = a1 + 2b1 +3c1

أين

أ₁ = F (2) = 2 ،

ب₁ = f (1) = 1 ،

ج₁ = 0

منذ f (n) = n لـ n <3.

هكذا:

F (3) = أ₁ + 2 ب₁ + 3C₁ = 4

  Step 2:  f(4) = f(3) + 2a1 + 3b1

لذا:

أ₂ = F (3) = 4 (محسوب أعلاه في الخطوة 1) ،

ب₂ = أ₁ = F (2) = 2 ،

ج₂ = ب₁ = F (1) = 1

هكذا:

F (4) = 4 + 2*2 + 3*1 = 11

  Step 3:  f(5) = f(4) + 2a2 + 3b2

لذا:

أ₃ = F (4) = 11 (محسوب أعلاه في الخطوة 2) ،

ب₃ = أ₂ = F (3) = 4 ،

ج₃ = ب₂ = F (2) = 2

هكذا:

F (5) = 11 + 2*4 + 3*2 = 25

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

أ_خطوة = نتيجة الخطوة - 1

ب_خطوة = أ_{الخطوة 1}

ج_خطوة = ب_{الخطوة 1}

بمجرد أن رأيت هذا ، كان الخروج بالنسخة التكرارية واضحة.

Answer 3

نظرًا لأن المنشور الذي ربطته لوصف الكثير عن الحل ، سأحاول فقط تقديم معلومات تكميلية.

أنت تحاول تحديد وظيفة خلفية التيل في المخطط هنا ، بالنظر إلى تعريف عودية (غير).

يتم التعامل مع الحالة الأساسية من العودية (F (n) = n إذا كان n <3) مع كلتا الوظيفتين. لست متأكدًا حقًا لماذا يفعل المؤلف هذا ؛ يمكن أن تكون الوظيفة الأولى ببساطة:

(define (f n)
   (f-iter 2 1 0 n))

سيكون الشكل العام:

(define (f-iter ... n)
   (if (base-case? n)
       base-result
       (f-iter ...)))

لاحظ أنني لم أملأ المعلمات لـ F-Titer حتى الآن ، لأنك تحتاج أولاً إلى فهم ما يجب نقله من تكرار إلى آخر.

الآن ، دعونا نلقي نظرة على تبعيات الشكل المتكرر لـ F (N). يشير إلى F (n - 1) ، f (n - 2) ، و f (n - 3) ، لذلك نحن بحاجة إلى الحفاظ على هذه القيم. وبالطبع نحتاج إلى قيمة n نفسها ، حتى نتمكن من التوقف عن التكرار عليها.

هكذا تتوصل إلى مكالمة خلفية التيل: نقوم بحساب f (n) لاستخدامها كـ f (n - 1) ، وتدوير f (n - 1) إلى f (n - 2) و f (n - 2) إلى F (n - 3) ، والعدد المنخفض.

إذا كان هذا لا يزال لا يساعد ، فيرجى محاولة طرح سؤال أكثر تحديدًا - من الصعب حقًا الإجابة عندما تكتب "لا أفهم" مع إعطاء تفسير شامل نسبيًا بالفعل.

Answer 4

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

المشكلة مع نهج بيل, ، مقتبس في سؤالك ، هو أنه ليس من الواضح على الفور ماذا المعنى تنقلها متغيرات الدولة ، a, b, ، و c. لا تنقل أسمائهم أي معلومات ، ولا يصف منشور بيل أي قاعدة ثابتة أو أخرى يطيعونها. أجد أنه من الأسهل صياغة وفهم الخوارزميات التكرارية إذا كانت متغيرات الحالة تطيع بعض القواعد الموثقة التي تصف علاقاتها مع بعضها البعض.

مع وضع ذلك في الاعتبار ، فكر في هذه الصيغة البديلة لخوارزمية نفسها بالضبط ، والتي تختلف عن بيل فقط في الحصول على أسماء متغيرة أكثر جدوى لـ a, b و c ومتغير مضاد متزايد بدلاً من تناقص:

(define (f n)
    (if (< n 3)
        n
        (f-iter n 2 0 1 2)))

(define (f-iter n 
                i 
                f-of-i-minus-2
                f-of-i-minus-1
                f-of-i)
    (if (= i n)
        f-of-i
        (f-iter n
                (+ i 1)
                f-of-i-minus-1
                f-of-i
                (+ f-of-i
                   (* 2 f-of-i-minus-1)
                   (* 3 f-of-i-minus-2)))))

فجأة ، فإن صحة الخوارزمية - وعملية التفكير وراء إنشائها - بسيطة في رؤيتها ووصفها. لكي يحسب f(n):

• لدينا متغير مضاد i يبدأ في 2 ويتسلق إلى n, ، زيادة بمقدار 1 في كل مكالمة إلى f-iter.
• في كل خطوة على طول الطريق ، نتتبع f(i), f(i-1) و f(i-2), ، وهو ما يكفي للسماح لنا بالحساب f(i+1).
• مرة واحدة i=n, ، لقد إنتهينا.

Answer 5

وظيفة f يتم تعريفه من خلال القاعدة f(n) = n, if n<3 و f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), if n > 3. اكتب إجراء يحسب f عن طريق عملية عودية.

هو - هي هو مكتوب بالفعل:

f(n) = n,                                  (* if *)  n < 3
     = f(n - 1) + 2f(n - 2) + 3f(n - 3),   (* if *)  n > 3

صدق أو لا تصدق ، كان هناك مرة واحدة هذه اللغة. إن كتابة هذا الأمر بلغة أخرى هو مجرد مسألة بناء جملة. وبالمناسبة ، فإن التعريف كما أنت (MIS) يقتبس له خطأ ، والذي أصبح الآن واضحًا وواضحًا للغاية.

اكتب إجراء يحسب f عن طريق عملية تكرارية.

التكرار يعني ذاهب إلى الأمام (هناك شرحك!) على عكس العودية للخلف في البدايه:

f(n)   =  f(n - 1) + 2f(n - 2) + 3f(n - 3) 
       =  a        + 2b        + 3c
f(n+1) =  f(n    ) + 2f(n - 1) + 3f(n - 2)
       =  a'       + 2b'       + 3c'          a' = a+2b+3c, b' = a, c' = b
......

وهذا يصف بالتالي انتقالات حالة المشكلة على أنها

 (n, a, b, c)  ->  (n+1, a+2*b+3*c, a, b)

يمكننا ترميزها على أنها

g (n, a, b, c) = g (n+1, a+2*b+3*c, a, b)

لكن بالطبع لن يتوقف. لذلك يجب أن يكون لدينا بدلاً من ذلك

f n = g (2, 2, 1, 0)
  where
  g (k, a, b, c) = g (k+1, a+2*b+3*c, a, b),    (* if *) k < n
  g (k, a, b, c) = a,                           otherwise 

وهذا يشبه تمامًا الرمز الذي طلبته ، حتى بناء الجملة.

عد حتى ن أكثر طبيعية هنا ، بعد نموذجنا المتمثل في "المضي قدمًا" ، ولكن العد التنازلي 0 كما هو الحال مع الرمز الذي تقتبسه هو بالطبع مكافئ تمامًا.

يتم استبعاد حالات الزاوية والأخطاء المحتملة خارج واحد كما ممارسه الرياضه التقنيات غير الفنية.