九度OJ 1146:Flipping Pancake(翻饼子) (递归、游戏)
时间限制:1 秒
内存限制:32 兆
特殊判题:是
提交:265
解决:116
- 题目描述:
-
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.
- 样例输入:
-
3 1 3 2
5 4 3 2 5 1
0
- 样例输出:
-
3 2 3 2
3 3 4 5
思路:
著名的翻饼子游戏。要求最后状态是小饼在大饼的上面,求翻得次数。最多需要翻2n-3次。
这种题要用逆向思维以及递归方法来分析,考察最终状态及前一步,逐步往前考察,从而发现游戏思路。
代码:
#include <stdio.h> #define N 30 int n, k;
int a[N+1], r[N+1], step[2*N+1]; void swap(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
} void print(int *x)
{
int j;
for (j=1; j<n; j++)
printf("%d ", x[j]);
printf("%d\n", x[j]);
} void flip(int i)
{
int j;
for (j=1; j<=i/2; j++)
{
swap(&a[j], &a[i-j+1]);
r[a[j]] = j;
r[a[i-j+1]] = i-j+1;
}
step[k++] = i;
//printf("=====");
//print(a);
//print(r);
} int main(void)
{
int i; while (scanf("%d", &n) != EOF && n)
{
for(i=1; i<=n; i++)
{
scanf("%d", &a[i]);
r[a[i]] = i;
} k = 0;
for (i=n; i>=2; i--)
{
if (r[i] != i)
{
if (r[i] != 1)
flip(r[i]);
flip(i);
}
} printf("%d ", k);
for (i=0; i<k-1; i++)
printf("%d ", step[i]);
printf("%d\n", step[i]); } return 0;
}
/**************************************************************
Problem: 1146
User: liangrx06
Language: C
Result: Accepted
Time:0 ms
Memory:912 kb
****************************************************************/
最新文章
- RabbitMq应用一的补充(RabbitMQ的应用场景)
- 从零自学Hadoop(19):HBase介绍及安装
- iOS-Objective-C基础
- [转]caffe的配置过程
- jQuery中的checkbox问题
- WWDC2016-session401-CodeSign大改版
- JavaSE复习_12 Socket网络编程
- Winform主窗体的设置
- 入门1:PHP的优点
- Visual C++内存泄露检测—VLD工具使用说明
- div模拟滚动条
- Javascript多线程引擎(二)
- 模拟jquery底层链式编程
- 深入理解Python的字符编码
- Spring--ApplicationContext
- PHP接口的思考
- Python - 判断list是否为空
- django 初始命令
- 详解webpack中的hash、chunkhash、contenthash区别
- SpringBoot cookie工具类
热门文章
- httperf+autobench测试web应用
- 审查php.ini自动分析程序
- Vagrant + PHPStorm 使用 Xdebug
- 【python】redis基本命令和基本用法详解
- C#调用C++Dll封装时遇到的一系列问题【转】
- java基础篇5之泛型
- 2017.2.9 深入浅出MyBatis技术原理与实践-第八章 MyBatis-Spring(二)-----配置文件详解
- browsersync按照官网,然后本地配置后,动态监听时不起作用
- 获取服务器classes根路径
- QTreeWidget里嵌套表格QTableView