Chinaunix首页 | 论坛 | 博客
  • 博客访问: 418780
  • 博文数量: 63
  • 博客积分: 1175
  • 博客等级: 少尉
  • 技术积分: 1204
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-19 11:33
文章分类
文章存档

2015年(1)

2014年(3)

2013年(7)

2012年(52)

分类:

2012-09-10 20:21:02

原文地址:烧饼问题 作者:wwwzyf

随便翻了翻《编程之美》,看到了一个算法描述,也就是以前听说过的翻饼问题,描述如下:服务员一只手托着盘
子,另外一只手也没闲着,他想用另外一直手翻转这饼,最终使得饼按照大小顺序排列,小的在上面,大的在下面
,请设计算法实现:

一开始我想都没想,唉,最简单的方法不就是冒泡排序么。后来经过别人提醒,题目有要求,意思就是不能从中间
抽取,所以,冒泡根本不适用。额,尴尬了。

然后就想着想着,还是用代码写出来再说吧,好了。代码如下:

/*
 * Copyright (c) 2010-~ zhouyongfei
 *
 * The source code is released for free distribution under the terms of the GNU General Public License
 *
 *
 * Author: alen Chou
 * Created Time: 2010年07月28日 星期三 19时47分36秒
 * File Name: sort5.c
 * Description:
 * 这个文章解决的一个算法问题,问题描述如下:服务员端了一碟烧饼,
 * 大小不一,先只能通过另一只手来翻转,使其按大小顺序排序。其中不能抽出任何一张饼
 * 只能对其进行翻转。
 *
 */


#include <stdio.h>
#include <stdlib.h>
/**
 *将一个数组逆置
 * */

void reversal(int r[],int start,int end)
{
    int i,j;
    int tmp;
    for(i = start,j = end;i-1 != j && j+1 != i-1;i++,j--){
        tmp = r[i];
        r[i] = r[j];
        r[j] = tmp;
    }
}

void sort(int r[],int length)
{
    int i,tmp = r[0];
    int maxIndex = 0;
    int tmplength = length;

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

        if(r[i] >= tmp){//记录当前需要排序的最大下标

            maxIndex = i;
            tmp = r[i];
        }

        if(i+1 == tmplength){//除了排好序的,对剩余的进行最后处理

            reversal(r,0,maxIndex);
            reversal(r,0,tmplength-1);
            //下面是初始化需要继续排序的剩余的元素

            tmp = 0;
            maxIndex = 0;
            i = -1; //这里为什么要令i=-1呢?因为,if执行完成后i++一次,之前忽略了这点,够折腾的。

            tmplength--;
        }
    }

}

int main(int argc, char *argv[])
{
    
    int i;
    int arr[] = {2,5,7,4,3,6,9,10,22,14};
    int length = sizeof(arr)/sizeof(arr[0]);
    for(i = 0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
    
    //reversal(arr,0,0);

    sort(arr,length);

    for(i = 0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");

    return 0;
}



这里,我是用一个数组模拟这些饼,最终实现从小到大排序就行了。算法大致描述如下,首先从这么多饼中
找到最大的,这很容易办到吧,然后将最大的饼一直到最上面的整体翻转,先让最大饼到最顶端,然后整体再
翻转,这样,最大饼到了最底下了。
接着继续,将剩余的上面的饼不断的运用上面的算法,次大的,次次大的饼不断的被弄到底下,直到最后肯定
就将所有的排好了。
恩,其实,效率问题是这个算法的最大缺陷,有时间研究研究。今天就先说道这。
阅读(1086) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~