首页 > 试题广场 >

Flipping Pancake

[编程题]Flipping Pancake

热度指数：612 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

We start with a stack n of pancakes of distinct sizes. The problem is to convert the stack to one in which the pancakes are in size order with the smallest on the top and the largest on the bottom. To do this, we are allowed to flip the top k pancakes over as a unit (so the k-th pancake is now on top and the pancake previously on top is now in the k-th position).

For example: This problem is to write a program, which finds a sequence of at most (2n - 3) flips, which converts a given stack of pancakes to a sorted stack.

输入描述:

Each line of the input gives a separate data set as a sequence of numbers separated by spaces. The first number on each line gives the number, N, of pancakes in the data set. The input ends when N is 0 (zero) with no other data on the line. The remainder of the data set are the numbers 1 through N in some order giving the initial pancake stack.

The numbers indicate the relative sizes of the pancakes. N will be, at most, 30.

输出描述:

For each data set, the output is a single-space separated sequence of numbers on a line. The first number on each line, K, gives the number of flips required to sort the pancakes. This number is followed by a sequence of K numbers, each of which gives the number of pancakes to flip on the corresponding sorting step. There may be several correct solutions for some datasets. For instance 3 3 2 3 is also a solution to the first problem below.

示例1

输入

2 2 1
6 2 5 6 1 3 4
0

输出

1 2
4 3 6 4 2

备注:

http://en.wikipedia.org/wiki/Pancake_sorting

关于Pancake sorting的一种简单情况。就是有种方法可以保证至多2n-3次完成。

类似于选择排序：
先找出n各数字种最大的一个数n，假设所在位置为sn，那么先翻转前sn个数字f(sn)，
使得n在最顶部，之后再翻转前n个元素f(n)，这样一来n就到了最底部。就是两次翻转。
之后再选择第二大的假设为n-1，位置在sn-1，那么先翻转前sn-1个数字f(sn-1)，使得n-1在最
顶部，之后再翻转前n-1个元素f(n-1)，这样一来n-1就到了倒数第二个。也是两次翻转。
注意：每次对于第x大的元素要判断它是不是在倒是第x个位置上，若在就不用翻转这个数字了。
一直进行n-2次，最多2n-4次翻转。剩下上面三个最小的1,2其它的都排序了。

分成2种情况，顶多1次搞定：
12：已经有序，不用翻转。
21：一次，f(2)

算法知识视频讲解

用户抉择

#include <stdio.h>

void Flip(int a[],int i)
{
    int t,j;
    for(j=1;j<i;j++,i--)
    {
        t=a[j];
        a[j]=a[i];
        a[i]=t;
    }
}

int main()
{
    int n,i,max,c;
    while(scanf("%d",&n)!=EOF&&n!=0)
    {
        int a[n+1],b[2*n-3+1];
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        max=n;
        c=0;
        while(max>1)
        {
            for(i=1;i<=n;i++)
                if(a[i]==max) break;
            if(i==max) max--;
            else if(i==1)
            {
                Flip(a,max);
                b[c++]=max;
                max--;
            }
            else{
                Flip(a,i);
                b[c++]=i;
                Flip(a,max);
                b[c++]=max;
                max--;
            }
        }
        printf("%d ",c);
        for(i=0;i<c-1;i++) printf("%d ",b[i]);
        printf("%d\n",b[c-1]);
    }
    return 0;
}

发表于 2021-03-14 22:36:36 回复(0)

娱乐人生

原理在备注里说得很明白，稍微理一理就好了。

第一步：在数组中找到数a（a初始值为最大值）；

第二步：若a已在对应位置，则a--，返回第一步，

若a在第一个位置上，执行第四步，

若a不在对应位置，也不在第一个位置上，执行第三步；

第三步：将数组的第一个元素到a所在位置的元素翻转（比如a位于第三个元素，则将第一个到第三个元素翻转），执行第四步；

第四步：将第一个元素到第a个元素翻转，a--，返回第一步；

代码看着挺长，其实主要是括号占了很多格子。

#include<iostream>
using namespace std;

void Flip(int a[], int i)//翻转函数；
{
    int tmp = 0;
    for(int j = 1; j < i; j++, i--)
    {
        tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

int main()
{
    int N;
    while(cin >> N)
    {
        if(N == 0)
            break;
        int a[31] = {0};//待处理数组；
        for(int i = 1; i <= N; i++)//从下标1开始存，便于后面操作；
            cin >> a[i];
        int count = 0;//记录翻了多少次；
        int flips[57] = {0};//记录每次从哪翻的；
        int max = N;//max保存当前要找的数；
        while(max > 1)
        {
            int i = 1;
            for(; i <= N; i++)
                if(a[i] == max)
                    break;
            if(i == max)
            {
                max--;
                continue;
            }
            else if(i == 1)
            {
                Flip(a, max);
                flips[count++] = max;
                max--;
                continue;
            }
            else
            {
                Flip(a, i);
                flips[count++] = i;
                Flip(a, max);
                flips[count++] = max;
                max--;
            }
        }
        cout << count << " ";
        for(int i = 0; i < count - 1; i++)
            cout << flips[i] << " ";
        cout << flips[count - 1] << endl;
    }
    return 0;
}

编辑于 2021-02-25 17:15:34 回复(0)

給迩灬微笑

//按照备注的过程写的代码

#include<bits/stdc++.h>

using namespace std;
int List[31];
int ans[100];
int ansSize;
int n;
bool judge(){
   for(int i=1;i<=n;i++){
       if(List[i]!=i){
           return false;
       }
   }
   return true;
}
void swapList(int x){
   int tmp[31];
   for(int i=1;i<=x;i++) tmp[i]=List[i];
   for(int i=1;i<=x;i++) List[i]=tmp[x-i+1];
}
int main(){

   while(cin>>n && n!=0){
       ansSize=0;
       int num=0;
       for(int i=1;i<=n;i++){
           cin>>List[i];
       }
       while(!judge()){
           for(int i=1;i<=n;i++){
               if(List[i]==n-num && i !=n-num){
                   if(i!=1){
                       ans[ansSize++]=i;
                       swapList(i);
                   }
                   if(n-num!=1){
                       ans[ansSize++]=n-num;
                        swapList(n-num);
                   }
                   break;
               }
           }
           num++;
       }
       cout<<ansSize;
       for(int i=0;i<ansSize;i++){
           cout<<" "<<ans[i];
       }
       cout<<endl;

   }
}

发表于 2020-02-28 16:11:43 回复(0)

C/C++

纠结offer的菜狗

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

int data[31];

void Flip(int n)
{
    for(int i = 1;i <= n / 2;i++)
    {
        swap(data[i],data[n + 1 - i]);
    }
}

int main()
{
    int n;
    while(cin >> n && n)
    {
        for(int i = 1;i <= n;i++)
        {
            cin >> data[i];
        }
        int count = 0;
        vector<int> t;
        while(n != 1)
        {
            int max_num = -1,index;
            for(int i = 1;i <= n;i++)
            {
                if(max_num < data[i]) max_num = data[i],index = i;
            }
            if(index != max_num)
            {
                if(max_num != data[1])
                {
                    count++;
                    t.push_back(index);
                }
                Flip(index);
                count++;
                t.push_back(n);
                Flip(n);
            }
            n--;
        }
        cout << count << " ";
        for(int i = 0;i < count;i++) cout << t[i] << " ";
        cout << endl;
    }
    return 0;
}

发表于 2021-02-27 20:41:58 回复(0)

时光河里的鱼

总体思路同备注

#include<bits/stdc++.h>

using namespace std;

vector<int> ans;
vector<int> nums;

void Flip(vector<int> &nums){
bool flag = true;
while(flag){
flag = false;
int maxn = 0;
int index = 0;
for(int i=nums.size()-1; i>=1; i--){
if(nums[i]!=i&&nums[i]>maxn){
maxn = nums[i];
index = i;
}
}
if(index!=1){
ans.push_back(index);
reverse(nums.begin()+1, nums.begin()+index+1);
}
ans.push_back(maxn);
reverse(nums.begin()+1, nums.begin()+maxn+1);
for(int i=1; i<nums.size(); i++){
if(nums[i]!=i){
flag = true;
}
}
}
}

int main(){
int n;
while(scanf("%d", &n)!=EOF){
nums.clear();
ans.clear();
if(n==0) break;
nums.push_back(0);
for(int i=0; i<n; i++){
int temp;
scanf("%d", &temp);
nums.push_back(temp);
}
Flip(nums);
printf("%d ", ans.size());
for(int i=0; i<ans.size(); i++){
if(i!=ans.size()-1)
printf("%d ", ans[i]);
else printf("%d\n", ans[i]);
}
}
return 0;
}

发表于 2021-02-02 10:17:28 回复(0)

夏天的熊_

/*
参照备注很容易就能理解
*/
vector<int> Flip(int*a,int n){
    //将大小为n的数组反转，使得大的在小的下面
    vector<int>ans;
    //每次找出最大的元素，然后将其（包括自身）前面的元素反转，然后从头到尾继续反转
    int tmp=n;
    while(tmp>0){
        //选出当前最大的元素

        int index=max_element(a,a+tmp)-a;
        if(index==tmp-1){
            //无需反转
            tmp--;
            continue;
        }
        if(index!=0){
            //反转前index个元素
            reverse(a,a+index+1);
            ans.push_back(index+1);
        }
        //再反转前tmp个元素
        reverse(a,a+tmp);
        ans.push_back(tmp);
        tmp--;
    }
    return ans;
}
int main(){
    int n;

    while(cin>>n){
        if(n==0)break;
        int i;
        int a[n];
        for(i=0;i<n;i++){
            cin>>a[i];
        }
        vector<int>ans=Flip(a,n);
        cout<<ans.size();
        for(i=0;i<ans.size();i++){
            cout<<" "<<ans[i];
        }
        cout<<endl;
    }
    return 0;
}

发表于 2020-04-17 19:48:38 回复(0)