Слід зауважити, що отримані переможці Копленда та Борда можуть не співпадати, що ще раз свідчить про недосконалість правил голосування більшістю голосів. Результати роботи алгоритму будуть показані у відповідному розділі.
Складність програми (у даному випадку розуміється час, затрачений на виконання), прямо пропорційно залежить від величини кількості виборців та кандидатів.
Так як дана програма носить більш демонстраційний характер, то я ввела межу для кількості виборців і кандидатів для того, щоб обмежити час виконання – 200 та 50 відповідно. В загальному воно не є суттєвим, так як завжди можна розбити виборчий округ на менший з умовою того, щоб виконувалось дане обмеження.
Дана програма призначена для визначення переможця виборів за правилами Копленда і Борда і порівняння отриманих результатів.
На початку роботи програми користувач може вибрати, чи проглядати результати розв’язку контрольного прикладу, чи вносити власні дані. В обох випадках визначаються переможці за Коплендом і Борда.
Спочатку працівники виборчого органу вносять загальну інформацію: кількість виборців у даному окрузі та кількість кандидатів. Далі заносяться імена кандидатів і вказується спосіб занесення профілів переваг: кожним виборцем окремо чи працівниками виборчого округу. В останньому випадку інформація є згрупована (аналогічно до контрольного прикладу).
Внизу екрана виводяться імена усіх кандидатів. Кожен виборець (чи працівник виборчого округу) вносить профіль переваг, розташовуючи кандидатів у строго визначеному порядку.
Для кожного виборця не допускається випадків байдужості; крім того, кандидати повинні бути строго ранджовані (тобто кожен з них займає своє місце у перевазі виборця, і на одному рівні не можуть знаходитись два кандидати). Імена кандидатів, які заносяться виборцями, повинні співпадати з іменами, вказаними на початку заповнення інформації.
Після занесення усіх цих даних видається результат роботи програми.
Спочатку виводиться переможець Копленда і вказується, чи він визначений із збереженням нейтральності. Для переможця вказується його оцінка. У противному випадку виводиться множина переможців (кандидатів, сума очок яких дорівнює максимальній оцінці).
Аналогічно визначається переможець Борда.
Як буде показано у контрольному прикладі, оцінки кандидатів, отриманих за правилами Борда і Копленда, можуть ранджуватись у протилежному порядку.
Нехай дано наступний профіль для 9 виборців і 5-ти кандидатів:
| 1 | 4 | 1 | 3 |
| abcde | cdbea | eadbc | eabdc |
У кожному стовпці кандидати розташовані у порядку зменшення їх значущості для кожної групи виборців. Тобто, для першого стовпця можна визначити переваги наступним чином: група виборців, що складається з однієї особи, вважає кандидата a найкращим. На другому місці вони ставлять кандидата b, на третьому місці c і т.д.
Продемонструємо розв’язок контрольного прикладу за правилом Копленда. Визначаємо оцінку Копленда.
Кандидат a є кращим за b для 1+1+3 виборців, а для 4-х виборців кандидат b є кращим за a. Визначимо такі переваги для кожного кандидата, порівняємо його з усіма іншими.
| ab – 5ac – 5ad – 5ae – 1 | ba – 4ca – 4da – 4ea – 8 | bc – 5bd – 4de – 5 | cb – 4db – 5eb – 4 | cd – 5ce – 5 | dc – 4ec – 4 | de – 5 | ed – 4 |
Визначимо оцінку Копленда для кожного кандидата. Кандидат a є кращим за b (додаємо +1); він також є кращим за c та d (додаємо два рази +1) і гіршим за e (додаємо –1). Отже, оцінка Копленда для a рівна 2.
Знайдемо оцінку для інших кандидатів.
a=+1+1+1-1=2
b=-1+1-1+1=0
c=-1-1+1+=0
d=-1+1-1+1=0
e=+1-1-1-1=-2
Серед отриманих оцінок визначаємо максимальну. Як бачимо, вона дорівнює 2 і належить кандидату a. Отже, a – переможець Копленда.
Якби у нас отрималось два кандидати з максимальною оцінкою, наприклад b та f, ми б обрали кандидата b, так як він розташований ближче за алфавітом.
Для цього ж профілю знайдемо переможця Борда.
Отже, отримуємо такі оцінки:
a=1*4+4*0+1*3+3*3=16
b=3*1+2*4+1*1+2*3=18
c=2*1+4*4+0+0=18
d=1*1+4*3+2*1+1*3=18
e=1*4+1*4+3*4+0=20
Переможцем за Борда є кандидат е.
Як бачимо, оцінки Борда ранджують кандидатів у порядку, протилежному до того, який отримується за оцінками Копленда.
Дана курсова робота була присвячена огляду методів голосування більшістю голосів. Було проведено порівняльну характеристику кожного з методів і з їх множини обрано найкращі. До них відносяться
1. заможні за Кондорсе правила Копленла і Сімпсона, дерево багатоетапного виключення;
2. один з методів підрахунку очок – правило Борда.
Всі ці правила задовольняють умовам оптимальності за Парето, монотонності та анонімності. Крім того, правило Борда задовольняє також аксіомі участі та поповнення.
Для програмної реалізації було обрано методи Копленда і Борда.
Результати роботи програми продемонстровано на контрольному прикладі.
1. Мулен Э. “Кооперативное принятие решений: Аксиомы и модели” – Москва, Мир, 1991.
2. Миркин Б. Проблема групового выбора. – Москва, Наука, 1974.
label y, z;
type mas = string[6];
type ball =array[1..10] of shortint;
var N: byte; {к-ть виборцiв}
M: byte; {к-ть кандидатiв}
s: byte; {к-ть груп}
rang: array[1..10,1..100] of mas; {профiль переваг}
k,i,j,l,r,contrl: byte;
a,b: byte; {для проведення парних порiвнянь}
kopl: ball; {масив оцiнок Копленда}
vybor1, vybor2: mas;
bord: ball; {масив оцiнок Борда}
name: array[1..10] of mas; {масив iмен кандидатiв}
many: array[1..100] of byte; {масив груп виборцiв}
n1: array[1..10] of mas;
c: char;
{дані контрольного прикладу}
{---------------------------}
procedure example;
var i, j: byte;
begin
clrscr; M:=5; n:=9; s:=4;
name[1]:='a'; name[2]:='b'; name[3]:='c'; name[4]:='d'; name[5]:='e';
many[1]:=1; many[2]:=4; many[3]:=1; many[4]:=3;
rang[1,1]:='a'; rang[1,2]:='c'; rang[1,3]:='e'; rang[1,4]:='e';
rang[2,1]:='b'; rang[2,2]:='d'; rang[2,3]:='a'; rang[2,4]:='a';
rang[3,1]:='c'; rang[3,2]:='b'; rang[3,3]:='d'; rang[3,4]:='b';
rang[4,1]:='d'; rang[4,2]:='e'; rang[4,3]:='b'; rang[4,4]:='d';
rang[5,1]:='e'; rang[5,2]:='a'; rang[5,3]:='c'; rang[5,4]:='c';
gotoXY(15,1);
writeln('Завдання контрольного прикладу');
writeln; writeln('Число виборців: ', N);
writeln('Число кандидатів: ', M);
writeln('Профіль переваг:');
for i:=1 to 40 do
write('-');
writeln; write('Число виборців ');
gotoXY(19,7);
for i:=1 to s do
write(many[i], ' ');
writeln; gotoXY(19,9);
for i:=1 to M do
begin
for j:=1 to s do
write(rang[i,j], ' ');
gotoXY(19, 9+i);
end;
gotoXY(1,15);
end;
{---------------------------}
{перевіряє правильність вводу варіанту вибору}
procedure right;
label l;
begin
l: readln(c);
if (c<>'0') and (c<>'1') then
begin
write('Повторіть спробу: ');
goto l;
end;
end;
{---------------------------}
{виводить список імен кандидатів}
procedure help;
var x,y,i: byte;
begin
x:=WhereX;
y:=WhereY;
gotoXY(1,24);
write('Імена кандидатів: ');
for i:=1 to M do
if i<>M then write(name[i], ', ')
else write(name[i]);
gotoXY(x,y);
end;
{---------------------------}
{визначення переможця виборів}
procedure victory(v: ball; s: string);
var max, t: shortint;
hl: array[1..10] of byte;
begin
{визначення максимальної оцiнки}
help;
max:=v[1];
for i:=1 to M do
if max<v[i] then
max:=v[i];
t:=1;
{визначення кандидатiв з максимальною оцiнкою}
for i:=1 to M do
if (v[i]-max)=0 then
begin
hl[t]:=i;
t:=t+1;
end;
if (t-1)=1 then
begin
write('Переможець за ', s, ' iз збереженням нейтральностi: ');
writeln(name[hl[1]]); writeln('Сума очок - ', max);
end
else
begin
vybor1:=name[hl[1]];
for i:=2 to t-1 do
if name[hl[i]]<vybor1 then
vybor1:=name[hl[i]];
write('Переможець за ', s, ' без збереження нейтральностi: ');
writeln(vybor1); writeln('Сума очок - ', max);
writeln('обраний з множини найкращих:');
for i:=1 to t-1 do
writeln(name[hl[i]]);
end;
end;
{---------------------------}
{основна програма}
begin
gotoXY(21,1); writeln('Визначення переможця виборів');
writeln; writeln('Запуск контрольного прикладу - 1; Самостійне внесення профілю - 0');
right;
if c='1' then
begin
example;
help;
goto z;
end
else clrscr;
write('Введiть кiлькiсть кандидатiв: ');
readln(M);
write('Введiть кiлькiсть виборцiв: ');
readln(N);
writeln('Введiть iмена кандидатiв');
for i:=1 to M do
begin
write('Кандидат ', i, ': ');
readln(name[i]);
end;
writeln('Як буде здiйснюватись занесення iнформацiї?');
write('1- окремими виборцями, 0- комiтетом: ');
right;
if c='1' then
for i:=1 to N do
many[i]:=1;
clrscr; writeln('Введiть профiль переваг');
s:=1; contrl:=0;
while contrl<>N do
begin
if c='1' then writeln('Виборець ', s)
else writeln('Група ', s);
for i:=1 to m do
n1[i]:='';
help;
for j:=1 to M do
begin
y:readln(vybor1);
{перевірка на коректність введеного профілю}
r:=0; a:=0; b:=0;
n1[j]:=vybor1;
for l:=1 to M do
begin
if vybor1=name[l] then
begin
b:=1;
for a:=1 to M do
{таке ім'я вже було введено у даному профілі}
if (vybor1=n1[a]) and ((a-j)<>0) then r:=1;
end;
{ім'я введеного кандидата не співпадає із жодним із списку}
if (vybor1<>name[l]) and (l=M) and (b<>1)then r:=1;
end;
if r=1 then
begin
n1[j]:='';
writeln('Уважно вводьте імена кандидатів');
goto y;
end
else rang[j,s]:=vybor1; {профіль коректний}
end;
if c='0' then
begin
writeln('Кiлькiсть виборцiв у групi ', s);
readln(many[s]);
contrl:=contrl+many[s];
end
else
contrl:=contrl+1;
s:=s+1;
clrscr;
end; {while}
{Визначення оцiнок Копленда}
z: contrl:=1;
while contrl<=M do
begin
k:=contrl+1;
vybor1:=name[contrl]; vybor2:=name[k];
while k<=M do
begin
i:=1; a:=0; b:=0;
while i<=s do
begin
for j:=1 to M do
if rang[j,i]=vybor1 then l:=j
else
if rang[j,i]=vybor2 then r:=j;
if l<r then a:=a+many[i]