سلسلة - شغل مخك (15)

نأخذ إحدى الكرات جانباً ونقسم ما تبقى إلى قسمين

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

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

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

يوجد أفضل

أرجو أيضا ذكر الوقت المؤخوذ في الحل

وقت كتابة الرد

اقوم بقسم الكرات ثلاث اقسام كل قسم فيه ثلاث كرات

اقوم بوزن قسمين ويبقى قسم ثالث خارج الوزن

وإذا رجح أحدها يعني أن الكرة مع القسم الراجح وأما

إذا تساوى القسمين فإنها ستكون في القسم الثالث

اقوم بعد ذلك بأخذ القسم ( الراجح أو الثالث ) الذي يتكون من ثلاث كرات وآخذ كرتين منه وأزنهما فالراجح منهما هي الكرة المطلوبه

أما إذا تساوت الكرتين الموزونتين فإن الكرة الثاثه التي خارج الميزن هي المطلوبه

كل هذا خلال عمليتين فقط ;)

ولك تحياتي

إبراهيم:D

كيف لم تحطر ببالي :'( :'(

نعم كلام ابراهيم أفضل ...

طيب ماذا لو كانة الكرة أخف أو أثقل من البقية .؟؟؟

هذا سؤال ثاني وإلا ؟

نفس الطريقة

قسمهم 3 مجموعات. اوزن مجموعتين اذا كانوا متساويين يبقي نشيل المجموعتين و نحط كورتين من المجموعة الثالثة و نفس الخطوة اللي فاتت اذا كانوا متساويين يبقي اللي فاضلة نقارنها مع أي واحدة عشان نعرف خفيفة ولا ثقيلة

--------------

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

complexity in best cases=log n+1 (logarithm of base 3)

i couldn't get complexity in worst case so any 1 write it here please ya shabab

سلام عليكم