排列的遞歸解決方案

嘿我有一個問題，我需要創建兩個函數，countWithPerms（）和ignorePerms（）這兩個函數必須是遞歸解決方案。 countWithPerms（）會計算實際排列的數量，而ignorePerms（）只會計算重複排列的數量。所以如果我將3傳入函數countWithPerms（）會發現3 =（2 + 1）=（1 + 2）=（1 + 1 + 2） 1），因此countWithPerms（3）爲3，因爲它計數3種方式來總結3.由於（1 + 2）和（2 + 1），countIgnorePerms（3）爲2，因此它們都不會計入countWithPerms中是正好寫在相反的順序。排列的遞歸解決方案

大量例子是countWithPerms（7）是63，而countIgnorePerms（7）爲14

我已經做countwithPerms，但我完全被卡住的countIgnorePerms。

int countWithPerms(int n) 
{ 
    if(n == 1) 
      return 0; 
    else 
      n--; 
    return (countWithPerms(n) + 1) + 
      (countWithPerms(n)); 
} 

    int ignorePerms(int sum, int xmin){ 
    if(sum == 1) 
      return 0; 

     else 
     for(int i=0; i<sum;i++){ 
      sum += sum-xmin; 
      2*ignorePerms(sum,xmin)+1; 

       return sum; 
    } 
}

來源

2014-02-17 Aaron B

你正在計數分區，而不是排列。 – aschepler

ignorePerms（）被稱爲[整數分區]（http://en.wikipedia.org/wiki/Partition_（number_theory））和countWithPerms（）被稱爲[整數組成]（http://en.wikipedia.org/維基/ Composition_（number_theory））。 – Ante

我想你是在排列的地方計算操作。 – Shravan40

不考慮排列計數的思想是隻考慮有序的解決方案。

要做到這一點，除了n還有什麼是附錄必須具有的最小值xmin。例如

3 = 1 + 2

將是確定（因爲2> = 1），但

3 = 2 + 1

是不能接受的（因爲1 < 2）。

所以這個想法是寫一個函數來回答「在第一個附錄中有多少個非減少項的和可以給出規定的total不小於min_addendum？」。

如果min_addendum是大於total顯然答案是0
如果total是1，那麼只有一個總和
否則第一個可能的總和total，那麼你應該算作總結
- min_addendum +其他不減少的總和，第一個不小於min_addendum合計total-min_addendum
- min_addendum+1 +其他非遞減項的和，所述第一不小於min_addendum+1共計total-min_addendum-1
- min_addendum+2 +其他非遞減項的和，所述第一不小於min_addendum+2共計total-min_addendum-2
- ...

來源

2014-02-17 17:48:37 6502

xmin需要設置爲什麼？ N-1？ –

最初，您將它作爲0傳遞（因爲您可以接受任何附錄作爲第一個），而在遞歸調用中，您需要傳遞剛剛添加的值（以確保序列是有序的）。 – 6502

嗯，Im仍然有點困惑，所以我在n被傳回後傳入，但函數知道n的劑量必須是<然後計算n –

排列的遞歸解決方案

回答

相關問題