算法爲每個可能的塔建

Question

我需要在C中創建一個程序，應該做以下幾點： 鑑於ñ非零，正數，我打印出所有的塔，可以由給定的片段。只有一個規則 - 不能堆疊較大（但可以堆疊兩個相同的大小）。所以，如果我給出的3個數字，1 2 3，可能性是：

3, 2, 1 
3, 1 
3, 2 
3 
2, 1 
2 
1 

給出2 2 3，它的：

3, 2, 2 
3, 2 
3 
2, 2 
2 

誰能幫助我，好嗎？我嘗試着研究遞歸算法，進入河內算法和相關的算法，但我無法想到這一點。

Answer 1

從大小的降序開始排序，這意味着最大的作品排在第一位。現在考慮每個相同片段的序列。

1. 假設我們目前正在查看尺寸爲a的件。把所有這些東西放到塔上。

2. 繼續前進到下一個最大尺寸（尺寸爲b的零件，例如b < a），並從這一點遞歸構建所有可能的塔。

3. 塔上是否至少有一塊尺寸爲a？如果是這樣，刪除一個塊大小的a，並返回到步驟2。

下面的程序實現該算法在ANSI C.用戶輸入命令行上的碎片。我們將qsort與比較函數reverse一起按降序對輸入進行排序，然後我們調用遞歸函數print_tower。

#include <stdlib.h> 
#include <stdio.h> 

/* Assumes that data is sorted in descending order. */ 
void print_tower(int *data, int n, int pos, int *result, int len) { 
    int seek, i; 
    /* If we're out of data, print the result pieces. */ 
    if (pos == n) { 
    if (len > 0) { 
     printf("%d", result[0]); 
     for (i = 1; i < len; ++i) { 
     printf(", %d", result[i]); 
     } 
     printf("\n"); 
    } 
    return; 
    } 
    /* Scan the sequence of identical elements. */ 
    seek = pos; 
    while (seek < n && data[seek] == data[pos]) { 
    result[len++] = data[seek++]; 
    } 
    /* Recursively print the tower and shorten the sequence. */ 
    while (pos++ <= seek) { 
    print_tower(data, n, seek, result, len--); 
    } 
} 

/* Comparison function to sort integers in descending order. */ 
int reverse(const void *p, const void *q) { 
    int a = *(int *)p, b = *(int *)q; 
    return b - a; 
} 

int main(int argc, char **args) { 
    int i, n = argc-1, 
     *data = (int *) malloc(n*sizeof(int)), 
     *result = (int *) malloc(n*sizeof(int)); 
    for (i = 0; i < n; ++i) { 
    data[i] = atoi(args[i+1]); 
    } 
    qsort(data, n, sizeof(int), reverse); 
    print_tower(data, n, 0, result, 0); 
    return 0; 
} 

Answer 2

就我的理解，問題可以通過排序來簡化。如果首先對數組進行排序，則問題將減少爲輸入的所有子數組的輸出。如果n表示輸入中元素的數量，則會導致2^n可能的子數組遞歸地枚舉。

但是，此解決方案要求輸入中的大小相等的塊被認爲是不同的。如果大小相等的部分被認爲是相等的，那麼應該對輸入進行排序，然後轉換成對(s_i,m_i)其中s_i表示i-第一塊的大小，而m_i表示其多重性。然後，使用僞代碼中的以下算法可以生成可能的解決方案。

type piece = struct (integer, integer) 

function enumerate(a array of piece) 
{ 
    if (a is empty) 
    { 
     end current solution 
    } 
    else 
    { 
     let f = first element of a 
     for each i <= multiplicity of f 
     { 
      output size of f i times 
      enumerate (a with first element removed) 
     } 
    }  
}