Обнаружение, может ли быть записано целое число как кратность заданных

Question

У меня есть набор заданных целых чисел:

A[] = { 2, 3, 4, 5, 6, 7, 8, 10, 15, 20, 25, 30, 40, 50, 100, 500 }

1. Я хочу проверить, можно ли записать данное целое число T как кратное число в A[];РЕДАКТИРОВАТЬ УТОЧНЕНИЕ: можно использовать любое число в A [] . При использовании можно использовать только один раз.Пример 60 является действительным T.60 = 30 * 2.AlSO 90 действителен.90 = 3 * 5 * 6

2. Проверьте , какие числа могут образовать это целое число T.

3. Также вернуть 2 ближайших целых числа к данному T (которые могут быть записаны таким образом), если число T не может быть записано как кратное число этих чисел.

Части 2 и 3Я думаю, что смогу разобраться со своим, если кто-то поможет мне с частью 1.

Я знаю, что это алгоритмический или даже математический вопрос, но если кто-то может помочь, пожалуйста, сделайте.

НЕ РАБОТАЕТ.СМ. КОММЕНТАРИЙ НИЖЕ.

#

РЕШЕНИЕ.ОЧЕНЬ ОЧЕНЬ БОЛЬШОЙ ДЛЯ ВСЕГО ОТВЕТА. 1 (но автор решил удалить его, и я не знаю, почему, поскольку он был правильным.) Автор (не помню вашего имени.)

#

Код решения с поворотом (авторский алгоритм использовал несколько раз один множитель. Этот алгоритм использует множитель только 1 раз)

int oldT = 0;
        HashMap<Integer, Boolean> used = new HashMap<Integer, Boolean>();
        while (T != 1 && T != -1) {
            oldT = T;
            for (int multiple : A) {
                if (!used.containsKey(multiple)) {
                    if (T % multiple == 0) {
                        T = T / multiple;
                        used.put(multiple, true); 
                    }
                }
            }
            if (oldT == T)
                return false;
        }
        return true;

Answer 1

Если T не очень большой (скажем, <10 ^ 7), это прямой DP. </p>

a[1] = true; // means that number '1' can be achieved with no multipliers
for (every multiplier x) {
   for (int i = T; i > 0; --i) {
      if (a[i] and (i * x <= T)) {
          // if 'i' can be achieved and 'x' is a valid multiplier,
          // then 'i * x' can be achieved too
          a[i * x] = true;
      }
   }
}

Предполагается, что каждый множитель можно использовать только один раз.
Теперь вы можете найти декомпозицию T, если у вас есть другой массив b [i], хранящий множитель, который был использован для достижения i.

Существует много онлайн-контента для знакомства с динамическим программированием, если у вас мало времени. Это должно дать вам представление о том, как подойти к таким проблемам. Например, этот кажется неплохим
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Answer 2

Я не совсем уверен, что вы спрашиваете.

Если пользователь может выбрать n * (одно из этих чисел), то обратите внимание, что у вас есть простые числа 2, 3, 5 и 7, поэтому, если ваше число делится на 2, 3, 5 или 7, то разделите это, и тогда у вас есть n * (тот).

Если вам нужно умножить числа друг на друга, но вы можете сделать это несколько раз, то обратите внимание, что все ваши числа делятся на степени 2, 3, 5 и 7. Проверьте, делится ли ставка только на это (делите каждый, пока вы не сможете больше делить, затем посмотрите, осталось ли у вас 1) и посчитайте, сколько раз вы поделили на каждый.

Если вам нужно умножить числа друг на друга без замены , то снова найдите простую факторизацию и удалите из списка любое число, которое делает представленные полномочия наиболее четными. Если вам удастся удалить все кратные, все готово.

Во всех случаях, кроме последнего, число ставок может быть очень плотным, поэтому вы можете найти ближайший, просто поднявшись или опустившись и проверив еще раз. В последнем случае поиск чего-то близкого может быть довольно сложным; Вы можете просто составить таблицу возможных (низких) ставок и предложить что-то из этого, предполагая, что пользователи не собираются делать ставки 2 * 3 * 4 * 5 * 6 * 7 * 8 * 10 * 15 * ... .