팬케이크 분류를 위한 C 프로그램?

이 C 프로그램은 정수 배열에 대한 팬케이크 정렬을 구현합니다.

팬케이크 정렬은 시퀀스에서 특정 접두사의 요소를 반대로 하는 작업만 허용되는 정렬 문제의 변형입니다.

팬케이크 정렬은 시퀀스에서 특정 접두사의 요소를 반대로 하는 작업만 허용되는 정렬 문제의 변형입니다. p>

팬케이크 정렬은 정렬되지 않은 팬케이크 더미를 크기 순서대로 정렬하는 수학적 문제를 가리키는 구어체 용어로, 스택의 어느 위치에나 주걱을 삽입하여 모두 뒤집을 수 있습니다. 팬케이크가 있습니다. 팬케이크의 꼭대기. 팬케이크 수는 주어진 팬케이크 수에 필요한 최소 뒤집기 횟수입니다.

Input:5,3,2,1,4
Output:1 2 3 4 5

Explanation

이것은 허용되는 유일한 작업이 시퀀스에서 특정 접두사의 요소를 바꾸는 것인 정렬 문제의 변형입니다. 가능한 한 적은 수의 비교를 통해 정렬하려고 하는 기존 정렬 알고리즘과 달리 목표는 가능한 한 적은 수의 반전을 사용하여 시퀀스를 정렬하는 것입니다. 이 문제의 변형은 탄 팬케이크와 관련이 있습니다. 모든 팬케이크에는 탄 면이 있고, 모든 팬케이크는 탄 면이 바닥에 오게 되어야 합니다.

예

#include <iostream>
using namespace std;
void do_flip(int *, int, int);
int pancake_sort(int *list, unsigned int length) {
   if (length < 2)
      return 0;
   int i, a, max_num_pos, moves;
   moves = 0;
   for (i = length;i > 1;i--) {
      max_num_pos = 0;
      for (a = 0;a < i;a++){
         if (list[a] > list[max_num_pos])
            max_num_pos = a;
      }
      if (max_num_pos == i - 1)
         continue;
      if (max_num_pos){
         moves++;
         do_flip(list, length, max_num_pos + 1);
      }
      do_flip(list, length, i);
   }
   return moves;
}
void do_flip(int *list, int length, int num) {
   int swap;
   int i = 0;
   for (i=0;i < --num;i++) {
      swap = list[i];
      list[i] = list[num];
      list[num] = swap;
   }
}
int main(int argc, char **argv) {
   int arr[]={5,3,2,1,4};
   int n=5;
   int moves=pancake_sort(arr, n);
   for (int i = 0;i < n;i++) {
      printf("%d ", arr[i]);
   }
   printf(" - with a total of %d moves</p><p>", moves);
}

위 내용은 팬케이크 분류를 위한 C 프로그램?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!