Project Euler 76 - список всех разделов для заданного числа

Question

Вот как Project Euler Problem # 76 звучит так: «Сколько разных способов можно записать сто как сумму не менее двух натуральных чисел?»

У меня естьизо всех сил пытался сделать это правильно в течение нескольких дней, пытался решить по-разному и получил в основном те же результаты для небольших чисел (те, которые легко проверить).Я закончил с алгоритмом, который перечисляет все разделы для данного числа в алфавитном порядке, по убыванию (начиная с «N-1 + 1»).Написано в VB.NET:

Dim ub As Integer = 6
Dim wayCount As Integer = 0
For n = ub - 1 To 1 Step -1
  'init value array (first combination)
  Dim s As New List(Of Integer)
  For m = 1 To ub \ n : s.Add(n) : Next
  Dim b As Integer = ub Mod n
  If b <> 0 Then s.Add(b)

  'from where to start decrementing
  Dim k As Integer = s.Count - 1
  While k > 0 And s(k) = 1 : k -= 1 : End While

  Do
    wayCount += 1 : Console.WriteLine(String.Join(" + ", s) & " = " & s.Sum)
    If s(k) = 1 Then k -= 1
    If k = -1 Then Exit Do
    s(k) -= 1
    s.Add(1)
  Loop While k >= 1
Next

Console.WriteLine("count=" & wayCount)

Код работает для чисел 1-6 включительно и начинает давать сбой при N = 7, при пропущенной 1 комбинации.Для N = 8 он пропускает 2 (19 вместо 21).Для N = 100 ответ 4576, что на несколько порядков меньше, чем требуется.Очевидно, я упускаю некоторые очень важные детали.

Если у вас нет времени или средств для компиляции и запуска приведенного выше кода, вот вывод (N = 7):

6 + 1 = 7
5 + 2 = 7
5 + 1 + 1 = 7
4 + 3 = 7
4 + 2 + 1 = 7
4 + 1 + 1 + 1 = 7
3 + 3 + 1 = 7
3 + 2 + 1 + 1 = 7
3 + 1 + 1 + 1 + 1 = 7
2 + 2 + 2 + 1 = 7
2 + 2 + 1 + 1 + 1 = 7
2 + 1 + 1 + 1 + 1 + 1 = 7
1 + 1 + 1 + 1 + 1 + 1 + 1 = 7
count=13

Я изучил эти ссылки:

(ProjectEuler) Суммарные комбинации - предоставляет математическое решение, в котором не перечислены все комбинации

Создание разделовчисла - в языке Python, который я не могу прочитать / запустить / понять.

Любая помощь будет высоко ценится, заранее спасибо!

Answer 1

Вы говорите: «Код работает для чисел 1-6 включительно и начинает сбой при N = 7, при пропущенной 1 комбинации».Вы должны шагать по коду по одной строке для N = 7, либо в отладчике, либо вручную.Подробно увидев, что делает ваш код, вы сможете увидеть, где он пропускает комбинацию.

Answer 2

Существует довольно точное решение этой проблемы в закрытом виде, хотите верьте, хотите нет.

Формула Харди и Рамануджана:

                    e^(PI sqrt(2n/3))
            p(n) ~   -----------------
                        4n sqrt(3)

, который становится ближе как n-> бесконечность. Математик Радемахер сделал точную формулу, но это не красиво. Вот обсуждение.

Я бы рекомендовал прочитать об этом в Википедии и Mathworld здесь и здесь .

Это - обсуждение проблемы MathOverflow.

Я не говорю, что это лучшие решения этой проблемы. На самом деле для достаточно малых значений n это пустая трата времени, но интересно посмотреть на это решение, а также на более «ориентированные на компьютер».

Answer 3

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

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

Это может быть несколько грязной реализацией, но она работает в разумные сроки, даже в рамках рассматриваемой проблемы (до 5минут на моей машине), генерируя несколько миллионов разделов в секунду.Здоровая критика всегда приветствуется!

Dim ub As Integer = 10
Dim availableIncrements(ub - 2) As Integer
Dim weightCoefficients(ub - 2) As Integer
For i = 0 To ub - 2
  availableIncrements(i) = ub - i - 1
  weightCoefficients(i) = -1 'indicates that enumeration has not started yet
Next
Dim wayCount As Integer = 0

Dim pos, sum As Integer
pos = 0 : sum = 0
Do
  If weightCoefficients(pos) = -1 Then
    'when we came here first, charge coefficient to maximum available
    weightCoefficients(pos) = (ub - sum) \ availableIncrements(pos)
  ElseIf weightCoefficients(pos) > 0 Then
    'regular cycle: decrease by one
    weightCoefficients(pos) -= 1
  Else
    'return to previous bucket
    If pos = 0 Then Exit Do
    pos -= 1
    Continue Do
  End If

  'calculate current sum
  sum = 0
  For k = 0 To pos
    sum += availableIncrements(k) * weightCoefficients(k)
  Next
  'found combination
  If sum = ub And weightCoefficients(pos) > 0 Then
    wayCount += 1

    'printing to screen, remove when expecting many combinations
    Dim printList As New List(Of Integer)
    For i = 0 To pos 'which number to print
      For k = 1 To weightCoefficients(i) 'how many times to print a number
        printList.Add(availableIncrements(i))
      Next
    Next
    Console.WriteLine(String.Join(" + ", printList))

    'if we were in the last bucket and we just partitioned the number,
    'no need to go down and check all lower coefficients, instead move one column back.
    If pos = UBound(availableIncrements) Then
      pos -= 1
      Continue Do
    End If
  End If

  If pos < UBound(availableIncrements) Then
    pos += 1
    weightCoefficients(pos) = -1 'prepare to charge
  End If

  'this is something to keep you busy (so you know it's not hanging)
  'uncomment for long enumerations
  'If wayCount Mod 100000 = 0 Then Console.WriteLine(wayCount)
Loop

Console.WriteLine("count=" & wayCount)