翻转烙饼排序问题

翻转烙饼排序问题

翻转烙饼排序问题：采用每次只能翻转最上面的若干个数字的方法将n个数排序。要求总的翻转次数最少。

程序：

#include

#include

void cakeSort(int cake[],int size);//排序函数，并输出排序方法

void reverse(int array[],int size);//数组逆序

int biggestFind(int array[],int size);//查找数组最大元素并输出位置

int step = 0;

int main(void)

{

system("title megamirurutia--翻饼问题 ");

int cake[100],n,i;

printf("请输入要排序的数字个数n:");

scanf("%d",&n);

printf("请输入需要排序的序列：");

for(i=0;i

{scanf("%d",&cake[i]);}

int size = n;

cakeSort(cake, size);

printf("共需要%d步翻转\n",step);

printf("排序结果：");

for(i = 0; i < size; i++) {

printf("%d", cake[i]);

}

printf("\n");

return 0;

}

void cakeSort(int cake[],int size)

{

int maxLocation;

if(size > 1) {

maxLocation = biggestFind(cake, size);//获取最大值位置

if(maxLocation == 0) { //最大值在开头，则reverse整个数组

reverse(cake, size);

step++;

printf("第%d步：翻转上面的%d个饼\n", step, size);

cakeSort(cake, size - 1);

} else if(maxLocation == size-1) {//最大值在末尾，则对前面的数字进行排序

cakeSort(cake, size - 1);

} else { //最大值在中间某位置，则将开始到最大值位置处的子数组进行reverse，使最大值放在开头处

reverse(cake, maxLocation + 1);

step++;

printf("第%d步：翻转上面的%d个饼\n", step, maxLocation+1);

reverse(cake, size);

step++;

printf("第%d步：翻转上面的%d个饼\n", step, size);

cakeSort(cake, size - 1);

}

}

}

//功能：返回数组中最大值所在的位置

#include

int biggestFind(int array[],int size)

{

int location, max;//存储最大值所在位置和最大值

int i;

if(size <= 0)

{

printf("Null array!\n");

return -1;

}

max = array[0];

for(i = 0, location = 0; i < size; i++)

{

if(array[i] > max)

{

max = array[i];

location = i;

}

}

return location;

}

//将数组逆置

void reverse(int array[],int size)

{

int i, temp;

for(i = 0; i < size/2; i++) {

temp = array[size - 1 - i];

array[size - 1 - i] = array[i];

array[i] = temp;

}

}