球钟(Ball Clock)
1.问题描述
球钟是一个利用球的移动来记录时间的简单装置。它有三个可以容纳若干个球的指示器:分钟指示器,五分钟
指示器,小时指示器。若分钟指示器中有2个球,五分钟指示器中有6个球,小时指示器中有5个球,则时间为5
:32。
球钟的工作原理如下:分钟指示器最多可容纳4个球。每过一分钟,球钟就会从球队列的队首取出一个球放入分
钟指示器,当放入第五个球时,在分钟指示器的4个球就会按照他们被放入时的相反顺序加入球队列的队尾。而
第五个球就会进入五分钟指示器。按此类推,五分钟指示器最多可放11个球,小时指示器最多可放11个球。当
小时指示器放入第12个球时,原来的11个球按照他们被放入时的相反顺序加入球队列的队尾,然后第12个球也
回到队尾。这时,三个指示器均为空,回到初始状态,从而形成一个循环。因此,该球钟表示时间的范围是从0
:00到11:59。
现设初始时球队列的球数为x(27≤x),球钟的三个指示器初态均为空。问要经过多少天(每天24小时)
,球钟的球队列才能回复原来的顺序。
实现代码如下:
#include
#include
#define N 16
typedef int datatype;
typedef struct
{
datatype data[N];
int top;
} seqstack;
typedef struct _node_
{
datatype data;
struct _node_ *next;
} linknode, *linklist;
typedef struct
{
linklist front;
linklist rear;
} linkqueue;
seqstack *CreateEmptyStack()
{
seqstack *s;
s = (seqstack *)malloc(sizeof(seqstack));
s->top = -1;
return s;
}
int EmptyStack(seqstack *s)
{
return (-1 == s->top);
}
void PushStack(seqstack *s, datatype x)
{
s->data[++s->top] = x;
return;
}
datatype PopStack(seqstack *s)
{
s->top--;
return s->data[s->top+1];
}
linkqueue *CreateEmptyQueue()
{
linkqueue *lq;
lq = (linkqueue *)malloc(sizeof(linkqueue));
lq->front = lq->rear = (linklist)malloc(sizeof(linknode));
lq->front->next = NULL;
return lq;
}
int EmptyQueue(linkqueue *lq)
{
return (lq->front == lq->rear);
}
void EnQueue(linkqueue *lq, datatype x)
{
lq->rear->next = (linklist)malloc(sizeof(linknode));
lq->rear = lq->rear->next;
lq->rear->data = x;
lq->rear->next = NULL;
return;
}
datatype DeQueue(linkqueue *lq)
{
linklist q;
q = lq->front;
lq->front = q->next;
free(q);
return (lq->front->data);
}
void ClearQueue(linkqueue *lq)
{
linklist q;
while (lq->front != lq->rear)
{
q = lq->front;
lq->front = q->next;
free(q);
}
return;
}
int SameQueue(linkqueue *lq)
{
linklist p = lq->front->next;
while (p!= lq->rear)
{
if (p->data > p->next->data) return 0;
p = p->next;
}
return 1;
}
int main()
{
int i, x, sum = 0;
seqstack *s1, *s5, *s60;
linkqueue *lq;
s1 = CreateEmptyStack();
s5 = CreateEmptyStack();
s60 = CreateEmptyStack();
lq = CreateEmptyQueue();
for (i=1; i<=27; i++)
{
EnQueue(lq, i);
}
while ( 1 )
{
sum++;
x = DeQueue(lq);
if (s1->top != 3)
{
PushStack(s1, x);
}
else
{
while ( ! EmptyStack(s1) )
{
EnQueue(lq, PopStack(s1));
}
if (s5->top != 10)
{
PushStack(s5, x);
}
else
{
while ( ! EmptyStack(s5) )
{
EnQueue(lq, PopStack(s5));
}
if (s60->top != 10)
{
PushStack(s60, x);
}
else
{
while ( ! EmptyStack(s60) )
{
EnQueue(lq, PopStack(s60));
}
EnQueue(lq, x);
if ( SameQueue(lq) ) break;
}
}
}
}
printf("sum = %d\n", sum);
return 0;
}
|
文件: |
ball_clock.zip |
大小: |
2KB |
下载: |
下载 | |
阅读(1563) | 评论(0) | 转发(2) |