كيف تثبت من خلال الاستقراء أن البرنامج لا شيء ؟

Question

لدي جهاز كمبيوتر برنامج يقرأ في مجموعة من المحارف التي المعاملات و مشغلي مكتوب في postfix التدوين.البرنامج ثم يمسح من خلال مجموعة تعمل على النتيجة باستخدام مكدس كما هو مبين :

get next char in array until there are no more
if char is operand
    push operand into stack
if char is operator 
    a = pop from stack
    b = pop from stack
    perform operation using a and b as arguments
    push result
result = pop from stack

كيف أثبت من خلال الاستقراء أن هذا البرنامج بشكل صحيح يقيم أي postfix التعبير ؟ (مأخوذة من ممارسة 4.16 خوارزميات بلغة جافا (Sedgewick 2003))

Answer 1

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

1) allgoritm يعمل مقابل 2 المعاملتين (ومشغل واحد) وغوارث يعمل لمدة 3 معاملات (و 2 من المشغلين) ==> من شأنها أن تكون القضية الأساسية الخاصة بك 2) إذا كانت الخوارزمية تعمل في المعاملات N (و N-1 للمشغلين) يجب أن تعمل مع المعاملات N + 1. ==> هذا سيكون الجزء الاستقرائي من الدليل

حظ سعيد ؛-)

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

مرة أخرى على مقيم التعبير القائم على المكدس ... تلميح أخير واحد (في التفسير الممتاز ل Captain Segfault الممتاز الذي ستشعر به أكثر من أبلغ ...).

تعبيرات RPN هي: - لديهم مشغل واحد أقل من المعامل - لا يوفرون أبدا مشغلا عندما يكون لدى المكدس أقل من 2 المعاملتين (إذا لم يفعلوا ذلك؛ سيكون هذا ما يعادل وضع قوس غير متوازن في سهل التعبير، أي تعبير غير صالح).

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

لذلك النظام لا يهم.

Answer 2

هل تعرف ما التعريفي ؟ هل عموما ترى كيف الخوارزمية تعمل ؟ (حتى لو كنت لا يمكن إثبات ذلك حتى الآن؟)

التعريف الخاص بك فرضية أن أقول أنه بعد معالجة N عنه حرف ، المكدس هو "الصحيح"."الصحيح" كومة كاملة RPN التعبير عنصر واحد فقط (الجواب).الجزئي RPN التعبير المكدس لديه عدة عناصر.

دليل الخاص بك ثم التفكير في هذه الخوارزمية (ناقص النتيجة = البوب من كومة خط) كما محلل أن يتحول جزئية RPN التعبيرات في أكوام ، وإثبات أن يتحول إلى الصحيح مداخن.

أنها قد تساعد في تعريف RPN التعبير و العمل بالعكس من ذلك.