Programme C pour le tri des crêpes ?

Ce programme C implémente le tri pancake sur un tableau d'entiers.

Le tri Pancake est une variante du problème de tri où la seule opération autorisée est d'inverser les éléments de certains préfixes dans la séquence.

Le tri Pancake est une variante du problème de tri où la seule opération autorisée est d'inverser les éléments de certains préfixes dans la séquence. p>

Tri des crêpes est un terme familier faisant référence au problème mathématique du tri d'une pile non ordonnée de crêpes par ordre de taille, où une spatule peut être insérée à n'importe quel endroit de la pile et utilisée pour toutes les retourner. Il y a des crêpes dessus dessus des crêpes. Le nombre de crêpes est le nombre minimum de retournements requis pour un nombre donné de crêpes

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

Explication

Il s'agit d'une variante du problème de tri où la seule opération autorisée est d'inverser les éléments d'un certain préfixe dans la séquence. Contrairement aux algorithmes de tri traditionnels qui tentent de trier avec le moins de comparaisons possible, l’objectif est de trier une séquence avec le moins d’inversions possible. Une variante de ce problème concerne les crêpes brûlées, où chaque crêpe a un côté brûlé, et toutes les crêpes doivent finir avec le côté brûlé au fond.

Exemple

#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);
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!