数组拆分算法

liangbch

一个数组，包含那个自然数1到n共n个元素，现在我们想把这个数组拆成几个更小的数组，使得 1.拆出来的每个子数组所有元素的最小公倍数小于2^32 2. 拆出来的子数组尽可能的少 3. 当然了,拆出来的各个子数组没有交集. 为了方便起见,我们以n=100为例,请大家给出好的拆分算法,或者给出一个好的拆分结果

winxos

我觉得： 应该尽量使得每组的最小公倍数极大，可以将所有的数按照因子来分类，尽量将因子有重合的分到一组，再按照2^32来计算下多少个因子会乘到这么大。 现在只有这点思路。

g99

因子有重合的分到一组，岂不是最小公倍数极小？

winxos

就是因为极小，所以才分到一组，那样才可以容纳更多的数到一组啊， 因为要求组数最少啊。

gxqcn

感觉楼主这道题与我在5个月发的那个[悬赏]最少分组方案算法非常类似， 但比我那个更难些，因为我那个针对的对象是素数，只需求积即可。

gxqcn

可先将这些数因数分解，然后将这些素数升序排列， 若某个素数p重复r次，则以p^r代替这r个p；替换完成后再排序； 然后借鉴我那帖里面的算法得到优化解，虽然该解不等同于楼主问题的最优解，但至少可以参考参考。

无心人

能不能通过对数转化成矩阵？？

liangbch

我现在想到2个方法，令 $L=2^32$ 第一个方法是顺序取数， 1. i=1 2.按照从到大的原则，从原始数组A中顺序去数，直到这几个数的最小公倍数$M_i$ 刚好小于L，将A中的所有$M_i$ 的因数取出,移动数组$B_i$,剩余的数仍然叫做A. 3.i=i+1 4.重复步骤2,直到数组中的数组取完为止. 说明:一点改进,为了达到较好的效果,步骤1可以做一些改进.当几个数的公倍数$M_i$小于L,而在取下一个数后,其公倍数将大于等于L时, 这时可在M上乘以一个适当的较小的因子f,使得$M_i=M_i*f$且$M_i

gxqcn

楼上想法是按“从小到大”的顺序取数， 我则更倾向于“从大到小”的顺序取数， 源于最简单“石头、沙、水”装瓶原理。

无心人

首先确定下？ 最大数字多大？