Closest-pair problem: Difference between revisions
Content added Content deleted
(Undo revision 270845 by Nuclearace (talk)) |
m (→{{header|REXX}}: added whitespace.) |
||
| Line 3,857: | Line 3,857: | ||
Programming note: this REXX version allows two (or more) points to be identical, and will |
Programming note: this REXX version allows two (or more) points to be identical, and will |
||
<br>manifest itself as a minimum distance of zero (the variable <big> <tt> '''dd''' </tt> </big> on line 17). |
<br>manifest itself as a minimum distance of zero (the variable <big> <tt> '''dd''' </tt> </big> on line 17). |
||
<lang rexx>/*REXX program solves the closest pair of points problem (in two dimensions). |
<lang rexx>/*REXX program solves the closest pair of points problem (in two dimensions). */ |
||
parse arg N low high seed . /*obtain optional arguments from the CL*/ |
parse arg N low high seed . /*obtain optional arguments from the CL*/ |
||
if N=='' | N=="," then N= 100 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N= 100 /*Not specified? Then use the default.*/ |
||
| Line 3,865: | Line 3,865: | ||
w=length(high); w=w + (w//2==0) /*W: for aligning the output columns.*/ |
w=length(high); w=w + (w//2==0) /*W: for aligning the output columns.*/ |
||
/*╔══════════════════════╗*/ do j=1 for N /*generate N random points*/ |
/*╔══════════════════════╗*/ do j=1 for N /*generate N random points*/ |
||
/*║ generate N points. ║*/ @x.j=random(low, high) |
/*║ generate N points. ║*/ @x.j= random(low, high) /* " a random X */ |
||
/*╚══════════════════════╝*/ @y.j=random(low, high) |
/*╚══════════════════════╝*/ @y.j= random(low, high) /* " " " Y */ |
||
end /*j*/ /*X & Y make the point.*/ |
end /*j*/ /*X & Y make the point.*/ |
||
A=1; B=2 /* [↓] MINDD is actually the squared*/ |
A=1; B=2 /* [↓] MINDD is actually the squared*/ |
||
minDD= (@x.A - @x.B)**2 + (@y.A - @y.B)**2 /*distance between the first two points*/ |
minDD= (@x.A - @x.B)**2 + (@y.A - @y.B)**2 /*distance between the first two points*/ |
||
/* [↓] use of XJ & YJ speed things up.*/ |
/* [↓] use of XJ & YJ speed things up.*/ |
||
do j=1 for N-1; xj=@x.j; yj=@y.j |
do j=1 for N-1; xj= @x.j; yj= @y.j /*find minimum distance between a ··· */ |
||
do k=j+1 to N /* ··· point and all the other points.*/ |
do k=j+1 to N /* ··· point and all the other points.*/ |
||
dd=(xj - @x.k)**2 + (yj - @y.k)**2 |
dd= (xj - @x.k)**2 + (yj - @y.k)**2 /*compute squared distance from points.*/ |
||
if dd<minDD then parse value dd j k with minDD A B |
if dd<minDD then parse value dd j k with minDD A B |
||
end /*k*/ /* [↑] needn't take SQRT of DD (yet).*/ |
end /*k*/ /* [↑] needn't take SQRT of DD (yet).*/ |
||
end /*j*/ /* [↑] when done, A & B are the points*/ |
end /*j*/ /* [↑] when done, A & B are the points*/ |
||
| Line 3,884: | Line 3,884: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
sqrt: procedure; parse arg x; if x=0 then return 0; d=digits(); m.=9; numeric form; h=d+6 |
sqrt: procedure; parse arg x; if x=0 then return 0; d=digits(); m.=9; numeric form; h=d+6 |
||
numeric digits; parse value format(x,2,1,,0) 'E0' |
numeric digits; parse value format(x,2,1,,0) 'E0' with g 'E' _ .; g= g *.5'e'_ % 2 |
||
do j=0 while h>9; m.j=h; |
do j=0 while h>9; m.j= h; h= h % 2 + 1; end /*j*/ |
||
do k=j+5 to 0 by -1; numeric digits m.k; g=(g+x/g)*.5; end /*k*/; |
do k=j+5 to 0 by -1; numeric digits m.k; g= (g+x/g)*.5; end /*k*/; return g</lang> |
||
{{out|output|text= when using the default input of: <tt> 100 </tt>}} |
{{out|output|text= when using the default input of: <tt> 100 </tt>}} |
||
<pre> |
<pre> |
||