Избежание грубой силы: подсчет решений - PullRequest
Новая
       8

Избежание грубой силы: подсчет решений

2 голосов
/ 23 ноября 2011

В соревновании по программированию проблема была:

Подсчитайте все решения уравнения: x + 4y + 4z = n. Ты будешь учитывая n, и вы будете определять количество решений. Предположим, что x, y и z являются положительными целыми числами.

Я подумал об использовании тройных циклов for (перебор), но это было неэффективно, в результате чего TIME LIMIT EXCEED. (поскольку n может быть = 1000 000): 

int sol = 0;
for (int i = 1; i <= n; i++)
{
 for (int j = 1; j <= n / 4; j++)
 {
  for (int k = 1; k <= n / 4; k++)
   {
      if (i + 4 * j + 4 * k == n)
         sol++;
   }
 }
}

Мой друг мог решить проблему. Когда я спросил его, он сказал, что он вообще не использовал грубую силу. Вместо этого он преобразовал уравнение в «серию» (то есть суммирование). Я попросил его рассказать, как я, но он отказался:)

Могу я узнать как?

Ответы [ 3 ]

4 голосов
/ 23 ноября 2011

Это частный случай проблемы с монетой , которая в общем случае решается с помощью динамического программирования.

Но здесь мы можем разработать простое решение.Я рассматриваю x, y, z> 0

x + 4 * (y + z) = n Пусть y + z = q = p + 1 (q> 1, p> 0)

x + 4 * q = n

x + 4 * p = n-4

Есть M = Этаж ((n-5) / 4) вариантыдля x и p, следовательно, существует M возможных значений q = 2..M + 1 Для каждого q> 1 существуют (q-1) варианты y и z: q = 1 + (q-1) = 2 +(q-2) + .. + (q-1) + 1

Итак, мы имеем N = 1 + 2 + 3 + ... + M = M *(M + 1) / 2 решения

Пример:

n = 15;

M = (15 - 5) div 4 = 2

N = 3

(3,1,2), (3,2,1), (7,1,1)

1 голос
/ 23 ноября 2011

Первое замечание: n-x должно делиться на 4. Начните с поиска наименьшего значения, которое может принять x: 

start = 4
while ((n - start) % 4 != 0)
{
    start = start + 1
}

Отныне вы знаете, что x будет принимать значения от [start, start+4, start+8 ...]. Теперь вы можете подсчитать количество решений простым циклом подсчета: 

count = 0

for (x = start; x < n - 4; x = x + 4)
{
    y_z_sum = (n - x) / 4
    count = count + y_z_sum - 1
}

Для каждого выбора x мы можем вычислить значение y+z. Для каждого значения для y+z существует y+z-1 возможных вариантов (поскольку y находится в диапазоне от 1 до y+z-1, при условии, что y и z являются положительными целыми числами).

Вместо решения методом грубой силы со временем O (n 3 ) вы можете достичь O (n) таким образом.

0 голосов
/ 23 ноября 2011

Это классическая задача линейной алгебры. Пожалуйста, обратитесь к любому учебнику линейной алгебры о том, как решить систему линейных уравнений. Один такой метод называется Гауссово исключение .

...