数组拆分算法

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<L$.


  第二个方法是小质因数优先法:
1. i=1
2. 求出数组A中所有数的最小公倍数,不是真正的算出来,而是得到一个素因子乘积的形式, 若数组$P_k$是刚好小于等于n的质数,则
数组A中所有数的最小公倍数 $M= P_1^{e_1}*P_2^{e_2}*...P_k^{e_k}$, 其中$e_i$ 是使得 $p_i^{e_i}<=n$的最大整数. 如n=30时, 有m=2*2*2*2*2*3*3*3*5*5*7*11*13*17*19*23*29*31

3.从M中按照从小到达的顺序选取质因数,使这几个质因数的乘积刚好小于L,上例中, 需要选择 T=2*2*2*2*2*3*3*3*5*5*7*11*13=367567200<L. 将数组A中的所有T的因数
移到数组$Bi_$.
4.i=i+1
5.求数组A中的所有自然数的最小公倍数 $M=P_1^{e_1}*p_2^{e_2}*...P_k^{e_k}$,这时计算方法不同于步骤1,需要先对数组A中的所有自然数数作批量质因数分解,
6.从M中按照从小到达的顺序选取质因数,使这几个质因数的乘积T刚好小于L, 将数组A中的所有T的因数移到数组Bi,如数组A非空,则结束,否则重复步骤4-6。

gxqcn

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

无心人

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