가능한 모든 타워에 대한 알고리즘

Question

다음을 수행해야하는 C로 프로그램을 작성해야합니다. 주어진 n 0이 아닌 양수, 주어진 조각으로 지을 수있는 모든 타워를 인쇄합니다. . 하나의 규칙 만이 더 작은 스택에 더 큰 스택을 쌓을 수 없습니다 (그러나 동일한 크기의 스택을 2 개 쌓을 수 있음). 내가 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) 
     } 
    }  
}