在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); 
     } 
    } 
} 

注意，我打電話之前檢查以避免單個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; 
}