パンケーキ問題のアルゴリズム
3,7,5,6,2,4,8,1 を昇順に並べ替える.
条件 先頭の部分列を逆さにする操作しか使わないこと.
例えば,1回目は 最大値8であるため3から8を入れ替える 8,4,2,6,5,7,3,1
その次に 全体を入れ替える 1,3,7,5,6,2,4,8
2回目は 次の最大値7であるから1から7を入れ替える. 7,3,1,5,6,2,4,8
その次に 全体を入れ替える 4,2,6,5,1,3,7,8
これを繰り返していくプログラムを考えているのですが,うまく出力されません
どなたかわかりますでしょうか.
/#include <stdio.h>
/#include <stdlib.h>
void swap(int a,int b)
{
int temp;
temp = a;
a = b;
b = temp;
return;
}
void print_array(int *list,int length){
for(int i=0;i<length;i++)
printf("%d ",list[i]);
printf("\n");
}
//回転
void do_flip(int *list,int length,int num){
for(int i=0;i<--num;i++)
swap(list[i],list[num]);
}
//パンケーキ食べたい
int pancake_sort(int *list,unsigned int length){
if(length<2)
return 0;
int i,j;
int max_num_pos;
int moves=0;//ソート回数
for(i=length;i>1;i--){
max_num_pos=0;
for(j=0;j<i;j++){
if(list[j]>list[max_num_pos])
max_num_pos=j;
}
if(max_num_pos==i-1)
continue;
if(max_num_pos){
moves++;
do_flip(list,length,max_num_pos+1);
}
moves++;
do_flip(list,length,i);
}
return moves;
}
int main(int argc, char **argv){
// 初期値 int moves[7]; int list[7]={3,7,5,6,2,4,8,1}; printf("Before\n"); print_array(list,8); moves[7] = pancake_sort(list,8); printf("After\n"); print_array(list,8);
}
出力
Before
3 7 5 6 2 4 8 0 8
After
3 7 5 6 2 4 8 0 8