); ^. X:=Pz.X; ^. Y:=Pz.Y; ^. rColor:=Pz.rColor; ^. Linked: =Pz.Linked; ^. Num:=Pz.Num; .Add (P) ;; i:=start to tmpList.Count - 2 do:=tmpList.Items [i]; not P ^ .Linked then:=MaxInt ; j:=0 to tmpList.Count - 1 doi lt; gt; j then:=tmpList.Items [j]; (not P2 ^ .Linked) and (P2 ^ .rColor lt; gt; P ^ .rColor) thensqrt ( sqr (P ^ .X - P2 ^ .X) + sqr (P ^ .Y - P2 ^ .Y)) lt; Min then:=sqrt (sqr (P ^ .X - P2 ^ .X) + sqr (P ^ .Y - P2 ^ .Y));:=P2 ;;;;:=Sum + Min; ^. Linked: =True; ^. Linked:=True; ^. Num:=P ^ .Num ;;; i:=0 to start - 1 do:=tmpList.Items [i]; not P ^ .Linked then:=MaxInt; j:=0 to tmpList.Count - 1 doi lt; gt; j then:=tmpList.Items [j]; (not P2 ^ .Linked) and (P2 ^ .rColor lt; gt; P ^ .rColor) thensqrt (sqr (P ^ .X - P2 ^ .X) + sqr (P ^ .Y - P2 ^ .Y)) lt; Min then:=sqrt (sqr (P ^ .X - P2 ^ .X) + sqr (P ^ .Y - P2 ^ .Y));:=P2 ;;;;:=Sum + Min; ^. Linked: =True; ^. Linked:=True; ^. Num:=P ^ .Num ;;; start=0 then:=sum; .Clear; i:=0 to tmpList.Count - 1 do:=tmpList.Items [ i]; (P); ^. X:=Pz.X; ^. Y:=Pz.Y; ^. rColor:=Pz.rColor; ^. Linked:=Pz.Linked; ^. Num:=Pz. Num; .Add (P) ;; if sum lt; minsum then:=sum; .Clear; i:=0 to tmpList.Count - 1 do:=tmpList.Items [i]; (P); ^. X:= Pz.X; ^. Y:=Pz.Y; ^. rColor:=Pz.rColor; ^. Linked:=Pz.Linked; ^. Num:=Pz.Num; .Add (P) ;;;;. Clear; i:=0 to oList.Count - 1 do:=oList.Items [i]; (P); ^. X:=Pz.X; ^. Y:=Pz.Y; ^. rColor:=Pz.rColor; ^. Linked:=Pz.Linked; ^. Num:=Pz.Num; .Add (P) ;;. Label3.Caption:= Мінімальна сума відрізків: + FloatToStr (minSum);
end;
Даний алгоритм містить кілька циклів: один глобальний цикл і два вкладених, які в свою чергу включають в себе ще по одному вкладеному циклу. Параметром для зовнішнього глобального циклу є змінна start, яка ділить даний список як би на два сегменти. Потім внутрішні цикли послідовно перебирають змінні в першому і другому сегментах. Дані змінні беруться в припущенні, що вони є початком відрізка, а кінці відрізків перебираються ще одним циклом по всьому списку. У результаті складається картина того, що почала відрізків беруться в різних сегментах, розміри яких змінюються в процесі прогону глобального циклу, а кінці - з усього списку. Даний спосіб перебору елементів дозволяє перебрати всі відрізки, вибрати з них мінімальні і знайти їх мінімальні суми. Підсумовування в попередню мінімальну суму для кожного набору відрізків відбувається, якщо відстань від даної точки (початку відрізка) до перебирається точки (кінця відрізка) менше, ніж відстані від даної точки до всіх інших. У результаті ми отримуємо суми довжин наборів відрізків, з яких запам'ятовуємо в свою чергу мінімальну суму.
Нижче наведена загальна блок-схема алгоритму:
4. Резюме
. 1 Висновки
В результаті виконання курсового проекту була створена програма рішення задачі про червоних і синіх точках, яка цілком нормально працює, і сильних відхилень немає.
До достоїнств програми можна віднести:
- простий інтерфейс без зайвих складнощів;
процес роботи програми візуалізується;
До недоліків можна віднести наступне:
- неможливість більш детального аналізу алгоритму;
. 2 Можливі модернізації
програма задача алгоритм
1. Доопрацювати програму і дати можливість користувачу більш детального аналізу алгоритму.
5. Література
1. Т. Кормен, Ч. Лейзерсон, Р. Ривест «Алгоритми: побудова і аналі?? ».
. В.В. Фаронов «Delphi - програмування на мові високого рівня».
. Ю.С. Ізбачков, В.Н. Петров «Інформаційні системи», друге видання
6. Додаток
. 1 Текст програми
Unit1;
interface, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms ,, ComCtrls, Menus, ToolWin, ExtCtrls, StdCtrls, ImgList, Grids ,, ShellAPI;=class (TForm): TMainMenu;:TMenuItem ;: TMenuItem ;: TPanel ;: TToolBar ;: TToolButton ;: TToolButton ;: TImage ;: TButton ;: TButton ;: TImageList ;: TToolButton ;: TMenuItem ;: TMenuItem ;: TScrollBox ;: TImage ;: TGroupBox ;: TLabel ;: TLabel ;: TLabel ;: TButton ;: TStringGrid ;: TPanel; ToolButton1Click (Sender: TObject); ToolButton3Click (Sender: TObject); FormCreate (Sender: TObject); Image1MouseUp (Sender: TObject; Button: TMouseButton ;: TShiftState; X, Y: Integer); ToolButton2Click (Sender: TObject); Button1Click (Sender: TObject); Button2Click (Sender: TObject); Button3Click (Sender: TObject); N4Click (Sender: TObject); N3Click (Sender: TObject);
{Private declarations}
{Public declarations};=^ TPnt;=record, Y: integer ;: byte ;: integer ;: boolean ;;: TForm1 ;...