|
为了更好地反映组合算法设计中的三原则对算法效率的影响，我们对“球迷购票问题”的五个模型进行了实验，其总结如下：
一、系统设置：
CPU: Intel 633 Celeron
RAM: 128MB
OS: Windows Me
算法运行环境：Turbo Pascal 7.0
二、 规模确定：
由于此实验的目的是确定模型的优劣，所以测试数据所得结果控制在长整型以内。由计算得到1≤n≤17。为了更好地反映算法的效率，尤其是信息冗余对算法效率的影响，在进行n值选取时，我们选的是不均匀的。
三、时间测定算法：
Begin
t:=meml[$40:$6c];
主程序；
t:=(meml[$40:$6c]-t)/18.2;
out(t)
end.
四、实验结果
N
结果
模型1运行时间
模型2运行时间
模型3运行时间
模型4运行时间
模型5运行时间
5
42
0.0000
0.0000
0.0000
0.0000
0.0000
10
16796
0.0000
1.1538
0.0000
0.0000
0.0000
13
7429000
0.1099
>60
0.2747
0.0000
0.0000
15
9694845
1.1538
>60
3.6813
0.0000
0.0000
16
35357670
4.2308
>60
13.5165
0.0000
0.0000
17
129644790
15.3846
>60
49.5055
0.0000
0.0000
(时间单位：s)
【源程序】
[1] 算法1—1 的源程序
Program Arithmtic1_1;
Var n,m:array[0..100] of longint;
t,i:integer;
Begin
write('Please input t:');
readln(t);
n[0]:=1;
m[0]:=0;
for i:=1 to t do
begin
n[i]:=m[i-1];
m[i]:=3*n[i-1]+2*m[i-1];
end;
writeln('N=',n[t]);
writeln('M=',m[t]);
End.
[2] 算法1—2的源程序
Program Arithmetic1_2;
var t:integer;
n,m:longint;
begin
write('Please input t:');
readln(t);
n:=trunc(exp(t*ln(3)));
m:=trunc(exp((t+1)*ln(3)));
if odd(t) then begin
n:=n-3;
m:=m+3;
end
else begin
n:=n+3;
m:=m-3;
end;
n:=trunc(n/4);
m:=trunc(m/4);
writeln('N=',n);
writeln('m=',m);
end.
[3]算法2的源程序
Program Arithmetic2;
Const InFile='input.txt';
OutFile='output.txt';
pi=3.1415926535;
s1=2/3*pi-1.732/2;
s2=pi/2-1;
s3=5/12*pi-1.732/2;
Var list,info:Array[1..100,1..100] of shortint;
x,y: Array[1..100] of integer;
n: Integer;
area,s4: real;
Procedure init;
Var f:Text;
a:integer;
Begin
assign(f,InFile);
reset(f);
readln(f,n);
for a:=1 to n do
read(f,x[a],y[a]);
close(f);
s4:=4*sin(pi/12)*sin(pi/12)+pi/12-1/4;
End;
Function dissmilaruty_function(k1,k2:integer):integer;
Var l:integer;
Begin
l:=abs(x[k1]-x[k2])+abs(y[k1]-y[k2]);
if l>2 then dissmilaruty_function:=0
else dissmilaruty_function:=l;
End;
Procedure done;
var i,j,k,p,count1,count2:integer;
check: boolean;
Begin
count1:=0;
count2:=0;
area:=n*pi;
for i:=1 to n-1 do
for j:=i+1 to n do
begin
list[i,j]:=dissmilaruty_function(i,j);
if list[i,j]=1 then inc(count1)
else if list[i,j]=2 then inc(count2);
end;
area:=area-count1*s1-count2*s2;
count1:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
begin
check:=true;
p:=list[i,j]+list[j,k]+list[i,k];
if (list[i,j]=0) or (list[j,k]=0) or (list[i,k]=0)
then check:=false;
if (p=4) and check then
begin
inc(count1);
if list[i,j]=2 then info[i,k]:=2
else if list[j,k]=2 then info[j,k]:=2
else if list[i,k]=2 then info[i,k]:=2;
end;
end;
area:=area+s3*count1;
count1:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
if (j<>k) and (info[i,j]=2) and (list[j,k]=1) and (list[i,k]=1) then
inc(count1);
area:=area-s4*count1;
End;
Procedure out;
Var f:text;
Begin
assign(f,OutFile);
rewrite(f);
writeln(f,area:0:4);
close(f);
End;
Begin
Init;
Done;
Out;
End.
[4]算法3—1的源程序
{$A+,B-,D-,E+,F-,G+,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 65520,0,655360}
Program Arithmetic3_1;
Var n,k,m:integer;
total:longint;
Procedure DFS(i:integer);
Var j:integer;
Begin
for j:=0 to 1 do
begin
if (j=0) then begin
inc(k);
inc(m);
if (m=n) then inc(total)
else dfs(i+1);
dec(k);
dec(m);
end
else begin
if k>0 then
begin
dec(k);
dfs(i+1);
inc(k);
end;
end;
end;
End;
Begin
read(n);
m:=0;
k:=0;
dfs(1);
writeln(total);
End.
[5]算法3—2的源程序
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+}
{$M 65520,0,655360}
program Arithmetic3_2;
var n:integer;
data:Array[1..100] of integer;
flag:set of byte;
total:longint;
function check(s:integer):boolean;
var a,b:integer;
begin
check:=false;
for a:=1 to s-2 do
for b:=a+1 to s-1 do
if (data[b]<data[s]) and (data[s]<data[a]) then exit;
check:=true;
end;
procedure stack(i:integer);
var j:integer;
begin
for j:=1 to n do
if not(j in flag) then
begin
data[i]:=j;
if check(i) then
begin
flag:=flag+[j];
if i=n then inc(total)
else stack(i+1);
flag:=flag-[j];
end;
end;
end;
begin
read(n);
stack(1);
writeln(total);
end.
[6]算法3—3的源程序
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+}
{$M 65520,0,655360}
program Arithmetic3_3;
var n:integer;
function f(a,b:integer):longint;
begin
if a<b then f:=0
else if b=0 then f:=1
else f:=f(a-1,b)+f(a,b-1);
end;
begin
read(n);
writeln(f(n,n));
end.
[7]算法3—4的源程序
Program Arithmetic3_4;
Var data :array[1..20,1..20] of longint;
a,b,n:integer;
Begin
readln(n);
for a:=1 to n do data[a,1]:=a;
for a:=2 to n do
for b:=2 to a do data[a,b]:=data[a-1,b]+data[a,b-1];
writeln(data[n,n]);
End.
[8]算法3—5的源程序
Program Arithmetic3_5;
Var n,a,b:integer;
total:longint;
Begin
readln(n);
total:=1;
a:=n+2;
b:=2;
while (a<=2*n) do
begin
total:=total*a;
while (total mod b=0) and (b<=n) do
begin
total:=total div b;
inc(b);
end;
inc(a);
end;
while b<n do
begin
total:=total div b;
inc(b);
end;
writeln(total);
End.
|
