Chinaunix首页 | 论坛 | 博客
  • 博客访问: 862834
  • 博文数量: 156
  • 博客积分: 6553
  • 博客等级: 准将
  • 技术积分: 3965
  • 用 户 组: 普通用户
  • 注册时间: 2010-06-22 18:36
文章存档

2012年(3)

2011年(43)

2010年(110)

分类: C/C++

2010-10-03 16:21:01

球钟(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) |
给主人留下些什么吧!~~