لمسألة الرياضيات

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

النظر في مشكلة البرمجة مثيرة للاهتمام ، والتي لديها شخصية أولمبياد إلى حد ما.

Pnp: من هذه النقطة إلى الأمام ، يمكن أنصار فكرة أن البرمجة اليوم تتكون من صفحات ويب مصممة بشكل جميل توقف عن القراءة ، أنت على حق تماما ، لا تحتاج إلى الرياضيات ...

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

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

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

أقوم بصياغة المشكلة - كم عدد الأرقام المختلفة للطول K التي تنتهي في زر p يمكن أن تكتب على لوحة مفاتيح الهاتف (لوحة المفاتيح) إذا كنا بحاجة إلى التنقل بين الأزرار مع فارس الشطرنج. من المعلوم أنك رأيت لوحة المفاتيح (لا يزال لديّ هاتف جوال عادي ، وليس هاتف ذكي ، لذلك أراها كل يوم ، على القارئ الأكثر تقدماً الاتصال بشبكة الإنترنت للحصول على المساعدة) وأنت تعرف كيف يسير حصان الشطرنج (يسهل الوصول إليه عبر google). الرياضيات لا علاقة لها بها حتى الآن ، إذا لم يكن لديك القدرة على حساب الخيارات.

الحل الأول واضح تمامًا - نأخذ جميع الأزرار العشرة واحدًا تلو الآخر (نشير إلى عددهم بعلامة n للعمومية) ، ونأخذ في الاعتبار جميع الأرقام الممكنة من K الطويلة منه ونحسب تلك الأزرار التي تنتهي في الزر المطلوب. يتم تلخيص الأرقام الناتجة والإجابة جاهزة. يتم التعبير عن العدد الإجمالي للخيارات التي يتم عرضها تقريبًا على أنها n * B (K) ، حيث B (K) هو عدد التحركات المحتملة للطول K. في الواقع ، تحتاج إلى النظر في مجموع المواضع n ، لأن B (p ، K) يعتمد بوضوح على عدد الزر ولكن كتقدير أولي ينزل.

قبل المتابعة إلى البحث B ، يمكن للمرء أن يقلل بشكل كبير من عدد الخيارات من خلال تطبيق الحس السليم (لا ، ليس بعد الرياضيات). نظرًا لأن حركة الأزرار تعتمد على الخلفية ، يمكننا عكس المهمة والبحث عن جميع أرقام الطول K بدءًا من الزر المطلوب ص. بعد ذلك سيكون العدد الإجمالي للخيارات هو B (p ، K) ، وهو أقل من n مرة. واو ، لقد وجدنا للتو طريقة للإسراع في البحث عن حل 10 مرات - رائع ، لنرى مقدار ما تبقى.

نحتاج إلى تقييم B (p ، K) ، والذي نحدد أنه في كل خطوة لدينا خياران إلى 3 خيارات لتطوير الأحداث. ويترتب على ذلك (بشكل عام ، أن هذا هو التوافقيات ، ولكنه واضح بشكل حدسي) أن إجمالي عدد الخيارات سيكون من 2 ** K إلى 3 ** K (من الآن فصاعداً استخدم K-1 كـ K). يمكننا تحسين هذا التقدير من خلال الانتقال إلى نموذج احتمالي. بالنظر إلى أن وجود إصبع في كل زر في الوقت الحالي أمر محتمل على حد سواء (بيان قوي ، على الأرجح غير صحيح ، ولكنه مقبول بتقديرات تقريبية) ، يمكننا حساب متوسط ​​عدد خيارات النقل 7 * 2 + 2 (الأزرار 4 و 6) * 3 = 20/9 ~ 2.22 . بعد ذلك ، سيكون التقدير 2.22 ** K ، ونعلم أن لدينا على الأقل 2 ** K. ثم للحصول على K = 100 نحصل على حد أدنى 2 ** 100 = (2 ** 10) ** 10> (10 ** 3) ** 10 = 10 ** 30.

إذا أخذنا بعين الاعتبار خيارًا واحدًا في الثانية نانوثانية (وهذا ليس بالأمر السهل حتى على أجهزة كمبيوتر سطح مكتب قوية) ، فإننا نحتاج إلى 10 ** 30/10 ** 9 = 10 ** 21 ثانية. بعد ذلك ، نذكّر بالذكريات الرائعة "π الثواني تساوي قرن" والوقت المطلوب سيكون 10 ** 21 / 3.14 * 10 ** 9 ~ 3 * 10 ** 11 قرون. يبدو لي أن عددًا قليلاً من القراء سيعيشون لرؤية نهاية الحسابات باستخدام المنهجية المقترحة. العارض فظيع ، الفصيل الوحيد هو الأسوأ منها.

سنقوم بتحسين الحل بناءً على حقيقة أننا مهتمون بعدد الخيارات ، لكن ليس الخيارات نفسها. يمكنك تقديم الصيغة الواضحة B (p ، K) = مجموع B (p '، K-1) للجميع p' التي نحصل عليها في خطوة واحدة من p. نبدأ من الزر الأخير ونخصص له وزنًا واحدًا ، ثم ننفذ الإجراء الخاص بتجميع الأوزان الحالية إلى التالي ، كرر إلى العمق المطلوب.

نوضح ما قيل بمثال ، بدءًا من الرقم 1 {1234567890}:
الوزن الأولي {1000000000} ،
بعد النقل الأول {0000010100} (خياران) ،
بعد النقل الثاني {2010001001} (5 خيارات) ،
بعد الثالث {0102040300} (10 خيارات) وهلم جرا.

الخوارزمية بسيطة ، ويمكن تنفيذها حتى مع يديك. التقدير العام لوقت التنفيذ هو التكرارات K ، في كل منها بالنسبة للأوزان n لا نقوم بتعديل أكثر من الأوزان ذات الصلة n ، الإجمالي n ** 2 * K. للحالة التي تم بحثها سابقًا ، 10 * 10 * 100 = 10 ** 4 - قليلاً جدًا.

يبقى فقط لتقييم مدة كل عملية - وهذا هو إضافة (مسألة القمامة) ، ولكن ليست إضافة بسيطة (من هذا المكان بمزيد من التفاصيل). لقد قمنا بالفعل بتعيين الحد الأدنى للاستجابة على 2 ** K ، أي أننا بالتأكيد بحاجة إلى K بت على الأقل لتمثيل النتيجة. الحد الأعلى هو 3 ** K ، بالنسبة لحالتنا 3 ** 100 = (3 ** 5) ** 20 <(2 ** 8) * 20 = 2 ** 160 ، أي أننا نضمن أن نصل إلى 160 بت. يمكننا أن نفترض أن 128 بت كافية لنا ، لأن 2.2 ** 100 <2 ** 128 ، لكن قبول مثل هذا البيان عن الإيمان أمر مخيف ، لذلك نحن بحاجة إلى رقم يحتوي على 160 بتة على الأقل أو مع 49 خانة عشرية ، اعتمادًا على مكتبة الأرقام دقة عالية.

PNP: لا تقدم نقطة عائمة ، نحن بحاجة إلى نتيجة دقيقة تمامًا.
في الافتراضات المقبولة ، ستشغل عملية الإضافة 160/8 = 20 بايت / 4 = 5 إضافات للأعداد الصحيحة 32 بت ، والتي لا تؤثر بأي شكل من الأشكال على ترتيب الوقت (تظل خطية في K) ، ولكن يمكن أن تزيد بشكل كبير من وقت الحساب الحقيقي (عدة مرات).

في أي حال ، تكون النتيجة رائعة ببساطة - لقد حولنا المهمة من غير قابلة للحل بشكل أساسي في وقت معقول إلى حل كامل: إذا تم تنفيذ عملية إضافة أولية واحدة في مايكروثانية (ومن السهل ضمان ذلك حتى على لوحة Arduino) ، فلن يتجاوز الوقت الإجمالي 10 * 4 * 20 / 10 ** 6 ، أقل من ثانية) وفعلنا دون أي الرياضيات.

ومع ذلك ، وإذا كنا بحاجة إلى K أكبر - بالطبع ، الترتيب الخطي للحسابات - هذا أمر رائع ، لكنه (وقد) سيؤدي إلى خسائر كبيرة في الوقت للقيم الكبيرة. اتضح أنه يمكنك تحسين الوقت المتوقع بشكل كبير ومشاهدة يديك.

ما نقوم به في كل خطوة من خطوات الحساب (الرمز الزائف):

  = 0;
   1
    2
*  (  1     2)
*       1     2.
  =  

    2 (  1 *  )

0 1, . '=* =(...((*)*)...). , =***. , . **3, ***3 — , ? , …

— , **3 , , , ( ) ( ), . , 100 99 8. , 2*log2(), ( =100 1000/10=100 ) , 2*log2()***3. , , , . , , log2(K), , , 100.

- ( , ), , , .