Как разбить число?

Question

[iBadCoder]

Ни как не могу придумать алгоритм для разбиения числа на с#. Необходимо, чтобы при вводе например числа 4, программа выводила все варианты разбиения:
1 + 1 + 1 + 1
2 + 2
2 + 1 + 1
3 + 1
4

Comments

[freeExec]

Ни как не могу придумать алгоритм для разбиения числа на с#

Ну хорошо, а не на шарпе как выглядит ваш алгоритм?

[Lynn «Кофеман»]

Забанили?
https://yandex.ru/search/?text=разбиение+числа+на+...

Answer 1

[MaximKAI]

/// <param name="remain">Оставшаяся часть нашего числа</param>
/// <param name="maxTerm">Максимальный размер слагаемого</param>
/// <param name="terms">Список слагаемых</param>
static void Solve(int remain, int maxTerm, List<int> terms)
{
    //Если от числа ничего не осталось, выводим все слагаемые и выходим из функции
    if (remain == 0)
    {
        Console.WriteLine(string.Join(" + ", terms));
        return;
    }

    //Перебираем возможные слагаемые от наибольшего до 1
    for (int term = maxTerm; term >= 1; term--)
    {
        if (term <= remain)
        {
            terms.Add(term);
            Solve(remain - term, term, terms);
            terms.Remove(term);
        }
    }
}

Вызываем метод:

var partitions = new List<int>();
Solve(n, n, partitions); //n - число для которого нужно найти разбиения

Answer 2

[mayton2019]

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