Soalan tempahan pancake?

Di sini kita akan melihat satu lagi masalah pengisihan yang dipanggil pengisihan pancake. Soalannya mudah sahaja. Kami mempunyai array. Kita perlu menyusun ini. Tetapi kita hanya boleh menggunakan satu operasi yang dipanggil rev(arr, i). Ini akan membalikkan elemen arr dari 0 ke kedudukan ke-i.

Ideanya seperti pemilihan jenis. Kami berulang kali meletakkan elemen terbesar di hujung untuk mengurangkan saiz tatasusunan. Mari lihat algoritma untuk memahami idea ini.

Algoritma

pancakeSort(arr, n)

Begin
   size := n
   while size > 1, do
      index := index of max element in arr from [0 to size – 1]
      rev(arr, index)
      rev(arr, size - 1)
      size := size - 1
   done
End

Contoh

#include<iostream>
using namespace std;
void rev(int arr[], int i) {
   int temp, st = 0;
   while (st < i) {
      temp = arr[st];
      arr[st] = arr[i];
      arr[i] = temp;
      st++;
      i--;
   }
}
int maxIndex(int arr[], int n) {
   int index, i;
   for (index = 0, i = 0; i < n; ++i){
      if (arr[i] > arr[index]) {
         index = i;
      }
   }
   return index;
}
int pancakeSort(int arr[], int n) {
   for (int size = n; size > 1; size--) {
      int index = maxIndex(arr, size);
      if (index != size-1) {
         rev(arr, index);
         rev(arr, size-1);
      }
   }
}
int main() {
   int arr[] = {54, 85, 52, 25, 98, 75, 25, 11, 68};
   int n = sizeof(arr)/sizeof(arr[0]);
   pancakeSort(arr, n);
   cout << "Sorted array: ";
   for (int i = 0; i < n; ++i)
   cout << arr[i] << " ";
}

Output

Sorted array: 11 25 25 52 54 68 75 85 98

Atas ialah kandungan terperinci Soalan tempahan pancake?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!