Алгоритм, который принимает целое число и возвращает все возможные форматы сложения

Question

Мне нужно написать алгоритм, который принимает целое число и возвращает все возможные форматы сложения

например,

Если я введу: 6

, он вернет следующую строку:

 0+6=6
 1+1+1+1+1+1=6
 1+1+1+1+2=6
 1+1+1+3=6
 1+1+4=6
 1+5=6
 2+1+1+1+1=6
 2+1+1+2=6
 2+1+3=6
 2+4=6
 3+1+1+1=6
 3+1+2=6
 3+3=6
 4+1+1=6
 4+2=6
 5+1=6
 6+0=6

Вот моя попытка:

import java.util.*;
public class Test
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter an integer? ");
        int num = in.nextInt();
        System.out.println();
        calculate(num);
    }
    private static void calculate(int n)
    {
        int[] arInt = new int[n];
        for(int i = 0; i <= n; i++)
        {
            for(int j = 0; j <= n; j++)
            {
                arInt[j] = i;
            }
            // ...
        }
    }
}

Answer 1

Я согласен с Брэдом. Вероятно, лучший способ выполнить это - рекурсия. На самом деле, я работал над чем-то связанным с этим прошлой ночью. Я решил свою проблему, используя рекурсивный алгоритм возврата. Посетите страницу Википедии: Возврат

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

Однако стоит обратить внимание на то, что 0. Вы можете бросить любое количество нулей в сложение / вычитание, и оно получится одинаковым.

Answer 2

Как правило, в такой проблеме вы не рассматриваете одни и те же комбинации с разными перестановками как разные значения, и вы не рассматриваете сложение на 0: см. Разделение . Тем не менее, в вашем примере вы, кажется, различаете различные перестановки и считаете 0. Я очень уверен, что вы не должны включать 0, потому что это даст вам бесконечно много примеров для любого n. (Кстати, ответ, который вы дали, не включает в себя все значения.) Поэтому я предполагаю, что вы различаете различные перестановки, но не допускаете сегментацию в 0. Это на самом деле значительно облегчает проблему.

Предположим, у вас n = 6.

   O O O O O O 
    ^ ^ ^ ^ ^

Подумайте о n - 1 = 5 позициях между шестью объектами выше. Для каждой позиции вы можете решить либо сегментировать в точке, либо нет. Например,

   O|O O O|O O 
    ^ ^ ^ ^ ^

является одним из возможных сегментирования. Интерпретируйте это как: 1 + 3 + 2, беря последовательные объекты, не сегментированные '|'. Вы должны быть в состоянии получить все возможные пути таким образом. А именно, для n-1 позиций, сегментируйте это или нет. Для любого n в вашем списке должно быть 2 ^ (n-1) примеров.

например. для n = 3: 1 + 1 + 1, 2 + 1, 1 + 2, 3 => 4 разных способа = 2 ^ (3-1)

для n = 6 у вас должно быть 2 ^ (6-1) = 32 примера, но у вас есть только 17, что сразу говорит о том, что ваш список неполон.

Наконец, обратите внимание, что, как я писал в начале, ваш вопрос отличается от вопроса о разделе, который гораздо более стандартен.

Answer 3

Если вы задали вопрос, вы, вероятно, застряли ... поэтому я дам вам подсказку:

Answer 4

Возможное решение в Java с использованием рекурсии:

public void run(int n)
{

    List<StringBuilder> combos = showAdditionsFor(n);

    for (StringBuilder s : combos)
    {
        if (s.indexOf("+") < 0)
        {
            System.out.println(s + " + 0 = " + n);
            System.out.println("0 + " + s + " = " + n);
        }
        else
        {
            System.out.println(s + " = " + n);
        }
    }
}

List<StringBuilder> showAdditionsFor(int n)
{
    List<StringBuilder> list = new ArrayList<StringBuilder>();
    if (n == 0)
        list.add(new StringBuilder(""));
    else if (n == 1)
        list.add(new StringBuilder(String.valueOf(1)));
    else
    {
        for (int i = 1; i <=n; i++)
        {
            //get n-i list
            List<StringBuilder> tempList = showAdditionsFor(n-i);
            appendToEachListElement(String.valueOf(i),tempList);
            list.addAll(tempList);
        }
    }

    return list;
}


private void appendToEachListElement(String x, List<StringBuilder>l)
{
    for (StringBuilder s : l)
    {
        if (s.length() == 0)
            s.append(x);
        else
            s.append("+" + x);
    }

}

Answer 5

Это похоже на домашнее задание, поэтому я не буду пытаться написать это для вас.Но я дам вам подсказку о решении.Вы зафиксировали количество, например, мрамор.Вы пытаетесь найти все возможные числа, которые складываются в это количество.Это означает, что вы должны как-то разделить шарики на группы.Если вы знаете основы комбинаторики, вы можете легко подсчитать возможности и перечислить их с помощью алгоритма.Удачи!