求Matlab大神帮我看下如何能优化这个程序!题目是这样的： 一道离散数学： 10000条随机线段（线段长度不定）互相平行,从其中任选三条,求共有几组这样的线段两两可见（两两可见意
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/28 22:16:52
求Matlab大神帮我看下如何能优化这个程序!题目是这样的： 一道离散数学： 10000条随机线段（线段长度不定）互相平行,从其中任选三条,求共有几组这样的线段两两可见（两两可见意
求Matlab大神帮我看下如何能优化这个程序!
题目是这样的：
一道离散数学：
10000条随机线段（线段长度不定）互相平行,从其中任选三条,求共有几组这样的线段两两可见（两两可见意思是两条线段之间的垂直连线不被第三条线段隔断）
我写的是这样的~~~
x=5000-10000*rand(1,10000)
y1=10*rand(1,10000)
y2=-10*rand(1,10000)
A=zeros(10000)
for i=1:10000
for j=1:10000
fork=1:(j-1)
if(y1(i)>y1(k)&y1(j)>y1(k))|(y2(i)
求Matlab大神帮我看下如何能优化这个程序!题目是这样的： 一道离散数学： 10000条随机线段（线段长度不定）互相平行,从其中任选三条,求共有几组这样的线段两两可见（两两可见意
clear;
clc;
close all;
N=10000;
tic;
ye=10*rand(1,N);
ys=10*rand(1,N);
num = 0 ;
for i=1:N
if( ys(i) > ye(i) )
temp = ys(i) ;
ys(i) = ye(i) ;
ye(i) = temp ;
end
end
for i=1:N
for j=(i+1):N
yij_e=min(ye(i),ye(j));
yij_s=max(ys(i),ys(j));
if( yij_e <= yij_s ) % i,j投影不重叠, 三条直线必然两两可见
num = num + N - j ;
else
for k=(j+1):N
if( yij_s >= ye(k) || yij_e <= ys(k) ) % i,j的重叠投影与k不重叠, 三条直线两两可见
num = num + 1 ;
end
end
end
end
end
rate=num/N/(N-1)/(N-2);
inf=sprintf('num=%d, rate=%f',num,rate);
disp(inf)
toc;
matlab,实测35分钟,你还可以用matlab并行,估计能更快,但是优化空间有限
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
int main()
{
const int N=10000;
unsigned int ye[N], ys[N];
time_t t;
time(&t);
srand(t);
time_t t1 = clock() ;
unsigned int tempi ;
for( int i = 0 ; i < N ; ++ i )
{
ye[i] = rand() ;
ys[i] = rand() ;
if( ys[i] > ye[i] )
{
tempi = ys[i] ;
ys[i] = ye[i] ;
ye[i] = tempi ;
}
}
double num = 0.0 ;
for( int i = 0 ; i < N ; ++ i )
{
for( int j = i+1 ; j < N ; ++ j )
{
unsigned int yij_e=__min(ye[i],ye[j]);
unsigned int yij_s=__max(ys[i],ys[j]);
if( yij_e <= yij_s ) // i,j投影不重叠, 三条直线必然两两可见
num += double(N - j - 1) ;
else
{
for( int k = j+1 ; k < N ; ++ k )
if( yij_s >= ye[k] || yij_e <= ys[k] ) // i,j的重叠投影与k不重叠, 三条直线两两可见
num += 1.0 ;
}
}
}
double rate = num/double(N)/double(N-1)/double(N-2);
time_t t2 = clock() ;
double t_cost = double(t2-t1)/1000.0/60.0 ;
printf("num=%0.lf, rate=%lf, cost=%lf",num,rate,t_cost);
return 0;
}
C/C++,实测6.7分钟