数字游线问题——2002年第8期题解

问题描述请参见2002年第8期杂志。算法分析首先我们要对这个问题进行数学抽象。定义1:对于有理数组成的多重集合S,f(S)定义如下: 如果S是空集或只包含一个元素,则f(S)=S;否则f(S)=Uf((S-{r_1·r_2})∪{r}),对于每一个r=r_1+r_2,r_1-r_2,r_1×r_2,r_1÷r_2(if r_2≠0),且r_1,r_2取遍S中所有元素的组成的二元组。根据上述定义,在本问题中。