Фактор целое число к чему-то как можно ближе к квадрату

У меня есть функция, которая читает файл побайтно и преобразует его в массив с плавающей запятой. Он также возвращает количество элементов в указанном массиве. Теперь я хочу преобразовать массив в 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

Но мне интересно, есть ли более эффективные решения для этого? Конечно, я не могу быть первым, кто хочет сделать что-то подобное.

Источник

7 ответов

Решение
def factor_int(n):
    nsqrt = math.ceil(math.sqrt(n))
    solution = False
    val = nsqrt
    while not solution:
        val2 = int(n/val)
        if val2 * val == float(n):
            solution = True
        else:
            val-=1
    return val, val2, n

попробуйте это с:

for x in xrange(10, 20):
      print factor_int(x)
Источник

Я думаю, что оператор модуля хорошо подходит для этой проблемы:

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
Источник

Вот более короткий код, основанный на принятом в настоящее время ответе, который короче и занимает на 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'
Источник

Вот прямой метод, который находит самые маленькие и ближайшие целые числа 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)
Источник

Интересный вопрос, вот возможное решение вашей проблемы:

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)

Ключом этого метода является нахождение минимального расстояния до декартовой точки [math.sqrt(N), math.sqrt(N)], которое удовлетворяет требованиям целых чисел N=a*b, a&b.

Источник

Oneline код для одного номера:

      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), как вы упомянули в описании. Надеюсь, поможет!

Источник

Это эквивалентно нахождению факторов(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).

Источник
Другие вопросы по тегам