SICP جعل التغيير

Question

وبالتالي؛ أنا هواية يحاول العمل من خلال SICP (انه مجانا!) وهناك إجراء مثال في الفصل الأول الذي يهدف إلى حساب الطرق الممكنة لتغيير المعاملات المعدنية الأمريكية؛ (تغيير صانع 100) => 292. يتم تنفيذ شيء مثل:

(define (change-maker amount)
  (define (coin-value n)
    (cond ((= n 1) 1)
          ((= n 2) 5)
          ((= n 3) 10)
          ((= n 4) 25)
          ((= n 5) 50)))

  (define (iter amount coin-type)
    (cond ((= amount 0) 1)
          ((or (= coin-type 0) (< amount 0)) 0)
          (else (+ (iter amount
                         (- coin-type 1))
                   (iter (- amount (coin-value coin-type))
                         coin-type)))))

  (iter amount 5))

على أي حال؛ هذا إجراء عريض أشجار، ومؤلف "يترك كتحدي" إيجاد إجراءات تكرارية لحل نفس المشكلة (أي مساحة ثابتة). لم أكن حظا حظا في ذلك أو العثور على إجابة بعد الإحباط. أنا أتساءل عما إذا كان ضرطة في الدماغ من جانبي، أو إذا كان صاحب البلاغ معي.

Answer 1

أبسط / أكثر الطرق عامة للقضاء على العودية، بشكل عام، هي استخدام مكدس إضافي - بدلا من إجراء المكالمات العودية، فأنت تدفع حججها إلى المكدس، وتكرر. عندما تحتاج إلى نتيجة المكالمة العودية من أجل المضي قدما، مرة أخرى في الحالة العامة، هذا صبي أكثر تعقيدا لأنك ستضطر أيضا إلى دفع "طلب الاستمرار" (من شأنها أن تؤتي ثمارها كومة عندما تكون النتائج معروفة)؛ ومع ذلك، في هذه الحالة، نظرا لأن كل ما تقوم به مع جميع نتائج المكالمات العودية هو رخص، يكفي الاحتفاظ بمكرر، وفي كل مرة تحصل فيها على نتيجة عدد بدلا من الحاجة إلى إجراء المزيد من المكالمة، أضفه إلى المجمع.

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

خذ من أسفل إلى أعلى DP على هذه الوظيفة، على سبيل المثال. أنت تعرف أنك سوف تنتهي مرارا وتكرارا مع "عدد الطرق لتغيير المبلغ X مع أصغر عملة" فقط "(كما كنت تشعر بالأشياء إلى X مع مجموعات عملة مختلفة من الأصل amount)، لذلك تبدأ حساب أولئك amount القيم مع التكرار بسيط (f (x) = X/value إذا X هو بالضبط قابل للقسمة من قبل أصغر قيمة عملة value, ، آخر 0; ؛ هنا، value هو 1، لذلك f (x) = x للجميع x> 0). الآن تستمر من خلال حساب وظيفة جديدة G (X)، طرق لإجراء تغيير ل X مع اثنين أصغر العملات المعدنية: مرة أخرى التكرار بسيط لزيادة x، مع g (x) = f (x) + g (x - value) ل value من أصغر عملة صغيرة (سيكون التكرار بسيط لأنه بحسب الوقت الذي تقوم بحساب g (x) قمت بحسابها وتخزينها بالفعل f (x) و جميع g (y) ل y <x - بالطبع، g (x) = 0 لجميع x <= 0). ومرة أخرى بالنسبة ل H (x)، طرق لإحداث التغيير ل X مع ثلاثة أصغر عملات معدنية - H (x) = g (x) + g (x-value) على النحو الوارد أعلاه - ومن الآن عليك لن تحتاج إلى f (x) أي أكثر، حتى تتمكن من إعادة استخدامها الذي - التي الفضاء. قال كل شيء، وهذا سيحتاج إلى الفضاء 2 * amount - ليس "مساحة ثابتة" بعد، ولكن، الاقتراب ...

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

Answer 2

الحل الذي توصلت إليه هو الحفاظ على حساب كل نوع من أنواع العملة التي تستخدمها في "محفظة"

الحلقة الرئيسية تعمل مثل هذا؛ "الدين هو الطائفة الحالية،" تغيرت "هي القيمة الإجمالية للعملات المعدنية في المحفظة،" المقدمة هي مقدار التغيير الذي أحتاجه لجعله و "واضحة - أن يأخذ جميع القطع النقدية أصغر من طائفة معينة من المحفظة وبعد

#lang scheme
(define (sub changed denom)
  (cond
   ((> denom largest-denom)
    combinations)

   ((>= changed given)
    (inc-combinations-if (= changed given))

    (clear-up-to denom)
    (jump-duplicates changed denom)) ;checks that clear-up-to had any effect.

   (else
    (add-to-purse denom)
    (sub
     (purse-value)
     0
     ))))

(define (jump-duplicates changed denom)
  (define (iter peek denom)
    (cond
     ((> (+ denom 1) largest-denom)
      combinations)

     ((= peek changed)
      (begin
        (clear-up-to (+ denom 1))
        (iter (purse-value) (+ denom 1))))

      (else
       (sub peek (+ denom 1)))))
  (iter (purse-value) denom))

بعد قراءة إجابة Alex Martelli، جاءت مع فكرة المحفظة ولكن فقط تحقق لجعلها تعمل

Answer 3

هنا هل نسختي من الوظيفة، باستخدام البرمجة الديناميكية. يتم تهيئة متجه حجم N + 1 إلى 0، إلا أن العنصر 0 هو في البداية 1. ثم لكل عملة ممكنة (حلقة خارجية)، كل عنصر من نوع ناقلات (الحلقة الداخلية) بدءا من K'TH ، حيث K هي قيمة العملة المعدنية، يتم تزويد القيمة عند الفهرس الحالي ناقص ك.

(define (counts xs n)
  (let ((cs (make-vector (+ n 1) 0)))
    (vector-set! cs 0 1)
    (do ((xs xs (cdr xs)))
        ((null? xs) (vector-ref cs n))
      (do ((x (car xs) (+ x 1))) ((< n x))
        (vector-set! cs x (+ (vector-ref cs x)
          (vector-ref cs (- x (car xs)))))))))

> (counts '(1 5 10 25 50) 100)
292

يمكنك تشغيل هذا البرنامج في http://ideone.com/eiovy..

Answer 4

لذلك، في هذا الموضوع, ، يأتي Asker الأصلي للمسألة مع إجابة صوتية عبر النزول. ومع ذلك، أود أن أقترح أن رمزه يمكن تحسينه بسهولة إذا لاحظت ذلك cc-pennies غير ضروري تماما (وبإحكام، كذلك cc-nothing)

انظر، المشكلة مع الطريق cc-pennies هو مكتوب هو أنه نظرا لعدم وجود طائفة أقل للذهاب، كل ما ستفعله من خلال تحية هيكل إجراءات الطائفة المرتفعة هو تكرره (- amount 1) ل 0, ، وسوف تفعل هذا في كل مرة تقوم فيها بتمريرها مبلغا من cc-nickels إجراء. لذلك، في المرة الأولى، إذا حاولت 1 دولار، فستحصل على amount من 100، لذلك (- amount 1) يقيم إلى 99, وهذا يعني أنك ستخضع لعام 99 دورات زائدة من cc-pennies و cc-nothing دورة. ثم، سوف تنزلق النيكل 95 كمبلغ، حتى تحصل على 94 دورات أكثر إهدارا، لذلك وما إلى ذلك. وهذا كل شيء قبل أن تتحرك حتى الشجرة إلى الدايمات، أو أرباع، أو نصف دولارات.

بحلول الوقت الذي تحصل عليه cc-pennies, ، أنت تعرف بالفعل أنك تريد فقط رفع الركود من قبل واحد، لذلك أقترح هذا التحسين:

(define (count-change-iter amount)
    (cc-fifties amount 0))

(define (cc-fifties amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-fifties (- amount 50)
                (cc-quarters amount acc)))))

(define (cc-quarters amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-quarters (- amount 25)
                (cc-dimes amount acc)))))

(define (cc-dimes amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-dimes (- amount 10)
                (cc-nickels amount acc)))))

(define (cc-nickels amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-nickels (- amount 5)
                (cc-pennies amount acc)))))

(define (cc-pennies amount acc)
    (+ acc 1))

آمل أن تكونوا وجدت هذا مفيدا.

Answer 5

يمكنك حلها بشكل متكرر مع البرمجة الديناميكية في وقت متعدد الحدود الزائفة.