logo标签列表

把一个整数分解成最接近平方数的形式。

pythonalgorithmcythonfactoring
6
我有一个函数，它逐字节读取文件并将其转换为浮点数数组。 它还返回所述数组中的元素数量。现在，我想将数组重塑为最接近正方形的2D数组。 举个例子，让我们看看数字800： sqrt（800）=28.427... 现在，通过尝试和误差，我可以计算出25 * 32是我要找的解决方案。 如果整数相乘的结果过高，则减小sqrt（四舍五入到最近的整数），如果结果过低，则增加它们。 我知道有关于质数做此操作的算法，但这对我不是必需的。 我的问题是，即使实施了暴力方法，有时也会卡住并永远无法完成（这就是我设置迭代的任意限制原因）。 
import math

def factor_int(n):
    nsqrt = math.ceil(math.sqrt(n))

    factors = [nsqrt, nsqrt]
    cd = 0
    result = factors[0] * factors[1]
    ii = 0
    while (result != n or ii > 10000):
        if(result > n):
            factors[cd] -= 1
        else:
            factors[cd] += 1
        result = factors[0] * factors[1]
        print factors, result
        cd = 1 - cd
        ii += 1

    return "resulting factors: {0}".format(factors)

input = 80000
factors = factor_int(input)
使用上面的脚本会导致输出陷入循环打印。 
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0

但我想知道是否有更有效的解决方案？我肯定不是第一个想做这样事情的人。

2
如果n是一个质数，它必须一直到n*1作为因子吗？ - Daniel Lee
在这种情况下，如果它没有偶然找到两个质数，那么是的。虽然我假设我读取的数据总是可以用矩形表示的。现在我想想，它也可能会卡住。我更改每次迭代增加或减少的因子... - meetaig
我刚在我的博客上讨论了这个问题，读者在评论中提供了一些非常好的解决方案，比我的好多了。去看看吧。 - user448810
7个回答
阿里云服务器只需要99元/年，新老用户同享，点击查看详情
5
def factor_int(n):
    val = math.ceil(math.sqrt(n))
    val2 = int(n/val)
    while val2 * val != float(n):
        val -= 1
        val2 = int(n/val)
    return val, val2, n

尝试以下步骤：

for x in xrange(10, 20):
      print factor_int(x)
哇，那真是太快了。现在我感觉很蠢，我没有想到n/val... :D - meetaig
很酷，可能还有更好的方法。 - Daniel Lee
我并不是在寻找完美的解决方案，只是想要一个快速的解决方法！ :) - meetaig
谢谢。这是一个“非常优秀”的解决方案。 - techdog
1

有趣的问题，这里提供一个可能解决您问题的方案：

import math


def min_dist(a, b):
    dist = []
    for Pa in a:
        for Pb in b:
            d = math.sqrt(
                math.pow(Pa[0] - Pb[0], 2) + math.pow(Pa[1] - Pb[1], 2))
            dist.append([d, Pa])

    return sorted(dist, key=lambda x: x[0])


def get_factors(N):
    if N < 1:
        return N

    N2 = N / 2
    NN = math.sqrt(N)

    result = []
    for a in range(1, N2 + 1):
        for b in range(1, N2 + 1):
            if N == (a * b):
                result.append([a, b])

    result = min_dist(result, [[NN, NN]])
    if result:
        return result[0][1]
    else:
        return [N, 1]


for i in range(801):
    print i, get_factors(i)
这种方法的关键是找到与要求N=a*b，a和b为整数相符合的笛卡尔坐标点 [math.sqrt(N), math.sqrt(N)] 的最小距离。
我喜欢你的答案，因为你的方法背后有数学支持 :) 我将结果与我接受的答案的结果进行了比较，它们都给出了相同的结果（至少对于1到100000之间的整数）。 - meetaig
@meetaig 我相信我的解决方案可以进一步优化（现在是暴力解法），但至少提供了解决你问题的见解。 - BPL
1

我认为模运算符很适合这个问题：

import math 

def factint(n):
    pos_n = abs(n)
    max_candidate = int(math.sqrt(pos_n))
    for candidate in xrange(max_candidate, 0, -1):
        if pos_n % candidate == 0:
            break
    return candidate, n / candidate
1

这是一个基于当前被接受的答案的更短的代码，相比他们的代码，它需要运行时间少约25% - 75%（来自基本的timeit测试）：

from math import sqrt, ceil
def factor_int_2(n):
    val = ceil(sqrt(n))
    while True:
        if not n%val:
            val2 = n//val
            break
        val -= 1
return val, val2
这是一个我制作的小而凌乱的测试，用于测试该方法的效率： 
print("Method 2 is shorter and about {}% quicker".format(100*(1 - timeit(lambda: factor_int_2(12345))/timeit(lambda: factor_int(12345)))))
#returns 'Method 2 is shorter and about 75.03810670186826% quicker'
1
这是一种直接的方法，可以找到最小、最接近的整数a、b，使得a * b >= n，且a <= b，其中n是任意数字。 
def factor_int(n):
    a = math.floor(math.sqrt(n))
    b = math.ceil(n/float(a))
    return a, b
尝试使用它： 
for x in xrange(10, 20):
    print factor_int(x)
3
问题要求的是 a * b == n，而不是 a * b >= n。 - GZ0
1
这是为 UI 中具有可变数量项目的瓦片方案（行/列）创建的。 - Joe DF
0

一个数字的一行代码：

import numpy as np
n = 800
(np.ceil(np.sqrt(n)), np.ceil(n/np.ceil(np.sqrt(n))))

>>> (29.0, 28.0)

不确定这是否是你所要求的，但相比你在描述中提到的(25,32)，这更接近正方形。希望能对你有所帮助！

它更接近一个正方形，但29*28不是800... - meetaig
它更接近一个正方形，但29*28不是800... - undefined
0

这相当于找到因子(b,c)，使得a=b*c，并且较小的因子b是不大于sqrt(a)的最大数。这可以通过以下方式解决：

import math

def closest_factors(a):
    for b in range(int(math.sqrt(a)), 0, -1):
        if a%b == 0:
            c = a // b
            return (b,c)

 print(closest_factors(800))

返回 (25,32)。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，