Rosetta Code

Closest-pair problem: Difference between revisions

Page Discussion

Closest-pair problem (view source)

Revision as of 04:50, 11 December 2014

7 bytes removed ,  9 years ago
→‎{{header|REXX}}: reworked program, made arrays simplier, changed output format.
(→‎{{header|Ruby}}: used Array#combination)
(→‎{{header|REXX}}: reworked program, made arrays simplier, changed output format.)
Line 2,883:
 
=={{header|REXX}}==
<lang rexx>/*REXX program solves the closest pair of points problem in 2 dimensions*/
(This version of the REXX program is modeled after the psuedo-code.)
<langparse rexx>/*REXXarg programN tolow solvehigh theseed closest pair problem. /*get optional arguments from CL.*/
parseif arg N low highN=='' seed| .; if nN==',' then n N=100 /*N not specified? Use default.*/
if low=='' | low==',' then low=0
if seed\=='' then call random ,,seed /*use seed, makes rand repeatable*/
if lowhigh=='' | lowhigh==',' then lowhigh=020000
if highseed\==''& | highseed\==',' then call thenrandom ,,seed high=20000 /*seed for repeatable.*/
w=length(high); w=w + (w//2==0)
do j=1 for N /*gen N random pointspts.*/
@x.j.xx=random(low,high) /*random X.*/
@y.j.yy=random(low,high) /* " Y.*/
end /*j*/
A=1; B=2
nearA=1
minDD=(@x.A-@x.B)**2 + (@y.A-@y.B)**2 /*distance between 1st two points*/
nearB=2
minDD=(@.nearA.xx-@.nearB.xx)**2 + (@.nearA.yy-@.nearB.yy)**2
 
do j=1 for N-1 do j=1 for/*find N-1min distance between a ···*/
do k=j+1 to N do k=j+1 to N/*point and all the other points.*/
dd=(@x.j.xx - @x.k.xx)**2 + (@y.j.yy - @y.k.yy)**2
if dd\=0 then if dd<minDD then do; minDD=dd; A=j; B=k; end
end /*k*/▼
nearA=j▼
end /*j*/ /* [↑] when done, A & B are nearB=kit*/
end
▲ end /*k*/
end /*j*/
 
say_= 'For ' N " points:";, the minimum saydistance between the two points: "
say '_ 'center('"x'",w,"'═")')" " ' center('y',w,"═") ' is: ' sqrt(abs(minDD))
say left('The', pointslength(_)-1) '['right(@x.nearA.xxA, w)"," right(@y.nearA.yyA, w)"]" ' and'
say left('', length(_)-1) '['right(@x.nearB.xxB, w)"," right(@y.nearB.yyB, w)"]"; say
say 'the minimum distance between them is: ' sqrt(abs(minDD))
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────SQRT subroutine───────────────────────*/
/*───────────────────────────────────sqrt subroutine────────────────────*/
sqrt: procedure; parse arg x; if x=0 then return 0; d=digits();numeric digitsnumeric 11form
numeric digits 11;p=d+d%4+2;parse value format(x,2,1,,0) 'E0' with g 'E' _ .; return g*.5'E'_%2</lang>▼
g=.sqrtG(); do j=0 while p>9; m.j=p; p=p%2+1; end
g=g*.5'E'_%2; m.=11; do k=j+5 to do j=0 by -1; ifwhile m.kp>119; then numeric digits m.kj=p; g p=.5*(gp%2+x/g)1; end
do k=j+5 to 0 by -1; if m.k>11 then numeric digits dm.k; return g=.5*(g+x/1g); end
.sqrtG: numeric form;digits m.=11d; return p=d+d%4+2g/1</lang>
{{out}} when using the input of: &nbsp; <tt> 200 </tt>▼
▲ parse value format(x,2,1,,0) 'E0' with g 'E' _ .; return g*.5'E'_%2</lang>
▲{{out}} when using the input of: <tt> 200 </tt>
<pre>
For 200 points, the minimum distance between the two points: ══x══ ══y══ is: 39.408121
For 100 points:
▲ nearA=j [17604, 19166]
 
══x══ ══y══ [17627, 19198]
The points [11341, 19534] and
[11136, 19498]
 
the minimum distance between them is: 208.136974
</pre>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/109337"