Algorithms2

‫الخوارزميات ‪Algorithms‬‬ ‫الجلسة الثالثة‪:‬‬ ‫الخوارزميات الجشعة (‪:)Greedy Algorithms‬‬ ‫يعتبر هذا النوع ذو نظر قصير لحل المشكلة‪ ،‬حيث يعتمد هذا النوع من ال ‪ Algorithms‬على الخيار‬ ‫الذي يظهر أنه الأفضل في كل خطوة من الحل دون النظر لأي عوامل أخرى قد تؤثر على الحل في الخطوات‬ ‫اللاحقة‪ ،‬ويسمى هذا الخيار (‪ ،)Locally Optimal Step‬وذلك على أمل أن نصل من خلاله لأفضل حل‬ ‫(‪ ،)Globally Optimal Solution‬أي أن هذا ال ‪ Algorithm‬يعتمد على الخطوة القادمة فقط (الظاهرة‬ ‫أمامه الأفضل حاليًا فقط) على أمل الوصول بالنهاية للحل الأفضل‪.‬‬ ‫مزايا ‪:Greedy‬‬ ‫‪ ‬يكون الحل بسيط‪.‬‬ ‫‪ ‬كتابته تكون سهلة نسبيًا مثل ‪.Brute Force‬‬ ‫سلبيات ‪:Greedy‬‬ ‫‪ ‬قد لا نصل للحل الأفضل دائ ًما‪ ،‬لأن بعض المشاكل نحتاج فيها أكثر للتفكير بالخطوات المستقبلية التي قد‬ ‫تؤثر على نتيجة الحل‪ ،‬وليس التفكير بالخطوة الحالية فقط‪ ،‬أي أن (‪ )Locally Optimal Step‬ليست‬ ‫دائ ًما تجعلنا نصل (‪.)Globally Optimal Solution‬‬ ‫*******‬ ‫مثال رقم (‪ )1‬على ‪:Greedy‬‬ ‫المطلوب (المشكلة)‪:‬‬ ‫لنفرض أننا نريد سحب مبلغ مالي من البنك‪ ،‬وفئات العملات المتوفرة هي (‪ )50,20,10,5,1‬دينار‪،‬‬ ‫فمثلاً لو أردنا سحب مبلغ (‪ )29‬دينار يمكن سحبهم بالفئات التالية‪ )1*50+4*10+2*1( :‬وبالتالي يكون عدد‬ ‫الأوراق (‪ ،)7‬أو بالفئات التالية (‪ )1*50+2*20+2*1‬وعدد الأوراق (‪ ،)5‬أي أن عدد الأوراق في المجموعة‬ ‫الثانية أقل من الأولى‪ ،‬المطلوب عمل برنامج بحيث‪ :‬يعطيني أقل عدد أوراق ممكن للمبلغ المسحوب‪.‬‬ ‫سنقوم بإدخال رقم يمثل المبلغ التي سيتم سحبها وسنرمز له بالرمز ‪ ،m‬وسيكون الرقم المدخل ‪ m‬قيمته‬ ‫بين ‪ 1‬و ‪ 111111‬أي (‪ ،)1<=m<=100000‬والمطلوب طباعة رقم يمثل أقل عدد ممكن من الأوراق‬ ‫المسحوبة‪.‬‬ ‫الحل‪:‬‬ ‫‪Page 1‬‬

‫يجب أن نأخذ بعين الاعتبار أنه لأخذ أقل عدد ممكن من الأوراق يجب أن نأخذ أكبر عدد ممكن من أكبر‬ ‫فئة من العملات في كل مرة‪ ،‬أي إذا كان الرقم أكبر من ‪ 51‬فيجب أن نأخذ فئة ال‪ 51‬بأكبر عدد ممكن من‬ ‫الأوراق في المبلغ‪ ،‬ثم بعدها نبحث عن أكبر عدد ممكن من الأوراق من فئة ‪ 91‬من المبلغ الذي تبقى بعد‬ ‫احتساب المبلغ الذي ينطبق على فئة ال ‪ ،51‬ثم نأخذ أكبر عدد ممكن مما تبقى من المبلغ للفئة ‪ ،11‬وهكذا حتى‬ ‫ينتهي المبلغ‪.‬‬ ‫*******‬ ‫‪Page 2‬‬

‫مثال رقم (‪ )2‬على ‪:Greedy‬‬ ‫المطلوب (المشكلة)‪:‬‬ ‫لنفرض أن لدينا كمية من الماء وعدد معين من الخزانات ولكل خزان سعة معينة‪ ،‬ونريد توزيع كمية‬ ‫الماء على الخزانات بحيث نقوم بتعبئة الماء في أقل عدد ممكن من الخزانات‪.‬‬ ‫سنقوم بإدخال رقمين الأول الذي يمثل كمية الماء المطلوب توزيعها وسنرمز له بالرمز ‪ ،w‬والرقم‬ ‫الثاني يمثل عدد عدد الخزانات المتوفرة وسنرمز له بالرمز ‪ n‬وستكون قيمتها بين ‪ 1‬و ‪ 11111‬أي‬ ‫(‪ ،)1<=n<=10000‬ثم بعدها سيتم إدخال مصفوفة من الأرقام تمثل سعة الخزانات التي عددها ‪ ،n‬وسنفترض‬ ‫أن كمية الماء أقل من أو تساوي سعة الخزانات أي بمعنى آخر بالتأكيد سيتم توزيع كل كمية الماء‪ ،‬والمطلوب‬ ‫طباعة رقم يمثل أقل عدد ممكن من الخزانات التي نحتاجها لتعبئة كمية الماء‪.‬‬ ‫الحل‪ :‬يجب أن نأخذ بعين الاعتبار أنه لأخذ أقل عدد ممكن من الخزانات يجب أن نبدأ بتعبئة أكبر خزان موجود‪،‬‬ ‫ثم نبحث للكمية المتبقية من الماء عن أكبر خزان بعده‪ ،‬وهكذا حتى ننتهي من تعبئة كامل كمية الماء‪ ،‬كما يجب‬ ‫أن نأخذ بعين الاعتبار أن ال ‪ array‬يجب أن تكون مرتبة من الأكبر للأصغر (لترتيب ال ‪ array‬سنستعين‬ ‫بمكتبة ‪ Algorithm‬التي تحتوي على أمر جاهز للترتيب وهو ‪ sort‬وهذا الأمر يرتب ال ‪ array‬من الأصغر‬ ‫للأكبر)‪.‬‬ ‫*******‬ ‫‪Page 3‬‬

‫مثال رقم (‪ )3‬على ‪:Greedy‬‬ ‫لنفرض أن لدينا مجموعة من الأرقام السالبة والموجبة (بدون ‪ ،)1‬ونريد أن‬ ‫المطلوب (المشكلة)‪:‬‬ ‫نأخذ أي مجموعة جزئية (‪ )subset‬من هذه الأرقام بحيث يكون لها أعلى ناتج ضرب ممكن‪ ،‬فمثلاً لو أن لدينا‬ ‫الأرقام (‪ )3,7,-9,-5,5,-2‬فإننا سنأخذ (‪)3*7*-9*-5*5=4725‬لأنها تعطينا أعلى ناتج ضرب ممكن‪ ،‬سنقوم‬ ‫بإدخال رقم يمثل عدد الأرقام التي نريدها وسنرمز له بالرمز ‪ n‬وستكون قيمتها بين ‪ 1‬و ‪ 11‬أي‬ ‫(‪ ،)1<=n<=18‬ثم بعدها سيتم إدخال الأرقام في مصفوفة ‪ a‬وستكون قيمتها بين ‪ -10‬و ‪ 11‬ولا تساوي ‪ 1‬أي‬ ‫(‪.)-10<=a[i]<=10, a[i]!=0‬‬ ‫يجب أن نأخذ بعين الاعتبار أنه إذا كانت الأرقام موجبة فسوف نأخذها جميعا لأنها ستزيد قيمة‬ ‫الحل‪:‬‬ ‫الناتج‪ ،‬أما إذا كانت الأرقام سالبة فيجب أخذها بأعداد زوجية ليصبح الناتج موجبًا أما إذا كانت فردية فسيكون‬ ‫الناتج سالبًا ولن يكون الجواب المطلوب‪ ،‬وكذلك يجب أن يكون الرقم السالب الذي لن نأخذه هو الرقم الأقرب‬ ‫للصفر (بمعنى أن ‪ -2‬أقرب للصفر من ‪.)-5‬‬ ‫*******‬ ‫‪Page 4‬‬

‫حيث لا يعمل ‪:Greedy‬‬ ‫المشكلة (‪ )1‬الحقيبة ‪ :Knapsack Problem‬لو فرضنا أن لدينا حقيبة بسعة معينة ولدينا مجموعة من‬ ‫الأغراض لكل منها قيمة ووزن معين‪ ،‬المطلوب تعبئة الحقيبة بالأغراض التي لها أكبر مجموع من القيمة ولا‬ ‫تتجاوز أوزانهم سعة الحقيبة‪.‬‬ ‫في الجهة (‪ )1‬من الصورة أعلاه من المنطقي أن نضع في الحقيبة (‪ )A,B,D‬لآنها تعطي قيمة ‪11‬‬ ‫والوزن ‪ ،11‬ولكن إذا أردنا حل المشكلة ب ‪ Greedy‬بأخذ الأغراض التي لها أعلى قيمة مقارنة بوزنها (أي‬ ‫نقسم ‪ ،)V/W‬إلا أن هذه النتيجة لن تعطينا دائ ًما الحل الصحيح كما في الجهة (‪ )9‬من الصورة أعلاه‪ ،‬حيث‬ ‫يظهر أن ‪ B‬أفضل من ‪ A‬ولكن في الحقيقة أن الحل الأفضل هو ‪ A‬وليس ‪.B‬‬ ‫المشكلة (‪ :)2‬لو فرضنا أن لدينا سلسلة أرقام وصعوبة الانتقال من مربع لآخر هي الفرق بينهما‪ ،‬ويمكننا‬ ‫الانتقال إما خطوة للمربع التالي مباشرة أو خطوتين للمربع يلي التالي‪ ،‬والمطلوب السير من أول السلسة لآخرها‬ ‫وتكون الصعوبة أقل ما يمكن‪.‬‬ ‫في الجهة (‪ )1‬من الصورة أعلاه بطريقة ‪ Greedy‬الحل الانتقال من ‪ 1‬إلى ‪ 2‬مباشرة وتكون الصعوبة‬ ‫‪ 1‬بدلاً من ‪ ،5‬لكن ‪ Greedy‬غير عملي في الجهة (‪ )9‬من الصورة أعلاه‪ ،‬لأنه سينتقل من ‪ 9‬إلى ‪ 1‬ثم سيضطر‬ ‫للانتقال من ‪ 1‬إلى ‪ 5‬ومجموع الصعوبة سيكون ‪ ،5‬بينما الحل الأفضل الانتقال من ‪ 9‬إلى ‪ 4‬ثم من ‪ 4‬إلى ‪5‬‬ ‫وتكون الصعوبة ‪.3‬‬ ‫*******‬ ‫‪Page 5‬‬

‫الجلسة الرابعة‪:‬‬ ‫خوارزميات المؤشرين (‪:)Two Pointers‬‬ ‫يعتمد هذا النوع على مؤشرين ويستخدم عادة في ال ‪ array‬أو ما يشبه ال ‪ array‬ونحتاج غالبًا أن تكون‬ ‫ال ‪ array‬مرتبة‪ ،‬هذان المؤشران لديهما مرونة كبيرة حيث يمكن أن نضع أحدهما في البداية والآخر في النهاية‬ ‫أو نضع كل واحد منهما في بداية ‪ ،array‬كما يمكن نجعلهما يتحركان م ًعا أو أن يتحرك كل منهما بشكل منفصل‬ ‫عن الآخر بنا ًء على شرط معين‪.‬‬ ‫مثال رقم (‪ )1‬على ‪( Two Pointers‬لتوضيح طريقة عمله)‪:‬‬ ‫المطلوب (المشكلة)‪ :‬لو كانت لدينا ‪ array‬مرتبة تصاعديًا تحتوي على الأرقام (‪)1,1,2,3,5,6,8,10,11‬‬ ‫والمطلوب أن نبحث عن رقمين فيها يكون مجموعهما ‪ x=10‬وإذا لم نجد يخبرني البرنامج أنه لا يوجد‪ ،‬من‬ ‫الممكن أن نحل هذه المشكلة باستخدام ‪ Brute Force‬والمرور على كل الثنائيات الممكنة (أي نجمع أول رقم‬ ‫مع كل رقم في ال ‪ array‬من بدايتها لنهايتها حتى نجد مجموع يطابق ‪ )x‬وذلك باستخدام ‪ loop‬داخل ‪loop‬‬ ‫(‪ )Nested Loops‬وبذلك تكون ال ‪ complexity‬هي )‪ ،O(n2‬كما في الكود الموجود بالصورة أدناه‪:‬‬ ‫ولكن يمكننا أن نستغل أن ال ‪ array‬مرتبة ونخفف ال ‪ complexity‬وذلك باستخدام ‪:Two Pointers‬‬ ‫حيث سيكون لدينا مؤشرين‪ :‬الأول في بداية ال ‪ array‬والثاني في نهايتها‪ ،‬وسنقوم بجمع الرقمين وفي هذه الحالة‬ ‫(‪ )1+11=12‬وهو رقم أكبر من الرقم المطلوب‪ ،‬ومعنى ذلك أننا بحاجة لرقم أصغر‪ ،‬ولأن ال ‪ array‬مرتبة‬ ‫فهذا يعني نعود بالمؤشر الثاني الذي في النهاية خطوة لليسار (للعنصر الذي يسبق ‪ )11‬وكذلك لا يزال المجموع‬ ‫أكبر من المطلوب (‪ )1+10=11‬ولذلك سنعود بالمؤشر الثاني خطوة أخرى لليسار‪ ،‬وفي هذه الحالة أصبح‬ ‫المجموع أصغر من الرقم المطلوب (‪ )1+8=9‬وهذا يعني أننا أصبحنا بحاجة لرقم أكبر‪ ،‬ولذلك سنحرك المؤشر‬ ‫الأول الذي في البداية خطوة لليمين‪ ،‬ولأن الرقم الثاني في ال ‪ array‬أي ًضا ‪ 1‬فسيبقى المجموع أصغر من الرقم‬ ‫المطلوب (‪ )1+8=9‬ولذلك نحن لا زلنا بحاجة لرقم أكبر وسنحرك المؤشر الأول خطوة أخرى لليمين‪ ،‬وبذلك‬ ‫سنكون وصلنا لمجموع يطابق الرقم المطلوب (‪ ،)2+8=10‬وبذلك سنلاحظ أن ال ‪ complexity‬ستكون )‪O(n‬‬ ‫في أسوأ حالاتها (أسوأ حالة أن يستمر كلا المؤشرين بالتحرك إلى أن يلتقيا مع بعضهما)‪.‬‬ ‫*******‬ ‫‪Page 6‬‬

‫استكمال حل مشكلة المثال رقم (‪ )1‬على ‪:Two Pointers‬‬ ‫في البداية يجب معرفة طريقة تعريف المؤشرين الذين سيؤشران على بداية ال ‪ array‬ونهايتها‪ ،‬فهناك‬ ‫أكثر من طريقة ولكن أسهل طريقة هي تعريف المؤشرين كمتغيرين من نوع ‪ int‬حيث سيؤشر كل منهما على‬ ‫ال ‪ index‬في ال ‪ ،array‬وكذلك يجب أن نحدد متى سيتوقف المؤشرين (وببساطة سيتوقفان عندما يلتقيان‪ ،‬أي‬ ‫عندما تتساوى قيمتهما) أي أن المؤشرين سيستمران بالتحرك طالما أن المؤشر الأول أقل من المؤشر الثاني‪،‬‬ ‫لأنه لا يوجد معنى لأن يتعدى مؤشر مكان التقائه مع الآخر وتنعكس مواقعهما فهذا يعني أنهما سيمران على‬ ‫عناصر تم المرور عليها مسبقًا‪ .‬سنقوم بإدخال ‪ n‬الذي سيمثل حجم ال ‪ array‬وسيكون بين ‪ 9‬و ‪ 1111‬أي‬ ‫(‪ ،)2<=n<=1000‬وكذلك سنقوم بإدخال ‪ x‬وهو الرقم المطلوب‪ .‬سنقوم بإدخال عناصر ال ‪( array‬مرتبين‬ ‫تصاعديًا خلال الإدخال) وسنرمز لها بالرمز ‪ ،a‬والمطلوب طباعة كلمة (‪ )yes‬إضافة للرقمين الذين مجموعهما‬ ‫يساوي ‪ x‬إذا وجدنا رقمين مجموعهما يساوي ‪ ،x‬أو كلمة (‪ )no‬إذا لم نجد أي رقمين مجموعهما يساوي ‪.x‬‬ ‫ملاحظة‪ :‬إذا أردنا إدخال عناصر المصفوفة غير مرتبة فيجب الاستعانة بمكتبة ‪ Algorithm‬وتطبيق الأمر‬ ‫‪ sort‬بعد إدخال عناصر المصفوفة لترتيبها تصاعديًا‪ ،‬كما في المثال رقم (‪ )2‬في ‪.Greedy‬‬ ‫*******‬ ‫‪Page 7‬‬

‫مثال رقم (‪ )2‬على ‪:Two Pointers‬‬ ‫المطلوب (المشكلة) (‪:)Palindrome‬‬ ‫‪ Palindrome‬هي مصطلح يطلق على الكلمة التي يمكن قراءتها بنفس الطريقة من اليمين لليسار ومن‬ ‫اليسار لليمين مثل (‪ )racecar‬التي يمكن قراءتها بنفس الطريقة بالاتجاهين‪ ،‬أما (‪ )eureka‬فلا يمكن قراءتها‬ ‫بنفس الطريقة بالاتجاهين (‪.)akerue‬‬ ‫سنقوم بإدخال ‪( string‬سلسلة أحرف‪ /‬كلمة أو مجموعة كلمات) واحدة طولها بين ‪ 9‬و ‪،1111‬‬ ‫والمطلوب تحويل ال ‪ string‬التي تم إدخالها إلى ‪ Palindrome‬بتغيير أقل عدد ممكن من الأحرف‪ ،‬فمثلاً لو‬ ‫كانت الكلمة ‪ Palindrome‬في الأصل فلن نغير أي حرف‪ ،‬المطلوب طباعة رقم يمثل عدد الأحرف التي تم‬ ‫تغييرها ثم ال ‪ string‬الجديدة بعد تغيير الأحرف‪.‬‬ ‫ملاحظة‪ :‬يمكننا التعامل مع ال ‪ string‬بأنه عبارة عن ‪ array‬من الأحرف التي تش ّكل كلمة أو جملة‪.‬‬ ‫سنستخدم مؤشرين في البداية والنهاية‪ ،‬ولكن في هذه المرة سيتم تحريكهما م ًعا في كل خطوة‪،‬‬ ‫الحل‪:‬‬ ‫في كل مرة سيتم مقارنة الحرفين الذين عليهما المؤشرين‪ ،‬وإذا كانا متشابهين لا يقوم بأي تغيير وينتقل إلى‬ ‫التأشير إلى الحرفين التاليين وإذا كانا مختلفين سيتم تغيير حرف واحد منهما‪ ،‬وسيتوقف المؤشران عندما يلتقيان‬ ‫مع الأخذ بعين الاعتبار أنه إذا كانت عدد حروف ال ‪ string‬فردية فلن يتم تغيير الحرف الذي بالوسط مهما كان‬ ‫لأنه لن يؤثر على الجواب‪.‬‬ ‫*******‬ ‫‪Page 8‬‬

‫مثال رقم (‪ )3‬على ‪:Two Pointers‬‬ ‫المطلوب (المشكلة)‪:‬‬ ‫لنفترض أن لدينا أشخاص موزعين على غرفتين‪ ،‬ونحن نعرف أعمار جميع الأشخاص في الغرفتين‪،‬‬ ‫والمطلوب توزيع الأشخاص إلى مجموعات بحيث يكون في كل مجموعة شخصين (شخص من كل غرفة)‬ ‫بشرط أن يكون الفرق بين عمرهما أقل من ‪ ،9‬ولا يوجد مشكلة إذا بقي أشخاص من أي غرفة بدون مجموعات‪،‬‬ ‫فالمطلوب توزيع أكبر عدد ممكن من المجموعات‪.‬‬ ‫ستكون المدخلات رقمان ‪ n‬و ‪ m‬يمثلان عدد الأشخاص في كل غرفة‪ ،‬ويكون عدد الأشخاص في كل‬ ‫غرفة بين ‪ 1‬و ‪ ،1111‬ثم يتم إدخال أعمار الأشخاص في كل غرفة‪ ،‬والمطلوب طباعة رقم يمثل عدد‬ ‫المجموعات الممكن عملها‪.‬‬ ‫الحل‪:‬‬ ‫أولا يجب أن نرتب الأشخاص حسب الأعمار في كل غرفة‪ ،‬ثم نضع مؤشرين الأول يؤشر على أول‬ ‫عنصر في ال‪ array‬الأولى والثاني على أول عنصر في ال‪ array‬الثانية‪ ،‬ونقارن القيم التي عليها المؤشرين‪،‬‬ ‫إذا كان الفرق بينهما أقل من ‪ 9‬سنضعهم في نفس المجموعة ثم نحرك المؤشرين خطوة لليمين‪ ،‬إذا كان الفرق ‪9‬‬ ‫فأكثر سنحرك المؤشر الذي يؤشر على الرقم الأصغر‪ ،‬وهكذا حتى يتعدى أحد المؤشرين نهاية ال‪array‬‬ ‫الخاصة به‪.‬‬ ‫‪Page 9‬‬

‫الكود‪:‬‬ ‫*******‬ ‫‪Page 10‬‬

‫حيث لا يعمل ‪:Two Pointers‬‬ ‫المشكلة (‪:)1‬‬ ‫مثال رقم (‪ )1‬على ‪ :Two Pointers‬لو فرضنا أن ال ‪ array‬التي تم إدخالها لم يتم إدخالها بترتيب‬ ‫تصاعدي وأدخلت الأرقام عشوائيًا (أي أن ال ‪ array‬غير مرتبة)‪ ،‬عندها لن نتمكن من استخدام ‪Algorithm‬‬ ‫ال ‪ ،Two Pointers‬لأننا اعتمدنا في حل المشكلة على أن المؤشر الأول يؤشر على أصغر عنصر في‬ ‫ال‪ array‬والمؤشر الثاني يؤشر على أكبر عنصر فيها وإذا أردنا أن نجعل الرقم أصغر نحرك المؤشر الثاني‬ ‫لليسار وإذا أردنا أن نجعل الرقم أكبر نحرك المؤشر الأول لليمين‪ ،‬فإذا كانت ال‪ array‬غير مرتبة لن نستطيع‬ ‫أن نضمن أن المؤشر الأول يؤشر على أصغر عنصر في ال ‪ array‬وأن المؤشر الثاني يؤشر على أكبر عنصر‬ ‫فيها‪ ،‬لذلك لن يكون ‪ Two Pointers‬فعالاً في هذه الحالة‪.‬‬ ‫وبشكل عام نحن بحاجة دائ ًما أن يكون لدينا رؤية واضحة لطريقة تحريك المؤشرين في حل المشكلة‪،‬‬ ‫وإلا لن نتمكن من حل المشكاة باستخدام ‪.Two Pointers‬‬ ‫المشكلة (‪:)2‬‬ ‫لنفرض أن لدينا ‪ array‬تحتوي على أرقام موجبة وسالبة (‪ ،)11,6,8,-2,3,7,-9,7,-5,-3‬والمطلوب‬ ‫إيجاد ال‪ sub array‬التي لها أعلى مجموع ممكن‪ ،‬قد يعتقد البعض أنه من الممكن وضع مؤشرين على بداية‬ ‫ال‪ array‬ثم البدء بجمع الأرقام وتحريك المؤشر الأول لليمين طالما كانت الأرقم موجبة‪ ،‬وعند الوصول لرقم‬ ‫سالب نتجاوز هذا الرقم ونضع المؤشر الثاني عند أول رقم موجب بعده ونبدأ باحتساب ‪ sub array‬جديدة‪ ،‬إلا‬ ‫أن هذه الطريقة لن تعطينا الجواب الصحيح دائ ًما لأنه من الممكن أن تحتوي ال‪ sub array‬على أرقام سالبة‬ ‫ومع ذلك يكون لها أكبر مجموع ممكن كما في الصورة أدناه للأرقام (‪ )11+6+8-2+3+7=33‬حيث أن هذه‬ ‫الأرقام تعطينا أكبر مجموع ل‪ sub array‬من هذه ال‪( array‬أي أنه من الممكن وجود أدثر من ‪sub array‬‬ ‫لأرقام موجبة وبينها أرقام سالبة إلا أن مجموعهم سيكون أكبر من أي مجموع لأي ‪ sub array‬من الأرقام‬ ‫الموجبة)‪ ،‬وبالتالي فإن فكرة تحريك المؤشرين على أساس الأرقام الموجبة والسالبة كانت فكرة خاطئة‪.‬‬ ‫*******‬ ‫‪Page 11‬‬

‫الجلسة الخامسة‪:‬‬ ‫خوارزميات البحث الثنائي (‪:)Binary Search‬‬ ‫لو كان لدينا ‪ array‬ونريد البحث عن رقم معين فيها فبالوضع الطبيعي أننا سنبدأ بالبحث من أول‬ ‫ال‪ array‬لآخرها‪ ،‬وطريقة البحث هذه تسمى (‪ )linear search‬أو (‪ )sequential search‬وال‪complexity‬‬ ‫له في أسوأ حالة )‪ ،O(n‬ولكن لو فرضنا أننا نريد البحث عن كلمة في قاموس وهذا القاموس لا يوجد به علامات‬ ‫تحدد بداية كل حرف (عل ًما أن القاموس يكون دائ ًما مرتب أبجديًا)‪ ،‬لو أردنا البحث بطريقة ‪ linear search‬أي‬ ‫من البداية سيكون الوصول للكلمة بطيء وبحاجة لوقت طويل‪ ،‬والحل الأفضل أن نفتح القاموس من منتصفه‬ ‫ونشاهد الحرف الذي فتحنا عليه‪ ،‬فإذا كان الحرف الذي تبدأ به الكلمة من الحروف التي في الجزء الذي قبل‬ ‫المنتصف نهمل الجزء الذي بعده وإذا كانت في الجزء الذي بعد المنتصف نهمل الجزء الذي قبله‪ ،‬أي لو فرضنا‬ ‫أن الكلمة التي نبحث عنها تبدأ بالحرف ‪ H‬وفتحنا القاموس على حرف ‪ M‬سنعلم أن الكلمة في الجزء الذي قبل‬ ‫‪ M‬ولذلك سنهمل الجزء الذي بعد ‪ M‬من القاموس وسنعيد نفس الخطوات على النصف الأول من القاموس‪ ،‬أي‬ ‫أننا سوف نعتبر أن القاموس هو الأحرف من ‪ A‬إلى ‪ M‬وسنفتح الجزء الذي قبل ‪ M‬من منتصفه ونتأكد من‬ ‫مكان الحرف ‪ ،H‬أي أننا في كل مرة سوف نقسم المجموعة إلى نصفين ونهمل النصف الذي تأكدنا أن الجواب‬ ‫ليس به ثم نقسم النصف المتبقي إلى نصفين حتى نصل للحل‪.‬‬ ‫أي أن ‪ Binary Search‬يعتمد أولاً على أن تكون البيانات مرتبة‪ ،‬ويعتمد على أنه في كل مرة سنقوم‬ ‫بتقسيم المنطقة التي نبحث فيها إلى قسمين حتى نصل للحل‪ ،‬ولذلك سمي ‪( Binary Search‬البحث الثنائي)‪.‬‬ ‫إي أننا لو فرضنا أن عدد العناصر ‪ n‬فإن ال‪ complexity‬لل‪ Binary Search‬هي عدد المرات التي سنقسم‬ ‫فيها ‪ n‬قبل أن تصبح ‪ )n/2( 1‬ولنعبر عن هذا الرقم نستخدم اللوغاريثم أي أن ال‪ complexity‬هي )‪O(log n‬‬ ‫واللوغاريثم يجعل ال‪ complexity‬أصغر بكثير‪ ،‬أي أن )‪.O(log n)<O(n‬‬ ‫*******‬ ‫‪Page 12‬‬

‫مثال رقم (‪ )1‬على ‪:Binary Search‬‬ ‫المطلوب (المشكلة)‪:‬‬ ‫هو أبسط مثال على ‪ Binary Search‬وهو البحث عن رقم معين في ‪ array‬مرتبة وإذا وجدناه نطبع‬ ‫ال‪ index‬الخاص به وإذا لم نجده نطبع أنه غير موجود‪.‬‬ ‫المدخلات ستكون ‪ n‬وهو حجم ال‪ array‬وستكون بين ‪ 1‬و ‪ ،100000‬وكذلك ‪ x‬وهو الرقم الذي نريد‬ ‫البحث عنه‪ ،‬ثم بعدها يتم إدخال عناصر ال‪ array‬مرتبة تصاعديًا (إذا لم يتم إدخالها مرتبة فيجب الاستعانة‬ ‫ب‪ sort‬لترتيبها‪ ،‬لأن ‪ Binary Search‬إلا إذا كانت ال‪ array‬مرتبة)‪ ،‬والمطلوب طباعة ال‪ index‬للرقم إذا‬ ‫وجدناه و(‪ (1-‬إذا لم نجده‪.‬‬ ‫الحل‪:‬‬ ‫في البداية سنقوم بتعريف المتغيرات ونقوم بإدخال القيم‪ ،‬بعد ذلك سنحتاج لتعريف متغير من نوع ‪bool‬‬ ‫سنسميه ‪ found‬لنعرف من خلاله أننا وجدنا الرقم أم لم نجده وستكون قيمته في البداية ‪ ،false‬بعد ذلك سنبدأ‬ ‫بجزء ‪ Binary Search‬الذي يشبه طريقة المؤشرين ولكن سيكون لدينا ‪ 3‬مؤشرات‪( :‬الأول ‪ left‬في أقصى‬ ‫اليسار وستكون قيمته ‪ ،1‬والثاني ‪ right‬في أقصى اليمين وستكون قيمته ‪ ،n-1‬والثالث ‪ mid‬الذي سيكون بين‬ ‫‪ left‬و ‪ right‬وقيمته هي التي سنتأكد منها لنعرف الجزء الذي سنبحث فيه في الخطوة التالية وهو الذي سنقسم‬ ‫فيه ال‪ array‬إلى جزأين في كل مرة ولن نضع له قيمة في البداية لأننا سنحسبه في كل مرة)‪.‬‬ ‫داخل ال‪ loop‬سنحسب أولاً قيمة ‪ mid‬التي ستكون عبارة عن المعدل بين ‪ left‬و ‪ right‬أي‬ ‫(‪ ،)mid=(left+right)/2‬ثم سنقارن العنصر الذي يؤشر عليه ‪ )a[mid]( mid‬مع الرقم ‪ x‬وإذا كان يساويه‬ ‫فهذا يعني أننا وجدنا ‪ x‬فسنغير حالة ‪ found‬إلى ‪ true‬ونخرج من ال‪ ،loop‬إذا لم يكن كذلك فهذا يعني أن الرقم‬ ‫الذي يؤشر عليه ‪ mid‬إما أصغر من ‪ x‬وبالتالي سنبحث بالجزء الذي على يمين ‪ mid‬أو أكبر من ‪ x‬وسنبحث‬ ‫بالجزء الذي على يسار ‪ ،mid‬لو فرضنا أن قيمة ‪ x=7‬مثلاً فهذا يعني أن ‪ x‬أصغر من الذي يؤشر عليه ‪mid‬‬ ‫ولذلك سنهمل النصف الأيمن من ال‪ array‬ونجعل نهاية البحث هو ال‪ index‬الذي يسبق ‪ mid‬أي‬ ‫(‪ )right=mid-1‬ولو كان ‪ x‬أكبر من الرقم الذي يؤشر عليه ‪ mid‬سنهمل النصف الأيسر ونجعل بداية البحث‬ ‫ال‪ index‬الذي يلي ‪ mid‬أي (‪ ،)left=mid+1‬والآن أصبح البحث في أحد جزأي ال‪ array‬أي قسمناها‬ ‫لنصفين وأخذنا النصف الذي يهمنا فقط أي أصبحنا نبحث في ‪ array‬أصغر‪.‬‬ ‫وسنستمر بهذه الطريقة حتى نجد الرقم أو نتأكد أننا ليس لدينا إلا عنصر واحد في ال‪ ،array‬وهذا يعني‬ ‫أن ‪ left=right=mid‬ولم نجد الرقم الذي يساوي ‪ ،x‬أي أن شرط الخروج من ال‪ loop‬سيكون أن ‪left‬‬ ‫أصبحت أكبر من ‪ right‬وهذا يعني المؤشر الأيسر تجاوز المؤشر الأيمن دون العثور على الرقم‪.‬‬ ‫‪Page 13‬‬

‫الكود‪:‬‬ ‫*******‬ ‫‪Page 14‬‬

‫مثال رقم (‪ )2‬على ‪:Binary Search‬‬ ‫المطلوب (المشكلة)‪ :‬لنفرض أن لدينا ‪ array‬مرتبة بحيث تكون تصاعدية في البداية ثم بعدها تنازلية‪ ،‬مثلاً‬ ‫بهذا الشكل (‪ ،)10,12,15,19,17,9‬والمطلوب إيجاد أكبر عنصر في ال‪ array‬باستخدام ‪.Binary Search‬‬ ‫المدخلات ستكون ‪ n‬وهو حجم ال‪ array‬وستكون بين ‪ 3‬و ‪ ،1000‬ثم بعدها يتم إدخال عناصر‬ ‫ال‪ ،array‬والمطلوب طباعة أكبر رقم في ال‪ array‬باستخدام ‪.Binary Search‬‬ ‫ستكون الطريقة شبيهة بالطريقة التي كانت في المثال رقم (‪ )1‬على ‪ ،Binary Search‬ولكن‬ ‫الحل‪:‬‬ ‫في هذه المرة بدلاً من أن نقارن ‪ mid‬مع ‪ x‬سنقارن ‪ mid‬مع الرقم الذي قبله والرقم الذي بعده (إذا كان الذي قبله‬ ‫والذي بعده أصغر منه فهذا يعني أنه أكبر عنصر في المجموعة‪ ،‬وإذا كان أحدهما أكبر فسوف نتحرك تجاه‬ ‫الرقم الأكبر)‪.‬‬ ‫*******‬ ‫‪Page 15‬‬