※ 引述《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)