Обманчиво просто? Учитывая целое число, найдите SET CLOSEST целых чисел, которые точно делят его?

Question

Учитывая положительное целое число объектов, скажем, маленьких ящиков, я хотел бы аккуратно их выложить на столе в хорошем 2d-блоке, который может или не может образовывать прямоугольник, но не старый прямоугольник, такой как близко к квадрату, насколько это возможно. Для этого мне нужны целые числа TWO, которые делят целое число объектов, максимально приближенных друг к другу.

Например,

Скажем, у меня есть 12 объектов. Я мог заложить их как

(12 х 1) или (1 х 12) или (6 х 2) или (2 х 6) или (3 х 4) или (4 х 3)

Я хочу, чтобы они были как (4 x 3), или даже (3 x 4), но предполагали, что наибольшее значение приходит первым, так как это самая большая пара, которая делит число, которое является самым близким.

Учитывая некоторое положительное целое число x, какой алгоритм вернет (y, z) где;

((у * г) = х) и (у> г) и (абс (у - г) является минимальным)

Когда нет решения, я мог поиск решение путем увеличения целого числа, начиная с количества объектов, которые у меня есть, найти ближайшее решение, а затем подставить мои объекты в это решение, оставив пробелы.

BUT ... Теперь давайте подберем темп!

Что делать, если я расширяю это сейчас на 3d, а не на плоской плоскости, и я хочу сделать хороший аккуратный блок из них, предположим, что кубические объекты в 3d-пространстве имеют CLOSEST THREE чисел, которые делят целое число объектов, максимально приближенных друг к другу, чтобы сформировать самую компактную, плотно упакованную 3d-структуру из этого числа объектов? Например,

Скажем, у меня есть 12 объектов. I может Оформить их как

(12 x 1 x 1) или (1 x 12 x 1) или (1 x 1 x 12) или (2 x 2 x 3) или (2 x 3 x 2) или (3 x 2 x 2) ...

Где я принимаю их как компактный (3 x 2 x 2) блок объектов.

Не являясь математиком, во-первых, Какова эта фактор-проблема, называемая, и, во-вторых, существует алгоритм, который может сделать это для любого положительного целого и предложить, когда решение невозможно.

Я знаю, что это начинается с факторинга целое число, а затем ...

бонусными баллами ... Может ли быть способ сделать 4 размерные решения? N мерный?

Я пытаюсь написать алгоритм C++, но это целая математическая проблема, которую я ударил.

Thank-you.

Answer 1

Вы хотите фактор целого числа п в к факторов, сводя к минимуму общего расстояния Евклида среди всех к _я. Для этого всегда есть решение, при условии, что 0 < k и 0 < n. Например, рассмотрите n = любое простое число: решение {n} + {1 повтор k - 1 раз}.

рекурсивный псевдокод подход:

list<int> reduce(int n, int k, list<int> factors) 
    // validity checks for 0 < k, 0 < n omitted 
    // if there's only one factor left, we know what it is 
    if(k == 1) 
    factors.add(n) 
    return factors 
    // we know all the remaining factors because n can't be reduced further 
    if(n is prime || n == 1) 
    factors.add(n) 
    return reduce(1, k - 1, factors) 
    // take the k-th root of n, rounded up 
    int r = ceiling(root(n, k)) 
    // if there's an exact root here, we're done; remaining factor distance = 0 
    if(n % r == 0) 
    do k times 
     factors.add(r) 
    return factors 
    // otherwise find the next largest remaining factor 
    while(n % r != 0) 
    r -= 1 
    factors.add(r) 
    return reduce(n/r, k - 1, factors) 

Этот код предназначен быть ясным, а не оптимизированы.

Концептуально вы пытаетесь свести к минимуму диагональное измерение, образованное путем расширения всех факторов из точки под прямым углом. Если K = 2, вы минимизируя гипотенузу прямоугольного треугольника, образованного размещая K под прямым углом к ​​к. Для k = 3 он минимизирует площадь треугольника, образованного путем создания всех трех факторов ортогонально (т. Е. Образуя оси X-Y-Z трехмерного декартового графа). Для k = 4 это сводит к минимуму объем тетраэдрического твердого тела; и т. д. Чтобы построить эту форму итеративно, в приведенном выше алгоритме используется k-й корень, чтобы связать размер добавляемого нового измерения.

Если вы хотите, чтобы результаты отсортированы, ну, просто отсортируйте возвращенный список. Предположительно n >>k, поэтому k log k Стоимость сортировки тривиальна по сравнению со стоимостью факторизации. Или, я полагаю, вы могли бы использовать структуру сортировки по сортировке в качестве возвращаемого типа, если вы ленивы.

Некоторые примеры работали:

п = 12, к = 3

• г = 3 (кубический корень из 12 округляется)
• 12% 3 == 0; 3 - коэффициент
• recurse; n = 4, k = 2
• r = 2 (квадратный корень из 4)
• 4% 2 == 0; Добавьте 2 к факторам 2 раза
• результат: {3, 2, 2}

п = 32, к = 3

• г = 4 (кубический корень из 32 округляется)
• 32% 4 == 0; 4 - коэффициент
• recurse; n = 8, k = 2
• r = 3 (квадратный корень из 8 округленных)
• 8% 3! = 0; r = 2
• 8% 2 == 0; 2 - коэффициент
• recurse; n = 2, k = 1
• k == 1; 2 представляет собой фактор
• результат: {4, 2, 2}

п = 25, к = 4

• г = 2 (Quad корень из 25 округляется)
• 25 % 2! = 0; r = 1
• 25% 1 == 0; 1 - коэффициент
• recurse; n = 25, k = 3
• r = 3 (кубический корень из 25 округленных)
• 25% 3! = 0; r = 2
• 25% 2!= 0; r = 1
• 25% 1 == 0; 1 - коэффициент
• recurse; n = 25, k = 2
• r = 5 (квадратный корень из 25)
• 25% 5 == 0; Добавьте 5 к факторам 2 раза
• результат: {1, 1, 5, 5}

Другие результаты:

• п = 88, к = 3 -> {4, 2, 11}
• п = 66, к = 5 -> {2, 1, 3, 11, 1}
• п = 14, к = 3 -> {2, 7, 1}
• п = 15 , k = 3 -> {3, 5, 1}
• n = 18, k = 2 -> {3, 6}
• п = 39, к = 3 -> {3, 13, 1}
• п = 49, к = 3 -> {1, 7, 7}