Разминка для мозгов: разбиение натурального числа на 3 слагаемых

Продолжаем рубрику Разминка для мозгов. Очередная задачка ))

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

Для справки: в данной задаче под натуральным числом подразумевается число из расширенного натурального ряда: целое неотрицательное число, включая 0.

Постарайтесь выбрать оптимальный алгоритм решения задачи.

Я тут придумал очевидный алгоритм:
Для каждого i от 1 до (n — 1) выводим i и все разложения числа (n — i) на два слагаемых (таких (n — i) / 2).
И, соответственно, реализация:

#include <iostream>

typedef unsigned int uint;

void f( uint n, std::ostream &stream );

int main()
{
    std::cout << "Введите натуральное значение (>=3): ";

    uint N;
    std::cin >> N;

    if ( N >= 3 )
    {
        std::cout << "Число " << N << " можно представить в виде суммы: " << std::endl;
        f( N, std::cout );
    }
    else
    {
        std::cout << "Введено неверное значение" << std::endl;
    }

    return 0;
}

void f( uint n, std::ostream &stream )
{
    for ( uint i = 1; i < n - 1; i++ )
    {
        for ( uint j = 1; j < ( (n - i) / 2 ) + 1; j++ )
        {
            stream << i << " " << n - i - j << " " << j << std::endl;
        }
    }
}

Но алгоритм медленный ( O(f) = (n — 2) * (n / 2) ), ведь так?

P.S.:

Для справки: натуральное число — это целое неотрицательное число, начиная с 0.

Разве натуральные не начинаются с 1?

Нуль (пустое множество) иногда относят к натуральным числам. Но в нашем случае учитывать нулевое слагаемое нет никакого смысла.

Но в нашем случае учитывать нулевое слагаемое нет никакого смысла.

Не согласен.

Во-первых, если 0 не учитывать, то разложить на три слагаемых натуральные числа 1 и 2 не получится.

Во-вторых, 0, как слагаемое, даёт больше вариантов разложения числа. Например, для 3 получаем:

1) 3 = 0 + 0 + 3
2) 3 = 0 + 1 + 2
3) 3 = 1 + 1 + 1

А в противном случае — всего один вариант.

В-третьих, читаем в Википедии вводную часть статьи (до Содержания). Если уж формулировать задачу совсем чётко, давайте говорить не о натуральных числах, а о числах расширенного натурального ряда, имея ввиду и исходное число, и полученные слагаемые.

А вообще-то я не понимаю, откуда возникла дискуссия. В формулировке задачи я оговорил что подразумевается под «натуральным числом».

UPD: Для буквоедов, внёс уточнение в условие задачи.

porshe, нестыковочка:

Введите натуральное значение (>=3): 5
Число 5 можно представить в виде суммы:
1 3 1
1 2 2
2 2 1
3 1 1

Первый и четвёртый варианты, а также второй и третий отличаются только порядком слагаемых.
И вариантов с нулевым слагаемым нет.

Я думаю это может быть представлено так:

#include <iostream>

int main()
{
    std::cout << "Enter a natural number: ";

    unsigned int N;

    std::cin >> N;

    std::cout << "The number " << N << " can be present by next three summands:\n";

    for (int i = 0; i < (N / 3) + 1; i++) {

        for (int j = i; j < ((N - i) / 2) + 1; j++) {

            std::cout << i << " " << j << " " << N - i - j << std::endl;

        }            
    }

    std::cin.get();
    std::cin.get();

    return 0;
}

На мой взгляд у beginner получилось хорошее решение.

Единственно, хотелось бы уточнить два момента:

1. Переменные цикла привести к тому же типу, что и исходное число. Дабы избежать сравнений знакового и беззнакового числа.
2. Убрать вычисления из условия завершения цикла. Хотя современный оптимизирующий компилятор, скорее всего, сам с этим справится. Но всё же.

Итого:

#include <iostream>

int main()
{
    std::cout << "Enter a natural number: ";

    unsigned int N;

    std::cin >> N;

    std::cout << "The number " << N << " can be present by next three summands:\n";

    unsigned int limit_1_summand = (N / 3) + 1;
    unsigned int limit_2_summand;

    for (unsigned int i = 0; i < limit_1_summand; i++) {

        limit_2_summand = ((N - i) / 2) + 1;

        for (unsigned int j = i; j < limit_2_summand; j++) {

            std::cout << i << " " << j << " " << N - i - j << std::endl;

        }
    }

    std::cin.get();
    std::cin.get();

    return 0;
}