جافا سكريبت مسلية: معادلة خطية تقريبا

ماذا لو أخذنا الرياضيات الرائعة (وهي المعادلات الخطية) وجافا سكريبت الرائعة لدينا ، ثم فرضناها على الآخر؟ في ظروف القيود وخصائص بيئة js ، يمكن أن تتحول مشكلة رياضية بسيطة إلى مشكلة غريبة ومليئة بمخاطر الأحجار. في مؤتمر HolyJS 19 الأخير في موسكو ، تسببت إحدى المعادلات الخطية (من بين مهام أخرى من SEMrush ) في ضجة كبيرة .



ونعم ، هذا هو مرة أخرى عنوان مسلية JavaScript: أطلب منك أن تقطع كل من يهتم.


بالطبع ، كل شيء موصوف أدناه - إنها مجرد محاولة تافهة لتعايش شيئين رائعين من أجل المتعة - لا ينبغي أن يؤخذ على محمل الجد. وهذه المواد لم تكن لتوجد لو لم تكن من أجل المصلحة الحيوية من جانب المشاركين في المؤتمر ، والتي شكر خاص لهم!

صيغة

1. ابحث عن جميع الحلول الصحيحة للمعادلة:

9 +~ x >> 6 / 3 = -x / 3 

2. ابحث عن جميع الحلول الصحيحة للمعادلة:

 9 +~ x >> 6 / 3 = -x / 3 | 0 

تختلف المعادلة الثانية عن الأولى فقط في عملية إضافية على الجانب الأيمن.

تقريب رياضي

ننتقل إلى المعادلة الأولى. ولنبدأ ، سوف نفهم أولويات العمليات المستخدمة ، وفقًا للجدول :

 (9 +(~ x)) >> (6 / 3) = -x / 3 

نحن نأخذ النفي bitwise من x ، ثم نضيفه إلى 9. ونُقلت نتيجة الإضافة bitwise إلى اليمين بعدد البتات المساوية لقيمة القسمة 6 على 3.

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

تعمل عمليات Bitwise مع المعاملات كعدد صحيح 32 بت موقعة. يمكن استبدال bitwise NOT بنفي عدد صحيح من الزيادة:

 (9 -(x + 1)) >> (6 / 3) = -x / 3 (8 - x) >> 2 = -x / 3 

يمكن استبدال التحول bitwise إلى اليمين (مع الحفاظ على علامة) بتقسيم عدد صحيح بمقدار اثنين إلى درجة مساوية لمعامل على اليمين:

 (8 - x) / 2^2 = -x / 3 (8 - x) / 4 = -x / 3 

بالطبع ، هذه البدائل تعسفية للغاية ، وسوف نتحدث عن هذا لاحقًا. والآن لدينا المعادلة الخطية المعتادة ، والجذر الوحيد منها هو -24. استبدل القيمة في الجانبين الأيسر والأيمن للمعادلة الأصلية:

 9 +~ (-24) >> 6 / 3; // = 8 -(-24) / 3; // = 8 

كلا الجزأين متساويان ، مما يعني أن كل شيء ليس ميئوسا منه و -24 هو حقا حل.

البحث عن كسول

إذا رسمنا رسومات بيانية للوظائف f1 (x) = (8 -x) / 4 و f2 (x) = -x / 3 ، فسنجد بالطبع نقطة التقاطع الوحيدة للخطين عند x = -24 .



لكننا قمنا ببضع بدائل غير متساوية مع عمليات bitwise في التعبير الأيسر ، لذلك في الواقع سيكون الرسم البياني للدالة f1 مختلفًا قليلاً. بالنسبة إلى أي x ، ستكون قيمة الوظيفة عددًا صحيحًا مختلفًا عن القيمة الموجودة في السطر المستمر f1 مع وجود تحول محتمل في النطاق من -1 إلى 1. وهذا يعني أنه يمكننا قصر منطقة البحث عن الحل على يسار ويمين -24 ، حيث تكون قيم الدالتين f1 و f2 تبدأ في الاختلاف بأكثر من واحد.

للعثور على حدود منطقة البحث ، يمكنك 1) حل مشكلة عدم المساواة مع الوحدة النمطية ، أو 2) إلقاء نظرة فاحصة على الرسوم البيانية للوظائف. سنجد أن x تستحق النظر إلى المقطع [-36 ، -12]:

 | (8 - x) / 4 + x / 3 | <= 1 

للتكرار على الحلول الكاملة في بعض النطاقات المغلقة [التسول ، النهاية] ، نكتب دالة findx :

 const findx = (f, beg, end) => [...Array(end - beg + 1)].map((_, i) => i + beg).filter(f); 

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

 let eq1 = x => 9 +~ x >> 6 / 3 == -x / 3; findx(eq1, -36, -12); // [-24, -21, -18, -15] 

وبالتالي ، فإن x = [-24، -21، -18، -15] هي الحلول المرغوبة للمعادلة الأولى.

حل رسومي

يعد التعداد ناجحًا بالطبع ، ولكن دعونا لا نزال نكتشف الرسم البياني للدالة f1 حتى النهاية ونحل المعادلة بيانياً. علاوة على ذلك ، لا يعني الحل الملكية الإلزامية لوحدة تحكم المستعرض.

يتجاهل عامل التشغيل NOT bitwise ببساطة الجزء الكسري ، وبالتالي يتم تقريب النتيجة (x + 1) . مشغل إزاحة البت أكثر تعقيدًا قليلاً. لقد استبدلناها بتقسيم صحيح ، ولكن استنادًا إلى علامة رقم الأرباح ، تقريب هذه العملية النتيجة إما إلى أسفل أو لأعلى:

 10 >> 2; // = 2 -10 >> 2; // = -3 

ومع ذلك ، فنحن نعرف أن x المطلوب في النطاق [-36 ، -12]. وفقًا لذلك ، يكون المعامل الأيسر للتحول في اتجاه البت ( 8-x ) في النطاق [20 ، 44] ، أي أنه إيجابي دائمًا. وهذا بدوره يعني تقسيم عدد صحيح مع التقريب لأسفل.

بعد معرفة طبيعة العمليات ، يمكننا رسم الرسم البياني الصحيح للدالة f1 :



سنجد أربع نقاط تقاطع للوظائف في نفس الإحداثيات x = [-24، -21، -18، -15].

المعادلة الثانية

لذلك ، وصلنا إلى المعادلة الثانية:

 9 +~ x >> 6 / 3 = -x / 3 | 0 

إنه يختلف عن الأول بإضافة bitwise OR. إذا كان المعامل الأيمن لمثل هذه العملية يساوي صفرًا ، فإن النتيجة هي ببساطة قيمة المعامل الأيسر مع تجاهل الجزء الكسري.

للبدء ، دعنا نذهب إلى نفس البحث ، فقط حدد منطقة البحث. نظرًا لأن الدالة f2 لها طابع مشابه مع f1 ، من أجل الموثوقية ، يجب تلخيص التغيير المحتمل ويجب أن يكون البحث محدودًا حيث تختلف الوظائف في القيمة المطلقة بأكثر من وحدتين - هذا [-48 ، 0].

 let eq2 = x => 9 +~ x >> 6 / 3 == -x / 3 | 0; findx(eq2, -48, 0); // [-24, -21, -18, -15] 

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

 x => (9 +~ x >> 6 / 3 == -x / 3) | 0; 

في هذه الحالة ، لن يكون للـ bitwise OR أي تأثير ، لأن true | 0 = 1 . لتجنب ذلك ، من الضروري الإشارة صراحة في نص الدالة إلى أننا نقارن نتائج تعبيرين فرعيين:

 let eq2 = x => (9 +~ x >> 6 / 3) == (-x / 3 | 0); findx(eq2, -48, 0); // [-32, -29, -28, -26, -25, -24, -23, -22, -21, -19, -18, -15] 

زاد عدد الحلول. الآن دعونا نلقي نظرة على الرسوم البيانية وظيفة. قياسًا على f1 ، يقوم "سلم الخطوة" بإنشاء دالة معدلة f2 :



تتداخل أماكن الرسوم البيانية الوظيفية مع بعضها البعض ، لكننا مهتمون فقط بالنقاط ذات قيمة عددية للإحداثي س : [-32 ، -29 ، -28 ، -26 ، -25 ، -24 ، -23 ، -22 ، -22 ، -21 ، -19 ، -18 ، -15] ، 12 حل فقط. يمكن العثور على تقاطع "سلالم" مع الخطوتين 3 و 4 خوارزمية ، إذا كنت تريد.

سؤال إضافي

في المشكلة المقترحة في المؤتمر كان هناك سؤال إضافي: كان من الضروري إيجاد الحل الأدنى للمعادلة 2. لم يقال أن هذا كان بالضرورة عددًا صحيحًا ، لذا فإن الإجابة x = -32 - تبين أنها غير صحيحة.

العثور على حل بالقوة الغاشمة لن ينجح هنا ، ولكن حلها بيانيا بسيط للغاية. هذه هي أقرب قيمة x إلى -33 على اليمين:



يبدو أن س = -32. (9). ولكن هذا لا يزال غير صحيح. نظرًا لأن بيئتنا هي JavaScript ، فهذا يعني أننا في تمثيل الأرقام مقيدون بنوع البيانات المستخدمة. رقم الكتابة هو float64 ، وهو رقم الفاصلة العائمة مزدوج الدقة (IEEE 754). لتذكر هذا وتسمية دقة تقريبية كانت كافية للحصول على الثعلب أفخم!

الجانب المظلم لعمليات bitwise

كما ذُكر أعلاه ، تحول عمليات bitwise المعاملات إلى أرقام 32 بت ممثلة بالتسلسل 0 و 1 - هذا هو النطاق [-2147483648 ، 2147483647]. إذا لم يكن الرقم مناسبًا له ، فسيتم إهمال البتات الأكثر أهمية.

في المعادلة الأولى ، لا يلعب هذا أي دور ، لأنه لا توجد عملية bitwise على الجانب الأيمن. ولكن في الحالة الثانية ، يفرض تحويل الأرقام هذا تأثيرًا مثيرًا للاهتمام.

على سبيل المثال ، سيتم تمثيل الرقم -24 على النحو التالي:

 11111111111111111111111111101000 

يتم الحصول على قيمة سالبة للرقم من خلال عكس البتات (bitwise NOT) في سجل الرقم الموجب مع إضافة واحد.

أي رقم خارج النطاق ، بعد انتهاء التحويل في هذا التسلسل 32 بت ، سيكون مطابقًا في العمليات الثنائية للرقم -24. على سبيل المثال ، هذه أرقام:

 4294967272 | 0; // -24 8589934568 | 0; // -24, prepend '1' 12884901864 | 0; // -24, prepend '10' 17179869160 | 0; // -24, prepend '11' 21474836456 | 0; // -24, prepend '100' // ... 

على الجانب الأيمن من المعادلة ، قبل العملية في اتجاه البت ، نقسم x على 3. نجد x بين "المعادلات" -24 قابلة للقسمة على 3. الرقم الأقرب من هذا الرقم 12884901864. استبدلها في المعادلة:

 9 +~ 12884901864 >> 6 / 3 = -12884901864 / 3 | 0 9 +~ 12884901864 >> 2 = -4294967288 | 0 9 + 23 >> 2 = 8 8 = 8 

نتيجة القسمة على 3 (-4294967288) لا تتناسب مع الأرقام الـ 32 المخصصة ؛ عند عكس البتات ، تُفقد الإشارة أخيرًا وتبقى 8 فقط:

 00000000000000000000000000001000 

بالإضافة إلى ذلك ، يمكنك التحقق من صحة النتيجة عن طريق استدعاء وظيفة eq2 :

 eq2(12884901864); // true 

إذا فكرت في الأمر ، فبجانب هذا الجذر ، يمكنك العثور على توقعات الحلول الصحيحة الـ 11 المتبقية.

وبالتالي ، يظهر عدد كبير من الحلول الجديدة ، ولا يُنظر إلا في الأقرب إلى المعادل الإيجابي لـ -24. ومع ذلك ، هذه ليست مهمة مثل المهمة الرئيسية ، وعند تحليل القرارات من المشاركين ، تم تقييم هذه الإجابات النادرة للغاية بشكل منفصل. من أجل عدم الخلط ، يمكنك إدخال قيود على الأعداد الصحيحة المطلوبة في حالة المشكلة كتلك الموقعة 32 بت.

وأنت لا تستطيع أن تجعل! بعد ذلك ، للعثور على أصغر الجذر ، يجب الانتباه إلى حي Number.MAX_SAFE_INTEGER بعلامة سالبة ، لأن هذا الرقم يكون عددًا صحيحًا وبدقة float64 فائقة الدقة. حسنا ، ثم لوحدك.

استنتاج

نتيجة للمؤتمر ، قام معظم المشاركين بحل المشكلة عن طريق البحث الشامل ، بينما كان نطاق البحث مختلفًا تمامًا لأسباب مختلفة. لكن كما رأينا ، يكفي الركض عند 50 صحيحًا. سقط العديد من الفخاخ ذات الأولوية التشغيلية. شخص ما قرر أيضا بيانيا أن يسر. وحدات فوجئت بالإفراج عن 32 فئة. يمكنك استخدام القوة الغاشمة للمضي قدمًا في المهام. ولكن من أجل الحصول على جائزة إضافية ، كان لا يزال من الضروري إجراء بعض التحليلات شبه الرياضية.

آمل حقًا أن تكون قد أحببت فكرة هذه المهمة غير التقليدية مثل الترفيه لشكل المؤتمر. خلال السنة الماضية ، اكتسبت العديد من مهام JavaScript "المسلية". قررت جمع كل منهم في مكان واحد. اتبع الرابط إذا كنت لا تخاف: جافا سكريبت غير متوقع . لقد تم بالفعل تحديد مهام Look Complex و Broken Pipe ، والتي تم اقتراحها أيضًا في المؤتمر. نعم ، هناك العديد من هذه المجموعات ، لكن هذه المجموعة هي مجموعتي! شكرا مرة أخرى للجميع.