////////////////////////////////////////////////////////////////////////////////////////////////////
Программа «А- дерево»
1. Цель программы
2. Исходные данные.
3. Основной цикл
4. Суперцикл
5. Вывод
6. Результаты
1. Цель программы
Программа «А- дерево» формирует случайное дерево.
Название условное, так как определения случайного дерева нет.
Ранее выставлена программа 06-дерево. Построение случайного дерева
Программа А- дерево быстрей выполняется и допускает большое число вершин.
Задействованы кнопки:
ПУСК, СВЯЗИ и ЗАКРЫТЬ.
Две кнопки зарезервированы для развития программы.
Программа в Дельфи 7.
Распечатка программы – Приложение 1
Если в Вашем компе нет Дельфи 7, можно ознакомиться с результатом выполнения программы, запустив файл project1 exe.
2. Исходные данные.
Исходные данные вводятся непосредственно в программу.
n – число вершин дерева
x- е число шагов (циклов) суперцикла
В массиве uu исходные фрагменты имеют величину 1.
3. Основной цикл
Исходные фрагменты: вершины искомого дерева: n - вершин.
Фрагменты случайным образом объединяются.
Всего n-1 итераций.
Действия на итерации.
Из фрагментов с положительной величиной в массиве случайно выбирается фрагмент – m1.
Из оставшихся фрагментов случайно выбирается фрагмент – m2
Фрагменты m1 и m2 объединяются
Новому фрагменту в массиве uu присваивается номер основного цикла.
В массиве uu величины m1 и m2 делаются отрицательными.
Два фрагмента m1 и m2 cсоединяются ребром (двумя противоположно направленными дугами)..
В фрагменте m1 случайно выбирается вершина ii.
Во фрагменте m2 случайно выбирается вершина jj.
В массиве p вводятся две дуги: p[ii,jj] и p[jj,ii].
.
4. Суперцикл
Для набора статистики введен суперцикл.
На каждом шаге суперцикла выполняется основной цикл.
Результаты суммируются и усредняются.
5. Вывод
Выводятся следующие результаты в форме массивов
Переменных.
Смотреть в распечатке программы – Приложение 1.
6. Результат
А) Величины массива s3 почти не меняются с изменением n
Б) Увеличение n не приводит к появлению вершин инцидентных большому числу рёбер.
Пример
X=100
Число ребер инцидентных вершине – величина s3 при n =100 - величина s3 при n =2000
1- 338,7 -334,32
2- 410,5 -407,05
3- 193,0 – 196,12
4- 48,9 – 52,61
5- 7,8 – 8,7
6- 1 - 1,1
7- 0,1-0,09
Скачать программу
https://disk.yandex.ru/d/Ilgtilw-d9Fvvw
Приложение 1
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Button1: TButton;
Button2: TButton;
Button3: TButton;
Button5: TButton;
Label1: TLabel;
StringGrid3: TStringGrid;
StringGrid4: TStringGrid;
Button4: TButton;
Edit1: TEdit;
Edit2: TEdit;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Label5: TLabel;
Label8: TLabel;
Label10: TLabel;
Edit3: TEdit;
Label11: TLabel;
StringGrid2: TStringGrid;
Label6: TLabel;
Label7: TLabel;
Label9: TLabel;
procedure Button1Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
const
n =100;//число вершин дерева
x=100;// число суперциклов
var
Tick: Cardinal;
u:array [ 1..n, 1 ..n] of integer;//матрица фрагментов дерева при выполнении
//основного цикла на пследнем цикла суперцикла
p : array [1..2*n,1..n] of integer;//матрица инциденций дуг
// на последнем цикле суперцикла
uu :array [1..2*n] of integer;//мартица номеров фрагментов
// по номерам циклов основного цикла на последнем цикле суперцикла
ua :array [1..4*n] of integer;//мартица номеров фрагментов
// по порядковому номеру объединения на последнем цикле суперцикла
r :array [1..n] of integer;// integer;//матрица инциденций числа дуг
//исходящих из вершин дерева после последнего цикла суперцикла
s1: array [1..n] of integer;// матрица суммы исходящих дуг
// с разбивкой по числу дуг инцидентных вершинам: 1,2, 3 ...n-1. //
s2: array [1..n] of variant;//
// // Число дуг в массиве S1 делтся на число циклов в суперцикле
s3: array [1..n] of variant;//
// Число дуг в массиве S1 делтся на произведение
//числаа циклов в суперцикле и числа вершин дерева
a, b, k, g, h, q,i,j: integer; //
j1,j2,j3,j4,j5,j6,j7,j8,i2,i1,e, i3,i4,i5,i6,i7,i8,i9,i0: integer; //
m, aa, bb, z, f, c, w,v : integer;//
m1 ,m2,vv: integer;//
kk, ii , jj,t1,tt, k1: integer;//
ia, ib, ic ,id,iw,ie, ja, jb,jc,jd,jw,je : integer;//
procedure TForm1.Button1Click(Sender: TObject);
// окантовка
begin
for q:=1 to n //нумерация по горизонтали в табл №1 ,
do StringGrid1.Cells[q,0]:=IntToStr(q);
for q:=1 to n // нумерация по вертикали в табл №1 ,
do StringGrid1.Cells[0,q]:=IntToStr(q);
for q:=1 to 42 //нумерация по горизонтали в табл №2,
do StringGrid2.Cells[q,0]:=IntToStr(q);
for q:=1 to 50 // нумерация по вертикали в табл №2 ,
do StringGrid2.Cells[0,q]:=IntToStr(q);
for q:=1 to 3*n //нумерация по горизонтали в табл №3,
do StringGrid3.Cells[q,0]:=IntToStr(q);
for q:=1 to 25 // нумерация по вертикали в табл №3 ,
do StringGrid3.Cells[0,q]:=IntToStr(q);
for q:=1 to n //нумерация по горизонтали в табл №4,
do StringGrid4.Cells[q,0]:=IntToStr(q);
for q:=1 to 2*n // нумерация по вертикали в табл №4 ,
do StringGrid4.Cells[0,q]:=IntToStr(q);
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
//суперцикл
for m:=1 to x do
begin
f:=0;
for id:=1 to 2*n do
for jd:=1 to n do
p[id,jd] :=0;
for iw := 1 to n do
for jw :=1 to n do
u[iw,jw] :=0;
for ie :=1 to 2*n do
uu[ie] :=0;
for ie := 1 to n do
r[ie] := 0;
// исходные фрагменты
begin
for i:=1 to n do
for j:=1 to n do
if i=j then p[i,j] :=1;
for i:= 1 to n do uu[i] := 1;
for w:= 1 to (n-1) do // основной цикл
begin
Form1.Caption:=IntToStr(GetTickCount-Tick);
for i5 := 1 to 2 do // пара фрагментов
begin // двойка
if i5 = 2 then //
C:=c+1;
//выбор фрагмента
V:=0; a:=0;
for i1 := 1 to (2*n) do
if uu[i1] >0 then
begin v:= v+1;
a:= random(v)+1;
end;
Z :=0; i2:=0; k:=0;
repeat begin i2:= i2+1; k:=i2;
if uu[i2] >0 then
z:= z+1 ; end;
until (z=a) ;
if i5 = 1 then m1 := k;
if i5 = 2 then m2 :=k;
if m=x then
begin
f:= f+1;
ua[f] :=k;
end;
//объединение фрагментов
vv := 0;
for i3 := 1 to n do
if p[k,i3]>0 then begin
vv:= vv+1;
p[w+n,i3]:=vv;
end;
//////////////////////////////////
//ввод ребра между соединяемыми рагметами
//////////////////////////////// ii
begin
if i5 =1 then
begin
I7:=0; kk:= 0; ; tt := 0; ii :=0;
for i6:=1 to n do
if p[m1,i6]>0 then kk := kk +1;
aa := random (kk) +1;
repeat
begin i7 := i7+1;
if p[m1,i7] >0 then tt:= tt+1; end;
until tt =aa;
end;
ii :=i7;
///////////////////////////////////
if i5 =2 then
begin
i0 := 0; k1:=0; t1:=0; jj:=0;
for i9:=1 to n do
if p[m2,i9]>0 then k1 := k1 +1;
bb := random (k1) +1;
repeat
begin i0 := i0+1;
if p[m2,i0] >0 then t1:= t1+1; end;
until t1 =bb;
jj :=i0;
u[ii,jj] := w;
u[jj,ii] := u[ii,jj];
end;
end;
/////////////////////////////////
if i5=2 then
uu[w+n] := w;
uu[k] := -w;
end ;
end;
h:=0;
for ia := 1 to n do
for ja := 1 to n do
if u[ia,ja] >0 then
r[ia] := r[ia]+1;
for i:=1 to n do
h := h+ r[i] ;
for ib := 1 to n do
for jb := 1 to n do
if r[ib] = jb then s1[jb] := s1[jb] +1;
end;
end; //суперцикл
/////////////////////////
for i:=1 to n do
s2[i] := s1[i]/x;
e:= h div 2;
for ic:=1 to n do
s3[ic] :=s1[ic]/(x*n);
for i:=1 to n do
StringGrid2.Cells[i,3]:=
IntToStr( r[i]);
for i:=1 to 2*n do
StringGrid2.Cells[i,1]:=
IntToStr( ua[i]);
for i:=1 to n do
StringGrid2.Cells[i,5]:=IntToStr(s1[i]);
for i:=1 to n do
StringGrid2.Cells[i,6]:= FormatFloat('0.0000',s2[i]);
for i:=1 to n do
StringGrid2.Cells[i,7]:= FormatFloat('0.0000',1000*s3[i]);
for i:=1 to n do
for j:= 1 to n do
StringGrid1.Cells[j,i]:=
IntToStr( u[i,j]);
for i:=1 to 2*n do
for j:= 1 to n do
StringGrid4.Cells[j,i]:=
IntToStr( p[i,j]);
for i:=1 to 2*n do
StringGrid3.Cells[i,1]:=
IntToStr( uu[i]);
Edit1.Text :=
'e='+'---'+IntToStr(e)+' ' +
'h='+'---'+IntToStr(h)+' ' +
't1='+'---'+IntToStr(t1) +' ' +
'k='+'---'+IntToStr(k) +' ' +
'w='+'---'+IntToStr(w)+' ' +
'c='+'---'+IntToStr(c)+' ' +
'z='+'---'+IntToStr(z)+' ' +
'v='+'---'+IntToStr(v)+' ' +
'a='+'---'+IntToStr(a);
Edit2.Text :=
'm1='+'---'+IntToStr(m1) +' ' +
'm2='+'---'+IntToStr(m2) +' ' +
'i1='+'---'+IntToStr(i2) +' ' +
'i2='+'---'+IntToStr(i3) +' ' +
'i4='+'---'+IntToStr(i4) +' ' +
'i5='+'---'+IntToStr(i5) +' ' +
'i6='+'---'+IntToStr(i6) +' ' +
'i7='+'---'+IntToStr(i7) +' ' +
'i8'+'---'+IntToStr(i8) +' ' +
'i9='+'---'+IntToStr(i9) +' ' +
'i0='+'---'+IntToStr(i0) ;
Edit3.Text := 'kk='+'---'+IntToStr(kk)+' ' +
'aa='+'---'+IntToStr(aa)+' ' +
'bb='+'---'+IntToStr(bb)+' ' +
'tt='+'---'+IntToStr(tt)+' ' +
'ii='+'---'+IntToStr(ii)+' ' +
'jj='+'---'+IntToStr(jj) +' ' +
'k1='+'---'+IntToStr(k1)+' ' +
't1='+'---'+IntToStr(t1) +' ' +
'f='+'---'+IntToStr(f) ;
end;
procedure TForm1.Button4Click(Sender: TObject);
begin
end;
///////// ///////////////////////////////////////////////////////
procedure TForm1.Button5Click(Sender: TObject);
begin
close
end;
initialization
randomize;
end.
Отредактировано ABC (2021-10-15 22:04:19)