自然数の分割 in C++ DouKaku?

自然数の分割

自然数nとm(n>=m>0)が与えられたとき，nをm個の非負の整数の和で表すやり方を全て出力してください．
その際，和の組(x_1, ..., x_m)は大きい順に出力してください．
ここでm = 3の時の「(a, b, c)が(A, B, C)より大きい」とは
(a > A)
(a == A) かつ (b > B)
(a == A) かつ (b == B) かつ (c > C)
のいずれかが成り立つとき(つまりは辞書的順序)とします．

例:n = 5, m = 3が与えられたときは
5, 0, 0,
4, 1, 0,
4, 0, 1,
3, 2, 0,
3, 1, 1,
...
0, 1, 4,
0, 0, 5,
を出力する．

post comment

Posted feedbacks - C++

普通に再帰で。

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cassert>

void output_impl(
    std::vector<size_t>& v,
    std::vector<size_t>::iterator it,
    size_t n)
{
    if (it == v.end())
    {
        std::copy(v.begin(), v.end(), std::ostream_iterator<size_t>(std::cout, ", "));

        std::cout << n << std::endl;

        return;
    }

    for (*it = n; ; --(*it))
    {
        output_impl(v, it + 1, n - *it);

        if (*it == 0)
        {
            break;
        }
    }
}

void output(size_t n, size_t m)
{
    assert(n >= m); assert(m > 0);

    std::vector<size_t> v(m - 1);

    output_impl(v, v.begin(), n);
}

int main()
{
    output(5, 3);
}

DouKaku?

自然数の分割

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq