Найти K чисел, произведение которых равно N, сохраняя максимум K чисел минимальным - PullRequest
Новая
       21

Найти K чисел, произведение которых равно N, сохраняя максимум K чисел минимальным

0 голосов
/ 09 июня 2018

По сути, нам даны числа N и K, нам нужно найти массив размера K такой, что произведение элементов массива равно N с максимальным количеством минимизируемых элементов.

, например,:

420 3

Ответ: 6 7 10 объяснение: 420 можно записать как произведение 6,10 и 7. Также можно записать как 5 7 12, но 10 (максимум6 10 и 7) минимум 12 (максимум 5 7 12).

Ограничения: числа> 0;0 <= N <10 ^ 6;1 <= k <= 100 </p>

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

Ответы [ 2 ]

0 голосов
/ 10 июня 2018

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

Оригинальный ответ (неправильный) (см. Комментарий @gus):

Без подтверждения правильности, предполагая N>0, K>0 в псевдокоде:

  • Разложить N в простые множители, сохранить в массив F
  • найти наименьшее целое число m>=0, такое, что length(F) <= 2^m*K
  • Заполните F на 1 с, чтобы получить размер 2^m*K.
  • Для i=m down to 1
    • sort F
    • для j=1 to 2^(i-1)*K
      • F[j] = F[j] * F[2^i*K+1-j] (умножить наименьшее на наибольшее и т. д.)
    • F=F[1:2^(i-1)*K] (удалить верхнюю половину F)
  • F содержит результат.

Пример 420 3:

  • F={2,2,3,5,7}
  • m=1
  • F={1,2,2,3,5,7}
  • F={7,10,6} ВЫПОЛНЕНО

Пример 2310 2:

  • F={2,3,5,7,11}
  • m=2
  • F={1,1,1,2,3,5,7,11} (заполнить до 2^m*K и отсортировать)
  • F={11,7,5,6} (уменьшить до половины)
  • F={5,6,7,11} (сортировка)
  • F={55, 42} DONE

Пример N=17^3*72, K=3

  • F={2,2,2,3,3,17,17,17}
  • m=2
  • F={1,1,1,1,2,2,2,3,3,17,17,17}
  • F={17,17,17,3,6,4}
  • F={3,4,6,17,17,17}
  • F={3,4,6,17,17,17}
  • F={51,68,102}
0 голосов
/ 09 июня 2018

В основном, amritanshu имел довольно хорошую идею : у вас есть список основных факторов и вы разбили этот список на список, содержащий K самых больших факторов, и другой, содержащий другое простое числофакторы: 

[2, 2], [3, 5, 7]

Затем вы умножаете самый большой элемент первого списка на самый маленький элемент второго списка и перезаписываете элемент второго списка с результатом.Удалить самый большой элемент из первого списка.Повторяйте эти шаги, пока ваш первый список не станет пустым: 

[2, 2], [3, 5, 7]
[2], [6, 5, 7]  // 5 is now the smallest element
[], [6, 10, 7]

, вот еще один пример: 

N = 2310 = 2 * 3 * 5 * 7 * 11
K = 3

[2, 3], [5, 7, 11]
[2], [15, 7, 11]
[], [15, 14, 11]

однако, этот алгоритм все еще не идеален для некоторых случаев, таких как N = 2310,K = 2: 

[2, 3, 5], [7, 11]
[2, 3], [35, 11]
[2], [35, 33]
[], [35, 66]  // better: [], [42, 55]

Итак, я подумал, что вы на самом деле хотите разделить факторы так, чтобы факторы были как можно ближе к корню K-й буквы N. Итак, я придумаю этот алгоритм:

  • вычислите R, наименьшее целое число, большее или равное K-му корню из N
  • , вычислите gcd для R и N
  • , если gcd равно R,добавьте R в список, вызовите ваш алгоритм рекурсивно с помощью N / R, K-1, добавьте результат в список и верните список
  • , если gcd не равен R, добавьте его в R и перейдите к шагу 2

Вот немного кода Python: 

import math

def gcd(a, b):

    while b:
        a, b = b, a % b
    return a

def root(N, K):

    R = int(math.exp(math.log(N) / K))
    if R ** K < N:
        R += 1
    return R

def find_factors(N, K):

    if K == 1:
        return [N]
    R = root(N, K)
    while True:
        GCD = gcd(N, R)
        if GCD == R:
            return [R] + find_factors(N // R, K-1)
        R += GCD

РЕДАКТИРОВАТЬ:

Я только что заметил, что этот алгоритм все еще дает неверныйрезультаты во многих случаях.Правильный путь - увеличение R до деления N: 

def find_factors(N, K):
    if K == 1:
        return [N]
    R = root(N, K)
    while True:
        if N % R == 0:
            return [R] + find_factors(N // R, K-1)
        R += 1

Таким образом, вам не нужно gcd.

...