Читайте также:
|
| computer.dat | computer.sol |
Розв’язок
Необхідно знайти спільні дільники чисел M та N, які не менші за число K.
Для i:=K до мінімум(N,M)
пц
якщо ост(i,N)=0 та ост(i,M)=0 то вивести (i)
кц
Програма:
| program computer; var n,a,b,c,min:integer; f1,f2:text; begin assign(f1,'COMPUTER.dat'); reset(f1); read(f1,a,b,c); close(f1); assign(f2,'COMPUTER.sol'); rewrite(f2); if a>b then min:=b else min:=a; for n:=c to min do begin if (a mod n=0)and(b mod n=0) then write(f2,n,' '); end; writeln(f2); close(f2); end. |
Задача 3. Збирання мита (TALLAGE) - 60 балів.
Король країни Аріїв завоював N міст на території сусідніх держав.
Тепер йому необхідно створити систему збирання мита з завойованих територій. Він хоче збудувати таку систему шляхів між цими містами, щоб до будь-якого міста можна було дістатися (можливо, через інші міста) зі столиці, але у воєнному стані на транспорт виділяється дуже незначна частина фінансів, тому сумарна вартість побудованих шляхів сполучення між містами має бути мінімальною.
Вхідні дані:
Перший рядок вхідного файлу містить натуральне число N (1<=N<=100) – кількість міст у країні, а також цілі числа X та Y – координати столиці.
Наступні N рядків містять через проміжок координати Xi, Yi завойованих міст.
Значення координат по модулю менші 50000.
Вихідні дані:
Перший рядок має містити дійсне число з трьома знаками після коми – сумарну вартість побудованих доріг. Вважайте, що вартість одиниці довжини дороги дорівнює одній умовній одиниці.
Наступні рядки мають містити у довільному порядку список побудованих доріг у форматі:
<номер міста> => <номер міста>
При цьому столицю позначте номером 0.
Якщо відповідей декілька, виведіть одну довільну з них.
Приклади:
| TALLAGE.DAT | TALLAGE.SOL |
| 6 0 0 1 1 -1 1 0 2 1 -1 -1 -1 0 -2 | 8.485 2 3 3 1 1 0 0 4 4 6 6 5 |
Розв’язок
Теорія графів-Жадібні алгоритми – каркас мінімальної ваги (остове дерево)
Визначити довжини шляхів за формулою довжини відрізка 
.
На основі довжин побудувати навантажений, неорієнтований граф.
На основі алгоритма Прима або Крускала побудувати каркас мінімальної ваги, який і буде розв’язком задачі.
Програма:
| program tallage; {$apptype console} var a:array[0..100,0..100] of extended; x,y:array[0..100] of integer; f1:text; kol_ver,v:array[0..100] of integer; n,k,i,j,vi,vj:integer; min,s:real; ver:array[0..100,1..2] of integer; f:boolean; cc:char; begin assign(f1,'tallage.dat'); reset(f1); read(f1,n); for i:=0 to n do begin read(f1,x[i],y[i]); end; close(f1); for i:=0 to n do for j:=i to n do begin a[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])); a[j,i]:=a[i,j]; end; | k:=0; v[k]:=0; s:=0; while (k<n) do begin min:=maxint; for i:=0 to k do for j:=0 to n do if a[v[i],j]<min then begin min:=a[v[i],j];vi:=v[i];vj:=j;end; f:=true; for i:=0 to k do if vj=v[i] then f:=false; if f then begin k:=k+1; ver[k,1]:=vi; ver[k,2]:=vj; v[k]:=vj; kol_ver[vj]:=kol_ver[vj]+1; kol_ver[vi]:=kol_ver[vi]+1; s:=s+a[vi,vj]; end; a[vi,vj]:=1e30;a[vj,vi]:=1e30; end; assign(f1,'tallage.sol'); rewrite(f1); writeln(f1,s:3:3); for i:=1 to n do writeln(f1,ver[i,1],' ',ver[i,2]); close(f1); end. |
Дата добавления: 2014-12-19; просмотров: 129 | Поможем написать вашу работу | Нарушение авторских прав |