作者yauhh (哟)
看板CSSE
标题Re: [问题] 未排序的阵列，演算法相关问题
时间Sun May 9 17:24:59 2010
※ 引述《LPH66 (-858993460)》之铭言：
: d = 100
: X = {90, 95, 96, 97, 98, 99, 60, 65}
: Y = {40, 30, 50, 51, 52, 53, 54, 55}
下一版演算法: 既然前面曾提到跟 merge sort 很像,那就
1. Sort X and Y by merge sort and generate a sorted key-value list Xy.
Xy = {{2,30},{2,40},{2,50},{2,51},{2,52},{2,53},{2,54},
{2,55},{1,60},{1,65}{1,90},{1,95},{1,96},{1,97},
{1,98},{1,99}}
key标为1是来自X阵列,key标为2是来自Y阵列.
2. ib = 0, ie = length of Xy - 1, d = 100,
d' = sum of values of Xy[ib] and Xy[ie] = 30 + 99
3. if d' = d, and key of Xy[ib] =\= key of Xy[ie], output(ib, ie) if ib is
for set #1 or output(ie, ib) if ie is for set #1, and then program ends.
4. while ib < ie, do:
t = near(ib+1, ie-1)
// Find which of value of Xy[ib+1] and Xy[ie-1] makes d' nearer
// to d than Xy[ib] and Xy[ie].
if (t == ib+1) ib++
if (t == ib-1) ie--
d' = sum of values of Xy[ib] and Xy[ie]
Try step 3.
if the loop ends, echo("No solution").
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.160.114.63
※ 编辑: yauhh 来自: 218.160.114.63 (05/09 17:34)