এই সি প্রোগ্রামটি পূর্ণসংখ্যার অ্যারের উপর প্যানকেক সাজানোর প্রয়োগ করে।
প্যানকেক বাছাই হল বাছাই সমস্যার একটি ভিন্নতা যেখানে একমাত্র অনুমোদিত অপারেশন হল অনুক্রমের কিছু উপসর্গের উপাদানগুলিকে বিপরীত করা।
প্যানকেক সাজানো প্যানকেকগুলির একটি বিশৃঙ্খল স্ট্যাকের আকারের ক্রমানুসারে সাজানোর গাণিতিক সমস্যার জন্য একটি কথ্য শব্দ যখন স্ট্যাকের যে কোনও স্থানে একটি স্প্যাটুলা ঢোকানো যেতে পারে এবং এর উপরে সমস্ত প্যানকেকগুলি উল্টাতে ব্যবহৃত হয়। একটি প্যানকেক সংখ্যা হল একটি প্রদত্ত সংখ্যক প্যানকেকের জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক ফ্লিপস
Input:5,3,2,1,4 Output:1 2 3 4 5
ব্যাখ্যা
এটি বাছাই সমস্যার একটি ভিন্নতা যেখানে একমাত্র অনুমোদিত অপারেশন হল অনুক্রমের কিছু উপসর্গের উপাদানগুলিকে বিপরীত করা। একটি প্রথাগত বাছাই অ্যালগরিদমের বিপরীতে, যা সম্ভব কম তুলনা দিয়ে সাজানোর চেষ্টা করে, লক্ষ্য হল যতটা সম্ভব কম বিপরীতে ক্রম সাজানো। সমস্যাটির একটি রূপটি পোড়া প্যানকেকগুলির সাথে সম্পর্কিত, যেখানে প্রতিটি প্যানকেকের একটি পোড়া দিক থাকে এবং সমস্ত প্যানকেকগুলি অবশ্যই নীচের দিকে পোড়া পাশ দিয়ে শেষ করতে হবে৷
উদাহরণ
#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\n", moves);
} 