ホームページ > バックエンド開発 > C++ > パンケーキの並べ替え用のCプログラム?

パンケーキの並べ替え用のCプログラム?

WBOY
リリース: 2023-08-31 17:21:04
転載
1097 人が閲覧しました

パンケーキの並べ替え用のCプログラム?

この C プログラムは、整数の配列に対するパンケーキ ソートを実装します。

パンケーキ ソートは、シーケンス内の特定のプレフィックスの要素を反転することだけが許可される操作であるソート問題の変形です。

パンケーキ ソートは、シーケンス内の特定のプレフィックスの要素を反転することだけが許可される操作であるソート問題の変形です。 p>

パンケーキソートは、スパチュラをパンケーキスタックに挿入することによって、順序付けられていないパンケーキスタックをサイズ順にソートする数学的問題を指す口語用語です。すべてのパンケーキをひっくり返すための任意のポイントと使用方法上にはパンケーキが付いています。パンケーキの数は、指定された数のパンケーキに必要な反転の最小数です

Input:5,3,2,1,4
Output:1 2 3 4 5
ログイン後にコピー

説明

これは並べ替え問題の変形であり、唯一許可される操作は、その中の何かを反転することです。 sequence 接頭辞付きの要素。可能な限り少ない比較で並べ替えを試みる従来の並べ替えアルゴリズムとは異なり、目標は、可能な限り少ない反転でシーケンスを並べ替えることです。この問題のバリエーションは、焦げたパンケーキに関係しており、どのパンケーキにも焦げた面があり、すべてのパンケーキの焦げた面が底部になる必要があります。

#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 中国語 Web サイトの他の関連記事を参照してください。

ソース:tutorialspoint.com
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート