球钟问题

转载请注明来源chengyaogen.blog.chinaunix.net    

 

 球钟问题描述:球钟是一个利用球的移动来记录时间的简单装置。它有三个可以容纳若干个球的指示器：分钟指示器，五分钟指示器，小时指示器。若分钟指示器中有2个球，5分钟指示器中有6个球，小时指示器中有5个球，则时间为5:32。

    

        工作原理:每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器最多可容纳4个球。当放入第五个球时，在分钟指示器的4个球就会按照他们被放入时的相反顺序加入球队列的队尾。而第五个球就会进入分钟指示器。按此类推，五分钟指示器最多可放11个球，小时指示器最多可放11个球。当小时指示器放入第12个球时，原来的11个球按照他们被放入时的相反顺序加入球队列的队尾，然后第12个球也回到队尾。这时，三个指示器均为空，回到初始状态，从而形成一个循环。因此，该秋种表示的时间范围是从00:00到11:59

 

 

思考：

    要想表示00:00到12：00需要多少个球?假设，指示器都为空，球队列需要多长时间能回到原来的状态?

#include <stdio.h>
#include <stdlib.h>

#define MAX 20

#define _SEGMENT_
#define _DEBUG_

//栈设计
typedef struct
{
    int data[MAX];
    int num;
}Stack;

//队列设计
struct _node_
{
    int data;
    struct _node_ *next;
};

typedef struct
{
    struct _node_ *front;
    struct _node_ *rear;

}ListQueue;

//栈操作
int stack_init(Stack **p)
{
    *p = (Stack *)malloc(sizeof(Stack));
    (*p)->num = -1;

    return 0;
}

int is_empty_stack(Stack *p)
{
    if(p->num == -1)
        return 1;
    else
        return 0;
}

int is_full_stack(Stack *p)
{
    if(p->num == MAX -1)
        return 1;
    else
        return 0;
}

int push_stack(Stack *p,int data)
{
    if(is_full_stack(p))
    {
        printf("Error!Stack is full.\n");
        return -1;
    }

    p->num ++;
    p->data[p->num] = data;

    return 0;
}

int pop_stack(Stack *p)
{
    int data;

    if(is_empty_stack(p))
    {
        printf("Error!Stack is empty.\n");
        return -1;
    }

    data = p->data[p->num];
    p->num --;

    return data;
}

//队列操作
int queue_init(ListQueue **p)
{
    struct _node_ *head;

    //创建一个头结点
    head = (struct _node_ *)malloc(sizeof(struct _node_));
    head->next = NULL;

    //让队列的头尾都指向它
    *p = (ListQueue *)malloc(sizeof(ListQueue));
    (*p)->front = (*p)->rear = head;

    return 0;
}

int is_empty_queue(ListQueue *p)
{
    if(p->front->next == NULL && p->rear->next == NULL)
        return 1;
    else
        return 0;
}

int push_queue(ListQueue *p,int data)
{
    struct _node_ *temp;

    //分配结点
    temp = (struct _node_ *)malloc(sizeof(struct _node_));
    temp->data = data;
    temp->next = NULL;

    //尾部插入结点
    p->rear->next = temp;

    //更新尾部指针
    p->rear = temp;

    return 0;
}

int pop_queue(ListQueue *p)
{
    struct _node_ *temp;
    int data;

    if(is_empty_queue(p))
    {
        printf("Error!,queue is empty...\n");
        return 0;
    }

    //指向头结点的下一个结点
    temp = p->front->next;
    data = temp->data;

    //删除结点
    p->front->next = temp->next;
    free(temp);
    temp = NULL;

    //最后一个结点处理
    if(p->front->next == NULL)
        p->rear = p->front;

    return data;
}

int print_queue(ListQueue *p)
{
    if(is_empty_queue(p))
    {
        printf("Error!,queue is empty...\n");
        return 0;
    }

    struct _node_ *q = p->front->next;

    while(q)
    {
        printf("%d ",q->data);

        q = q->next;
    }

    printf("\n");

    return 0;
}

int true_ballqueue(ListQueue *p)
{
    struct _node_ *q = p->front->next;
    int i = 0;

    for(i = 1;i <= 27;i ++)
    {
        if(q->data != i)
            return 0;
        q = q->next;
    }

    return 1;
}

//解决球钟问题
int main()
{
    Stack *mStack,*fmStack,*hStack;
    ListQueue *ballQueue;
    int data;
    int time = 0;

    //队列、栈初始化
    stack_init(&mStack);
    stack_init(&fmStack);
    stack_init(&hStack);
    queue_init(&ballQueue);

    //给队列装球
    int i = 0;
    for(i = 1;i <= 27;i ++)
    {
        push_queue(ballQueue,i);
    }


    while(1)
    {
        //从球队列出球进入分钟指示器
        data = pop_queue(ballQueue);
        if(mStack->num == 3)
        {
            int i = 0;
            int temp;

            //分钟指示器的球进入球队列
            for(i = 0;i < 4;i ++)
            {
                temp = pop_stack(mStack);
                push_queue(ballQueue,temp);
            }

            if(fmStack->num == 10)
            {
                //5分钟指示器的球进入球队列
                for(i = 0;i < 11;i ++)
                {
                    temp = pop_stack(fmStack);
                    push_queue(ballQueue,temp);
                }

                if(hStack->num == 10)
                {

                    //小时指示器的球进入球队列
                    for(i = 0;i < 11;i ++)
                    {
                        temp = pop_stack(hStack);
                        push_queue(ballQueue,temp);
                    }

                    push_queue(ballQueue,data);

                    time ++;

                    if(true_ballqueue(ballQueue))
                    {
                        break;
                    }

                }else{
                    push_stack(hStack,data);
                }

            }else{
                push_stack(fmStack,data);
            }

        }else{

            push_stack(mStack,data);

        }

    }

    printf("time = %d\n",time);

    return 0;
}

这个问题，只要思路清晰，实现起来还是比较简单的。