تيدمان

تيدمان

مشكلة بحاجة إلى حل

أنت تعرف بالفعل عن الانتخابات التعددية، التي تتبع خوارزمية بسيطة للغاية لتحديد الفائز في الانتخابات: يحصل كل ناخب على صوت واحد، ويفوز المرشح الذي حصل على أكبر عدد من الأصوات.

لكن التصويت الأغلبي له بعض العيوب. ماذا يحدث، على سبيل المثال، في انتخابات تضم ثلاثة مرشحين، ويتم الإدلاء بالأصوات أدناه؟

سيؤدي التصويت بالأغلبية هنا إلى إعلان التعادل بين أليس وبوب، حيث أن لكل منهما صوتين. لكن هل هذه هي النتيجة الصحيحة؟

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

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

يمكن أن يؤدي التصويت بالاختيار المُصنف أيضًا إلى حل عيب محتمل آخر للتصويت التعددي. ألق نظرة على صناديق الاقتراع التالية.

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

أليس، في هذه الانتخابات، هي من يُطلق عليها "الفائزة في كوندورسيه" في الانتخابات: الشخص الذي كان سيفوز في أي مواجهة مباشرة ضد مرشح آخر. لو كانت الانتخابات تقتصر على أليس وبوب فقط، أو فقط أليس وتشارلي، لكانت أليس قد فازت.

طريقة التصويت Tideman (المعروفة أيضًا باسم "الأزواج المُصنفة") هي طريقة تصويت حسب الاختيار المُصنف والتي تضمن الحصول على الفائز من Condorcet في الانتخابات إذا كان موجودًا. في ملف اسمه tideman.c في مجلد يسمى tideman، قم بإنشاء برنامج لمحاكاة الانتخابات بطريقة التصويت Tideman.

تجريبي

رمز التوزيع

$

wget https://cdn.cs50.net/2026/x/psets/3/tideman.zip

unzip tideman.zip

rm tideman.zip

cd tideman

tideman/ $

ls

الخلفية

بشكل عام، تعمل طريقة Tideman من خلال إنشاء "رسم بياني" للمرشحين، حيث يشير السهم (i.e. edge) من المرشح A إلى المرشح B إلى أن المرشح A يفوز على المرشح B في مباراة وجهاً لوجه. إذن، سيبدو الرسم البياني للانتخابات المذكورة أعلاه كما هو موضح أدناه.

السهم من Alice إلى Bob يعني أن المزيد من الناخبين يفضلون Alice على Bob (5 يفضلون Alice، 4 يفضلون Bob). وبالمثل، تعني الأسهم الأخرى أن المزيد من الناخبين يفضلون أليس على تشارلي، وأن المزيد من الناخبين يفضلون تشارلي على بوب.

بالنظر إلى هذا الرسم البياني، تقول طريقة Tideman أن الفائز في الانتخابات يجب أن يكون "مصدر" الرسم البياني (i.e. المرشح الذي ليس لديه سهم يشير إليه). في هذه الحالة، المصدر هو Alice - أليس هي الوحيدة التي ليس لديها سهم يشير إليها، مما يعني أنه لا يوجد أحد مفضل على Alice وجهًا لوجه. وهكذا تم إعلان فوز أليس في الانتخابات.

من الممكن، مع ذلك، أنه عند سحب الأسهم، لا يوجد فائز من كوندورسيه. النظر في الاقتراعات أدناه.

بين Alice وBob، يتم تفضيل Alice على Bob بفارق 7-2. بين بوب وتشارلي، يتم تفضيل بوب على تشارلي بفارق 5-4. لكن بين تشارلي وأليس، يُفضل تشارلي على أليس بفارق 6-3. إذا قمنا برسم الرسم البياني، فلا يوجد مصدر! لدينا دورة من المرشحين، حيث تتغلب أليس على بوب الذي يهزم تشارلي الذي يهزم أليس (تشبه إلى حد كبير لعبة حجر ورقة مقص). في هذه الحالة، يبدو أنه لا توجد طريقة لاختيار الفائز.

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

كيف سيتم تطبيق ذلك في حالة الأصوات أعلاه؟ حسنًا، أكبر هامش انتصار للزوج هو فوز أليس على بوب، حيث أن 7 ناخبين يفضلون أليس على بوب (لا يوجد أي مباراة أخرى وجهاً لوجه لها فائز يفضله أكثر من 7 ناخبين). لذلك تم قفل سهم Alice-Bob في الرسم البياني أولاً. أكبر هامش انتصار تالي هو فوز تشارلي على أليس بنتيجة 6-3، لذا فإن هذا السهم مغلق بعد ذلك.

الخطوة التالية هي فوز بوب على تشارلي بنتيجة 5-4. لكن لاحظ: إذا أضفنا سهمًا من بوب إلى تشارلي الآن، فسننشئ دورة! وبما أن الرسم البياني لا يسمح بالدورات، فيجب علينا تخطي هذه الحافة، وعدم إضافتها إلى الرسم البياني على الإطلاق. إذا كان هناك المزيد من الأسهم التي يجب وضعها في الاعتبار، فسننظر إلى الأسهم التالية، ولكن هذا كان السهم الأخير، وبالتالي فإن الرسم البياني مكتمل.

تظهر هذه العملية خطوة بخطوة أدناه، مع الرسم البياني النهائي على اليمين.

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

بشكل أكثر رسمية، تتكون طريقة التصويت في Tideman من ثلاثة أجزاء:

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

بمجرد اكتمال الرسم البياني، يكون مصدر الرسم البياني (الذي لا توجد به حواف تشير إليه) هو الفائز!

الفهم

دعونا نلقي نظرة على tideman.c.

أولاً، لاحظ المصفوفة ثنائية الأبعاد preferences. العدد الصحيح preferences[i][j] سيمثل عدد الناخبين الذين يفضلون المرشح i على المرشح j.

يعرّف الملف أيضًا مصفوفة أخرى ثنائية الأبعاد تسمى locked، والذي سيمثل الرسم البياني للمرشح. locked هي مصفوفة منطقية، لذا locked[i][j] يجري يمثل true وجود حافة تشير من المرشح i للمرشح j; false يعني عدم وجود حافة. (إذا كان الأمر مثيرًا للفضول، فإن هذا التمثيل للرسم البياني يُعرف باسم "مصفوفة الجوار").

التالي هو أ struct pair، يستخدم لتمثيل زوج من المرشحين: يتضمن كل زوج winnerفهرس المرشح و loserفهرس المرشح.

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

يحتوي البرنامج أيضًا على متغيرين عالميين: pair_count و candidate_count، يمثل عدد الأزواج وعدد المرشحين في المصفوفات pairs و candidatesعلى التوالي.

الآن main. لاحظ أنه بعد تحديد عدد المرشحين، يقوم البرنامج بالتكرار خلال الملف locked الرسم البياني ويقوم في البداية بتعيين كافة القيم على false، مما يعني أن الرسم البياني الأولي الخاص بنا لن يحتوي على حواف فيه.

بعد ذلك، يقوم البرنامج بالتكرار على جميع الناخبين ويجمع تفضيلاتهم في مصفوفة تسمى ranks (عبر مكالمة إلى vote)، حيث ranks[i] هو فهرس المرشح iالتفضيل الرابع للناخب. يتم تمرير هذه الرتب إلى وظيفة record_preference ، والتي تتمثل مهمتها في أخذ تلك الرتب وتحديث النطاق العالمي preferences متغير.

بمجرد دخول جميع الأصوات، تتم إضافة أزواج المرشحين إلى القائمة pairs مصفوفة عبر استدعاء add_pairs، تم فرزه عبر مكالمة إلى sort_pairs، ويتم قفله في الرسم البياني عبر مكالمة إلى lock_pairs. وأخيرا، تم استدعاء print_winner لطباعة اسم الفائز في الانتخابات!

في أسفل الملف، سترى الوظائف vote, record_preference, add_pairs,sort_pairs, lock_pairsو print_winner تُركت فارغة. هذا متروك لك!

المواصفات

أكمل تنفيذ tideman.c بطريقة تحاكي انتخابات Tideman.

• أكمل وظيفة vote .
  • تأخذ الدالة الوسائط rank, nameو ranks. إذا name مطابق لاسم مرشح صالح، لذا يجب عليك تحديث مصفوفة ranks للإشارة إلى أن الناخب لديه المرشح باعتباره مرشحه rank التفضيل (حيث 0 هو التفضيل الأول، 1 هو التفضيل الثاني، وما إلى ذلك.)
  • تذكر ذلك يمكن ranks[i] هنا يمثل المستخدم iالتفضيل الرابع.
  • يجب أن تعود الدالة true إذا تم تسجيل الرتبة بنجاح، و false بخلاف ذلك (إذا، على سبيل المثال، name ليس اسم أحد المرشحين).
  • قد تفترض أنه لن يكون هناك مرشحان يحملان نفس الاسم.
• أكمل وظيفة record_preferences .
  • يتم استدعاء الدالة مرة واحدة لكل ناخب، وتأخذ كوسيطة مصفوفة ranks ، (تذكر ذلك ranks[i] هو الناخب iالتفضيل الرابع، حيث ranks[0] هو التفضيل الأول).
  • يجب أن تقوم الوظيفة بتحديث النطاق العام مصفوفة preferences لإضافة تفضيلات الناخب الحالي. أذكر ذلك preferences[i][j] عدد الناخبين الذين يفضلون المرشح i على المرشح j.
  • قد تفترض أن كل ناخب سيقوم بتصنيف كل من المرشحين.
• أكمل وظيفة add_pairs .
  • يجب أن تضيف الوظيفة جميع أزواج المرشحين حيث يُفضل مرشح واحد على pairs مصفوفة. لا ينبغي إضافة زوج من المرشحين المرتبطين (لا يُفضل أحدهما على الآخر) إلى المصفوفة.
  • يجب أن تقوم الدالة بتحديث المتغير العام pair_count هو عدد أزواج المرشحين. (وبالتالي ينبغي تخزين جميع الأزواج بين pairs[0] و pairs[pair_count - 1]، ضمنًا).
• أكمل وظيفة sort_pairs .
  • يجب أن تقوم الوظيفة بفرز pairs مصفوفة بترتيب تنازلي لقوة النصر، حيث يتم تعريف قوة النصر على أنها عدد الناخبين الذين يفضلون المرشح المفضل. إذا كان لدى عدة أزواج نفس قوة النصر، فقد تفترض أن الترتيب لا يهم.
• أكمل وظيفة lock_pairs .
  • يجب أن تقوم الوظيفة بإنشاء ملف locked الرسم البياني، مع إضافة كافة الحواف بترتيب تنازلي لقوة النصر طالما أن الحافة لن تنشئ دورة.
• أكمل وظيفة print_winner .
  • يجب أن تقوم الوظيفة بطباعة اسم المرشح الذي هو مصدر الرسم البياني. قد تفترض أنه لن يكون هناك أكثر من مصدر واحد. وظائف

يجب ألا تقوم بتعديل أي شيء آخر في tideman.c بخلاف تطبيقات وظائف vote, record_preferences, add_pairs, sort_pairs, lock_pairsو print_winner (وإدراج ملفات رأس إضافية، إذا كنت ترغب في ذلك). يُسمح لك بإضافة وظائف إضافية إلى tideman.c، طالما لم تقم بتغيير إعلانات أي من الوظائف الموجودة.

الإرشادات التفصيلية

كيفية الاختبار

تأكد من اختبار الشيفرة الخاص بك للتأكد من أنه يتعامل مع...

• انتخابات بأي عدد من المرشحين (حتى MAX من 9)
• التصويت للمرشح بالاسم
• أصوات غير صالحة للمرشحين غير الموجودين في بطاقة الاقتراع
• طباعة الفائز في الانتخابات

صحة

check50 cs50/problems/2026/x/tideman

النمط

style50 tideman.c

كيفية الإرسال

في جهازك الطرفي، قم بتنفيذ ما يلي لإرسال عملك، والإجابة على المطالبات التي تظهر أيضًا.

submit50 cs50/problems/2026/x/tideman