для порівняння визначимо переможця за Борда.
Наведемо ще раз правила Копленда і Борда для того, щоб перейти до формулювання алгоритму програми.
Правило Борда. Кожен виборець повідомляє свої переваги, ранжуючи р кандидатів від кращого до гіршого (безрізниця забороняється). Кандидат не одержує очок за останнє місце, одержує одне очко за передостаннє і так далі, отримує р-1 очок за перше місце. Перемагає кандидат із найбільшою сумою очок. Він називається переможцем за Борда. p> Правило Копленда. Порівняємо кандидата а з будь-яким іншим кандидатом х. Нарахуємо йому +1, якщо для більшості а краще за х, -1, якщо для більшості х краще за а, і 0 при рівності. Підсумовуючи загальну кількість очок по всім х , х В№ а отримуємо оцінку Копленда для а. Обирається кандидат, названий переможцем за Коплендом, з найвищою з таких оцінок.
Вважаємо, що вхідними даними задачі є вже згрупована інформація: сформовані групи виборців з однаковими у кожній групі рангами переваг. Однак допускається і занесення інформації кожним виборцем окремо.
В
4. Опис алгоритму
У даному розділі наводяться алгоритми для знаходження переможців виборів. Для визначення переможців Борда та Копленда скористаємося безпосередньо наведеними вище правилами, тобто реалізуємо їх програмно. Складність алгоритмів, описаних нижче, прямо пропорційна кількості груп виборців та кількості кандидатів, що ще раз підтверджує приналежність даної задачі до Р-типу.
4.1 Визначення переможця Борда
Для знаходження оцінок Борда кандидати ранжуються, тобто за кожне місце у шкалі виборців кандидат отримує певну кількість балів.
Далі ці бали сумуються.
Введемо наступні змінні.
Нехай М - кількість кандидатів;
S - Кількість груп виборців;
Nаme [M] - Масив імен виборців;
Rаng [1 .. M, 1 .. S] - профіль переваг;
Many [S] - Кількість виборців у кожній групі;
Bord [M] - Масив оцінок кандидатів. p> Розглядаємо окремо кожну групу виборців. Для цієї групи кандидат отримує оцінку [Кількість виборців many [i]] * ([кількість кандидатів M] - [поточне значення лічильника j]). Знайдена оцінка додається до попередньої. Алгоритм продовжує роботу до тих пір, поки не будуть розглянуті усі групи виборців (i = S).
За правилом Борда отримуємо наступний алгоритм для знаходження оцінок Борда.
В
Рис. 4.1 Алгоритм знаходження оцінок Борда. br/>В
Рис. 4.2 Алгоритм знаходження оцінок Копленда (початок)
В В
4.2 Знаходження оцінки Копленда
Для знаходження оцінки Копленда крім вище наведених використовуємо наступні змінні: Kopl [M] - масив оцінок Копленда; Vybor1, vybor2 - допоміжні змінні; використовуються для перегляду імен кандидатів з масиву імен name.
Порівняння проходить наступним чин...
