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