从给定数字中,确定其产品为原始数字的三个紧密数字

Question

我有一个号码n,我想找到三个号码,其产品n尽可能彼此接近.也就是说,如果n = 12那时我想得到3,2,2结果,而不是6,1,2.

想到它的另一种方法是,如果n是长方体的体积,那么我想找到两侧的长度,以便使长方体尽可能像立方体(即,长度尽可能相似).这些数字必须是整数.

我知道不太可能有一个完美的解决方案,而且我很乐意使用能够在大多数时候给出一个好答案的东西,但我想不出去想出这个算法.有任何想法吗？

Answer 1

这是我的第一个算法草图,被授予n相对较小:

• 计算质因子的n.
• 挑选出三大并将它们分配到f1,f2,f3.如果少于三个因素,请分配1.
• 以递减顺序循环其余因子,将它们乘以当前最小的分区.

编辑

我们来看吧n=60.

其主要因素是5 3 2 2.

设置f1=5,f2=3和f3=2.

剩下2的乘以f3,因为它是最小的.

我们结束了5 * 4 * 3 = 60.

编辑

此算法将找不到最佳,通知btillys评论:

考虑17550 = 2*3*3*3*5*5*13.当最佳值为25,26,27时,您的算法将给出15,30,39.

编辑

好的,这是我的第二个算法草图,有一个稍微好一点的启发式:

• 设置列表L的主要因素的n.
• 设置r的立方根的n.
• 创建一组三个因子F,最初设置为1.
• 按降序迭代素数因子:
  • 尝试将当前因子L[i]与每个因子相乘,然后按降序排列.
    • 如果结果小于r,则执行乘法并继续下一个素数因子.
    • 如果没有,请尝试下一个F.如果超出Fs,则乘以最小的一个.

这适用于以下情况17550:

n=17550
L=13,5,5,3,3,3,2
r=25.98

F = { 1, 1, 1 }

迭代1:

• F[0] * 13小于r,设定F为{13,1,1}.

迭代2:

• F[0] * 5 = 65比起来更重要r.
• F[1] * 5 = 5小于r,设定F为{13,5,1}.

迭代3:

• F[0] * 5 = 65比起来更重要r.
• F[1] * 5 = 25小于r,设定F为{13,25,1}.

迭代4:

• F[0] * 3 = 39比起来更重要r.
• F[1] * 3 = 75比起来更重要r.
• F[2] * 3 = 3小于r,设定F为{13,25,3}.

迭代5:

• F[0] * 3 = 39比起来更重要r.
• F[1] * 3 = 75比起来更重要r.
• F[2] * 3 = 9小于r,设定F为{13,25,9}.

迭代6:

• F[0] * 3 = 39比起来更重要r.
• F[1] * 3 = 75比起来更重要r.
• F[2] * 3 = 27大于r,但它是我们能得到的最小的F. 设置F为{13,25,27}.

迭代7:

• F[0] * 2 = 26比r这更重要,但它是我们能得到的最小的F. 设置F为{26,25,27}.