مهام استخلاص المعلومات. Beanpoisk_1

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

البحث الثنائي الأيمن والأيسر

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

n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) for x in b: left = -1 right = len(a) # ,     while right - left > 1: middle = (right + left) // 2 if a[middle] < x: left = middle else: right = middle left_1 = -1 right_1 = len(a) # ,     while right_1 - left_1 > 1: middle = (right_1 + left_1) // 2 if a[middle] <= x: left_1 = middle else: right_1 = middle if left == left_1 and right == right_1: print(0) #     ,     continue if right == left_1: print(right + 1, right + 1) else: print(right + 1, left_1 + 1) 

البحث الثنائي التقريبي

هنا هذا اللغز مع تطور! من الضروري هنا تحويل البحث بحيث يتم تنفيذه حتى بالنسبة للأرقام غير المدرجة في قائمة البحث. هنا نبحث أيضًا عن الوسط في "قائمة الحدود" ، ثم العنصر الذي في الوسط يُقارن بالرقم ، إذا كان أقل من ذلك ، نكتب الفهرس الأوسط + 1 (أي لا نضمّن الوسط الأخير في قائمة الحدود) إلى الحد الأيسر (وهو الفهرس) ، خلاف ذلك ، في الحدود الصحيحة نكتب الفهرس الأوسط. نحن نفعل كل هذا بينما الحدود اليسرى أصغر من اليمين. بعد العثور على اليسار واليمين ، نعتبر الحالة عندما لا يكون الرقم في القائمة وتكون المسافة إلى اليسار أقل من أو تساوي ذلك في اليمين. لذلك ، نستنتج [يسار - 1] ، وإلا يسار [.

 n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) for x in b: left = 0 right = n - 1 while left < right: middle = (left + right) // 2 if a[middle] < x: left = middle + 1 else: right = middle if left > 0 and a[left] != x and abs(a[left - 1] - x) <= abs(a[left] - x): print(a[left - 1]) else: print(a[left]) 

الجذر التربيعي و المربع المربع

تادام مهمة البحث الثنائي عن طريق الإجابة. بادئ ذي بدء ، من مكتبة الرياضيات ، نقوم بوصل وظيفة sqrt ، التي تحسب الجذر التربيعي ، وبعد ذلك نحدد 0 للحد الأيسر ، و 1e10 للحد الأيمن ، أي 10 مليارات ، بناءً على القيود المحددة في الشرط. بعد ذلك ، كما هو الحال في بحث bin النموذجي ، نحن نبحث عن الوسط ، ثم نقارنه لاحقًا. ولكن ما هو المثير للاهتمام؟ هنا الوسط هو x في المعادلة. في ضوء ذلك ، نقوم بتحديد قيمة المعادلة ومقارنتها بالإجابة الحقيقية (على سبيل المثال ، C). حسنًا ، نقوم بنقل الحدود ، حتى يكون الفرق في الحدود أقل من أو يساوي 10 مليارات ، هذه هي دقة القياس. في وقت لاحق ، نضرب بالمليون ، ثم نترجم ، ونترجم إلى قسمة حقيقية وحقيقية بمقدار مليون.

 from math import sqrt c = float(input()) left = 0 right = 1e10#1 c 10-  while right - left > 10e-10:#10   1 middle = (left + right) / 2 if middle * middle + sqrt(middle) >= c: right = middle else: left = middle #  10e6, ,   int,   10e6 print(int(round(left*10e6))/10e6) 

التحدي السهل جدا

يوجد بالفعل تحليل لهذه المهمة ، لذلك سأرفق فقط الكود.

 n, x, y = map(int, input().split()) min1 = min(x, y) if n == 1: print(min1) else: left = 0 right = n * (x + y - min1 + 1) while right - left > 1: middle = (right + left) // 2 if n - 1 <= middle // x + middle // y: right = middle else: left = middle print(min1 + left + 1) 

لتوحيد المواد ، يمكنك حل المشاكل من هنا.