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

В соревновании по программированию проблема заключалась в следующем:

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

Я рассматривал возможность использования тройных циклов for (грубая сила), но это было неэффективно, что привело к ПРЕВЫШЕНИЮ TIME LIMIT. (поскольку 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++;
   }
 }
}

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

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


series algorithm brute-force
person Community    schedule 23.11.2011    source источник
comment
x, y и z часто обозначают действительные числа. Здесь предполагается, что они целые? Положительный? Или тоже отрицательные числа?   -  person thiton    schedule 23.11.2011
comment
Потенциально полезно: en.wikipedia.org/wiki/   -  person sarnold    schedule 23.11.2011
comment
Это уравнение определяет плоскость в R3, содержащую бесконечное число целочисленных решений. Вы не можете перебрать бесконечный набор;)   -  person Blender    schedule 23.11.2011
comment
Скорее всего недостающее ограничение состоит в том, что x, y и z являются неотрицательными целыми числами.   -  person Alexey Frunze    schedule 23.11.2011
comment
Если это так (x, y, z — неотрицательные целые числа), можете ли вы использовать производящие функции для решения этой проблемы?   -  person David Hu    schedule 23.11.2011
comment
Хотите знать, почему 2 голоса против этого вопроса?   -  person yasouser    schedule 23.11.2011
comment
Я бы сказал, что Mathematics stackexchange является подходящим местом для этого вопроса.   -  person yasouser    schedule 23.11.2011
comment
@yasouser, потому что они, очевидно, упустили ключевую информацию. Также вопрос не по теме, вероятно, относится к math.stackexchange.com.   -  person Brock Adams    schedule 23.11.2011

Ответы (3)


arrow_upward
4
arrow_downward

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

Но здесь мы можем разработать простое решение. Я считаю, что 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 = Floor((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;

М = (15 - 5) деление 4 = 2

N = 3

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

person MBo    schedule 23.11.2011

arrow_upward
1
arrow_downward

Во-первых, обратите внимание, что 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(n3) вы можете достичь O(n) таким образом.

person loudandclear    schedule 23.11.2011
comment
При тестировании с n = 40 Brute Force = 36, в то время как это решение дает 45 ?? - person ; 23.11.2011
comment
Почему тесты ваших циклов <= n/4? Вы упускаете некоторые решения, потому что ваш диапазон слишком мал. - person loudandclear; 24.11.2011
comment
Я проверяю n/4, потому что уравнение показывает, что 4y = n. Итак, y не может быть больше n/4. То же самое и с з. - person ; 30.11.2011
comment
Правильно. Измените начальное значение start на 4, и оно должно работать нормально (соответственно отредактировал ответ). - person loudandclear; 30.11.2011
comment
Извините. Все еще не работает. Что, если n % 4 != 0? например: n = 432. Перебор = 5671 = это решение. Когда n = 479: грубая сила = 5671, это решение = 5565. - person ; 14.12.2011

arrow_upward
-1
arrow_downward

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

person yasouser    schedule 23.11.2011
comment
@ Down-voter: не могли бы вы указать причину, по которой вы проголосовали против? - person yasouser; 23.11.2011
comment
Не я, но исключение Гаусса здесь бесполезно. Система уравнений — это всего лишь одно уравнение. - person Tom Sirgedas; 23.11.2011