Для визначення переможців Борда та Копленда скористаємося безпосередньо наведеними вище правилами, тобто реалізуємо їх програмно.

Складність алгоритмів, описаних нижче, прямо пропорційна кількості груп виборців та кількості кандидатів, що ще раз підтверджує приналежність даної задачі до Р-типу.

1. Визначення переможця Борда

Для знаходження оцінок Борда кандидати ранджуються, тобто за кожне місце у шкалі виборців кандидат отримує певну кількість балів. Далі ці бали сумуються.

Введемо наступні змінні.

Нехай М – кількість кандидатів;

S – кількість груп виборців;

Nаme[M] – масив імен виборців;

Rаng[1..M, 1..S] – профіль переваг;

Many[S] – кількість виборців у кожній групі;

Bord[M] – масив оцінок кандидатів.

Розглядаємо окремо кожну групу виборців. Для цієї групи кандидат отримує оцінку [кількість виборців many[i]]*([кількість кандидатів M] – [поточне значення лічильника j]). Знайдена оцінка додається до попередньої. Алгоритм продовжує роботу до тих пір, поки не будуть розглянуті усі групи виборців (i=S).

За правилом Борда отримуємо наступний алгоритм для знаходження оцінок Борда.

Рис. 4.1 Алгоритм знаходження оцінок Борда

1. знаходження оцінки Копленда

Для знаходження оцінки Копленда крім вище наведених використаємо наступні змінні:

Kopl[M] – масив оцінок Копленда;

Vybor1, vybor2 – допоміжні змінні; використовуються для перегляду імен кандидатів з масиву імен name.

Порівняння проходить наступним чином.

Змінній vybor1 присвоюємо значення імені першого кандидата з множини імен name (contrl=1), а vybor2 – наступне (k=contrl+1). Якщо vybor1 знаходиться вище, ніж vybor2, у перевагах виборців усіх груп, то до оцінки Копленда (kopl[contrl]) кандидата vybor1 додається очко, а vybor2 (kopl[k]) – віднімається і навпаки. Далі змінній vybor2 присвоюється наступне значення з масиву імен (k=k+1), і процедура порівняння знову повторюється. Цикл продовжується до тих пір, поки не вичерпаються імена у списку кандидатів.

Після цього змінній vybor1 присвоюється друге ім’я із списку кандидатів (contrl=contrl+1), а vybor2 – третя. Знову проходить цикл по змінній vybor2. Цикл по змінній vybor1 закінчується тоді, коли буде переглянуто усіх кандидатів.

Отримуємо наступний алгоритм знаходження оцінки Копленда.

Рис. 4.2 Алгоритм знаходження оцінок Копленда (початок)

Рис. 4.3 Алгоритм знаходження оцінок Копленда (закінчення)

1. Алгоритм визначення переможця за правилами Борда чи Копленда

Як можна було побачити, переможцем за Борда (Коплендом) є кандидат з найвищою сумою очок. Тому процес його визначення є однаковим для обох випадків , і я його об’єднала одним алгоритмом.

Як відомо, правила Копленда і Борда породжують множину розв’язків.

Для знаходження переможця використаємо наступні змінні:

K – кількість переможців;

Max – оцінка переможців;

Hl[M] – масив номерів переможців.

Спочатку масив номерів переможців заповнюємо нулями.

Масиви оцінок Копленда і Борда (kopl i bord) замінимо формальним масивом v[M].

Після того, як ми знайшли оцінки для кандидатів (масиви kopl i bord), серед них шукаємо максимальну (max). Далі відбираємо кандидатів, оцінка яких дорівнює max (їх номери з масиву name заносяться у масив hl), і рахуємо кількість переможців (k).

Переглядаємо заповнений масив hl. Якщо у ньому тільки перше значення є відмінне від нуля, то це означає, що ми знайшли єдиного переможця, і, отже, зберегли умову нейтральності.

В іншому випадку проглядаємо ті значення імен кандидатів (масив name), номери яких зустрічаються у масиві hl. Відібрані імена кандидатів впорядковуємо за списком. Переможцем стає той, ім’я якого знаходиться першим у даному списку.

У даному випадку умова нейтральності не зберігається.

Отже, ми отримали наступний алгоритм.

Рис. 4.4 Алгоритм визначення переможця (початок)

Рис. 4.5. Алгоритм визначення переможця (закінчення)

2. Опис програми

   1. Вибір технології програмування

Найбільш поширеними парадигмами програмування, які до того ж можуть бути використані у даній курсовій роботі, є парадигми процедурного та об’єктно-орієнтованого програмування.

Парадигма процедурного програмування найбільше широко поширена серед існуючих мов програмування (наприклад, Сі і Паскаль). Тут явно виділяють два види різноманітних сутностей:

1) процедури, що виконують активну роль, тобто являються тим, що задає поведінку (функціонування) програми;

2) дані, що виконують пасивну роль, тобто являють тим, що опрацьовується засобом, продиктованим процедурами. Спроможність складати процедури з команд (операторів) і викликати їх є ключем даної парадигми. Особливістю цієї парадигми є "бічні ефекти", що виникають у тих випадках, коли різноманітні процедури, що використовують загальні дані, незалежно їх змінюють.

У процедурній парадигмі активна роль в організації поведінки приділяється процедурам, а не даним; причому процедура активізується викликом. Подібні засоби завдання поведінки зручні для описів детермінованої послідовності дій або одного процесу, або декількох, але строго взаємозалежних процесів.

При використанні програмування, орієнтованого на дані, активну роль відіграють дані, а не процедури. Тут із структурами активних даних зв'язують деякі дії (процедури), що активізуються тоді, коли здійснюється доступ до цим даним. Деякі спеціалісти називають цей засіб активації дій "демонами". Програмування, орієнтоване на дані, дозволяє організувати поведінку мало залежних процесів, що важко реалізувати в процедурній парадигмі. Мала залежність процесів означає, що вони можуть розглядатися і програмуватися окремо. Проте при використанні парадигми, керованої даними, ці незалежно запрограмовані процеси можуть взаємодіяти між собою без їхньої зміни (тобто без перепрограмування).

Парадигма об'єктного програмування на відміну від процедурної парадигми не розділяє програму на процедури і дані. Тут програма організується навколо сутностей, названих об'єктами, що включають локальні процедури (методи) і локальні дані (змінні). Поведінка (функціонування) у цій парадигмі організується шляхом пересилки повідомлень між об'єктами. Об'єкт, отримавши повідомлення, здійснює його локальну інтепретацію, базуючись на локальних процедурах і даних. Такий підхід дозволяє описувати складні системи найбільш природним чином. Особливо він зручний для інтегрованих ІС.

Об'єктно-орієнтоване програмування (ООП) базується на абстракціях даних. В основі цього методу лежить представлення предметної області у вигляді сукупності об’єктів, які взаємодіють між собою через передачу повідомлень. Модель абстракції даних полягає в інкапсуляції даних та операцій над ними в окремий класовий тип. Доступ до даних можлива лише за допомогою інкапсульованих операцій. Класовий тип є автономно завершеним і дозволяє повне або часткове наслідування для інших класів. ООП концентрується на суті задачі, для якої розробляється програма. Задача будується як сукупність об'єктів, які взаємодіють між собою за допомогою повідомлень. Елементи програми розробляються у відповідності з об'єктами в описі задачі. Суть ООП полягає у визначенні найбільш вдалих об'єктових типів. Об'єктовий тип служить модулем, який може бути використаним для розв'язку інших подібних задач. Такий підхід не потребує спеціальної обчислювальної техніки, але суттєво відрізняється характером мислення виконавців у порівнянні з процедурними мовами програмування.

Через очевидну простоту алгоритму для реалізації задачі найкраще вибрати процедурну парадигму програмування і мови Паскаль чи Сі. Звичайно, для написання гарного інтерфейсу можна взяти об’єктно-орієнтовані мови C Builder чи Delphi. Проте, як можна було побачити з розгляду алгоритму задачі, побудова інтерфейсу зводилася б до послідовного виведення вікон. Ще одним аргументом на користь мов Паскаль чи Сі є розміри програми, які б при використанні C Builder чи Delphi були набагото більшими.

Серед двох мов – Паскаль і Сі, – я оберу Паскаль як більш звичну для себе.

1. Структура програми

Структурно дану програму можна поділити на блоки. Кожен блок може бути віднесений до однієї з функціональних груп:

1. Побудова інтерфейсу;

2. Реалізація алгоритмів, представлених у розділі 4.

О тже, програма має наступну структуру:

Рис. 5.1 Структура програми

Процедура victory – це реалізація алгоритму визначення переможця, описаного у попередньому розділі. Під час виклику даної процедури задається масив оцінок Борда чи Копленда, а також текст для виведення результатів (ним служать слова “Копленда” та “Борда”). У попередньому розділі вже було обгрунтовано, чому для визначення переможця за різними правилами використано єдиний алгоритм.

Процедура help виводить список імен кандидатів у нижньому рядку екрану. Вона введена для полегшення вводу інформації користувачем.

Процедура example містить дані контрольного прикладу. Вона введена для полегшення перевірки правильності роботи програми і носить демонстраційний характер.

Процедура right призначена для перевірки правильності вводу символу. Вона використовується при виборі внесення інформації (демонстрація контрольного прикладу чи самостійне внесення профілю) і виборі способу занесення даних (окремими виборцями чи працівниками виборчого комітету).

Перейдемо до розгляду основної програми.

Перш за все у ній проходить виклик і взаємозв’язок описаних вище процедур.

Процедури побудови інтерфейсу викликаються на початку роботи програми. Вони призначені для полегшення внесення даних.

Процедура victory визначає переможця і виводить результат голосування за певним правилом. Тому її виклик відбувається вкінці основної програми.

Опишемо змінні, які використовуються в основній програмі.

N: к-ть виборців;

M: к-ть кандидатів;

s: к-ть груп;

rang: профіль переваг;

a,b: для визначення оцінки Копленда (використовується у бінарних порівняннях);

kopl: масив оцінок Копленда;

vybor1, vybor2: змінні зовнішніх циклів при визначенні оцінки Копленда;

bord: масив оцінок Борда;

name: масив імен кандидатів;

k, i, j, l, r: допоміжні змінні;

many: масив груп виборців.

Опишемо структуру програми.

Спочатку програма просить внести усю потрібну інформацію. Користувач повинен вказати кількість виборців та кандидатів і спосіб занесення інформації (чи свої переваги буде вносити кожен виборець окремо, чи це буде проводити комісія, оперуючи згрупованими даними). Далі йде внесення профілю переваг і перевірка на його коректність. Профіль є некоректним, якщо у ньому зустрічається ім’я особи, яка не є вище вказаним кандидатом, або ж імена кандидатів повторюються.

У програмі використовуються алгоритми правил Борда та Копленда, вказані у попередньому розділі. Згідно отриманих оцінок визначається переможець за допомогою процедури victory, і проходить виведення результату.

Слід зауважити, що отримані переможці Копленда та Борда можуть не співпадати, що ще раз свідчить про недосконалість правил голосування більшістю голосів. Результати роботи алгоритму будуть показані у відповідному розділі.

Складність програми (у даному випадку розуміється час, затрачений на виконання), прямо пропорційно залежить від величини кількості виборців та кандидатів.

Так як дана програма носить більш демонстраційний характер, то я ввела межу для кількості виборців і кандидатів для того, щоб обмежити час виконання – 200 та 50 відповідно. В загальному воно не є суттєвим, так як завжди можна розбити виборчий округ на менший з умовою того, щоб виконувалось дане обмеження.

1. Інструкція користувачеві

Дана програма призначена для визначення переможця виборів за правилами Копленда і Борда і порівняння отриманих результатів.

На початку роботи програми користувач може вибрати, чи проглядати результати розв’язку контрольного прикладу, чи вносити власні дані. В обох випадках визначаються переможці за Коплендом і Борда.