> 백엔드 개발 > C++ > 본문

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

WBOY
풀어 주다: 2023-08-31 17:21:04
앞으로
1054명이 탐색했습니다.

팬케이크 분류를 위한 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:tutorialspoint.com
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
최신 이슈
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!