c++ - 在 C++ 中拆分一个数字

Question

我必须编写一个执行以下操作的程序:输入应为 n (n>1)。如果 n = 5，则应发生以下情况:

1 1 1 1 1
1 1 1 2 
1 1 2
1 1 3
1 4
2 3

如您所见，没有两条相同的线，并且顺序是严格的 - 从最低的数字到最高的。

我有一个代码，在同样的情况下，它输出这个:

1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1

如您所见，顺序颠倒了，这是意料之外的。我该如何解决这个问题？

代码如下:

#include <iostream>
#include <stdio.h>
using namespace std;

unsigned *mp;

void print(unsigned length)
{
    unsigned i;
    for (i = 1; i < length; i++) printf("%u ", mp[i]);
    printf("%u\n", mp[length]);
}

void devNum(unsigned n, unsigned pos)
{
    unsigned k;
    for (k = 1; k <= n; k++)
    {
        if (n != k)
        {
            mp[pos] = k;
            if (mp[pos] <= mp[pos - 1])
            {
                devNum(n - k, pos + 1);
            }
        }
        else
        {
            mp[pos] = k;
            if (pos > 1 && mp[pos] <= mp[pos - 1]) print(pos);
        }
    }
}

int main(void)
{
    unsigned n;
    cin >> n;
    mp = new unsigned[n + 1];
    mp[0] = n + 1;
    devNum(n, 1);
    delete[] mp;
    return 0;
}

Answer 1

编辑:我重写了 devNum() 和 main() 以适应新规范。请注意，我更改了 mp[0] 中填写的值。

void devNum(unsigned n, unsigned pos)
{
    for (mp[pos] = mp[pos-1]; mp[pos] <= n; ++mp[pos])
    {
        if(mp[pos] != n)
        {
            devNum(n - mp[pos], pos + 1);
        }
        else
        {
            if (pos > 1) print(pos);
        }
    }
}

int main(void)
{
    unsigned n;
    cin >> n;
    mp = new unsigned[n+1];
    mp[0] = 1;
    devNum(n, 1);
    delete [] mp;
    return 0;
}

---

(对于旧规范)

改变

void devNum(unsigned n, unsigned pos)
{
    unsigned k;
    for (k = n; k >= 1; k--)
    /* ... */

进入

void devNum(unsigned n, unsigned pos)
{
    unsigned k;
    for (k = 1; k <= n; k++)
    {
        if (n != k)
        {
            mp[pos] = k;
            if (mp[pos] <= mp[pos - 1])
            {
                devNum(n - k, pos + 1);
            }
        }
        else
        {
            mp[pos] = k;
            if (pos > 1 && mp[pos] <= mp[pos - 1]) print(pos);
        }
    }
}

请注意，我在调用 print() 之前检查了 pos > 1 以避免单个 5。

要移除固定的 MAX 限制，您可以在 main() 中动态分配 mp。即改变

const int MAX = 100;
unsigned mp[MAX + 1];

进入

unsigned *mp;

并将main()写成

int main(void)
{
    unsigned n;
    cin >> n;
    mp = new unsigned[n+1];
    mp[0] = n + 1;
    devNum(n, 1);
    delete [] mp;
    return 0;
}