Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2270431
  • 博文数量: 102
  • 博客积分: 1444
  • 博客等级: 中尉
  • 技术积分: 13853
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-29 10:58
文章分类

全部博文(102)

文章存档

2014年(29)

2013年(14)

2012年(59)

分类: C/C++

2012-03-31 22:08:57

转载请注明来源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需要多少个球?假设,指示器都为空,球队列需要多长时间能回到原来的状态?

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

  3. #define MAX 20

  4. #define _SEGMENT_
  5. #define _DEBUG_

  6. //栈设计
  7. typedef struct
  8. {
  9.     int data[MAX];
  10.     int num;
  11. }Stack;

  12. //队列设计
  13. struct _node_
  14. {
  15.     int data;
  16.     struct _node_ *next;
  17. };

  18. typedef struct
  19. {
  20.     struct _node_ *front;
  21.     struct _node_ *rear;
  22.     
  23. }ListQueue;

  24. //栈操作
  25. int stack_init(Stack **p)
  26. {
  27.     *p = (Stack *)malloc(sizeof(Stack));
  28.     (*p)->num = -1;

  29.     return 0;
  30. }

  31. int is_empty_stack(Stack *p)
  32. {
  33.     if(p->num == -1)
  34.         return 1;
  35.     else
  36.         return 0;
  37. }

  38. int is_full_stack(Stack *p)
  39. {
  40.     if(p->num == MAX -1)
  41.         return 1;
  42.     else
  43.         return 0;
  44. }

  45. int push_stack(Stack *p,int data)
  46. {
  47.     if(is_full_stack(p))
  48.     {
  49.         printf("Error!Stack is full.\n");
  50.         return -1;
  51.     }
  52.     
  53.     p->num ++;
  54.     p->data[p->num] = data;

  55.     return 0;
  56. }

  57. int pop_stack(Stack *p)
  58. {
  59.     int data;
  60.     
  61.     if(is_empty_stack(p))
  62.     {
  63.         printf("Error!Stack is empty.\n");
  64.         return -1;
  65.     }

  66.     data = p->data[p->num];
  67.     p->num --;

  68.     return data;
  69. }

  70. //队列操作
  71. int queue_init(ListQueue **p)
  72. {
  73.     struct _node_ *head;

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

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

  80.     return 0;
  81. }

  82. int is_empty_queue(ListQueue *p)
  83. {
  84.     if(p->front->next == NULL && p->rear->next == NULL)
  85.         return 1;
  86.     else
  87.         return 0;
  88. }

  89. int push_queue(ListQueue *p,int data)
  90. {
  91.     struct _node_ *temp;

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

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

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

  100.     return 0;
  101. }

  102. int pop_queue(ListQueue *p)
  103. {
  104.     struct _node_ *temp;
  105.     int data;

  106.     if(is_empty_queue(p))
  107.     {
  108.         printf("Error!,queue is empty...\n");
  109.         return 0;
  110.     }
  111.     
  112.     //指向头结点的下一个结点
  113.     temp = p->front->next;
  114.     data = temp->data;
  115.     
  116.     //删除结点
  117.     p->front->next = temp->next;
  118.     free(temp);
  119.     temp = NULL;

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

  123.     return data;
  124. }

  125. int print_queue(ListQueue *p)
  126. {
  127.     if(is_empty_queue(p))
  128.     {
  129.         printf("Error!,queue is empty...\n");
  130.         return 0;
  131.     }
  132.     
  133.     struct _node_ *q = p->front->next;

  134.     while(q)
  135.     {
  136.         printf("%d ",q->data);

  137.         q = q->next;
  138.     }

  139.     printf("\n");

  140.     return 0;
  141. }

  142. int true_ballqueue(ListQueue *p)
  143. {
  144.     struct _node_ *q = p->front->next;
  145.     int i = 0;
  146.     
  147.     for(i = 1;i <= 27;i ++)
  148.     {
  149.         if(q->data != i)
  150.             return 0;
  151.         q = q->next;
  152.     }

  153.     return 1;
  154. }

  155. //解决球钟问题
  156. int main()
  157. {
  158.     Stack *mStack,*fmStack,*hStack;
  159.     ListQueue *ballQueue;
  160.     int data;
  161.     int time = 0;

  162.     //队列、栈初始化
  163.     stack_init(&mStack);
  164.     stack_init(&fmStack);
  165.     stack_init(&hStack);
  166.     queue_init(&ballQueue);

  167.     //给队列装球
  168.     int i = 0;
  169.     for(i = 1;i <= 27;i ++)
  170.     {
  171.         push_queue(ballQueue,i);
  172.     }
  173.     

  174.     while(1)
  175.     {
  176.         //从球队列出球进入分钟指示器
  177.         data = pop_queue(ballQueue);
  178.         if(mStack->num == 3)
  179.         {
  180.             int i = 0;
  181.             int temp;
  182.         
  183.             //分钟指示器的球进入球队列
  184.             for(i = 0;i < 4;i ++)
  185.             {
  186.                 temp = pop_stack(mStack);
  187.                 push_queue(ballQueue,temp);
  188.             }
  189.             
  190.             if(fmStack->num == 10)
  191.             {
  192.                 //5分钟指示器的球进入球队列
  193.                 for(i = 0;i < 11;i ++)
  194.                 {
  195.                     temp = pop_stack(fmStack);
  196.                     push_queue(ballQueue,temp);
  197.                 }

  198.                 if(hStack->num == 10)
  199.                 {
  200.                     
  201.                     //小时指示器的球进入球队列
  202.                     for(i = 0;i < 11;i ++)
  203.                     {
  204.                         temp = pop_stack(hStack);
  205.                         push_queue(ballQueue,temp);
  206.                     }
  207.                     
  208.                     push_queue(ballQueue,data);
  209.                     
  210.                     time ++;

  211.                     if(true_ballqueue(ballQueue))
  212.                     {
  213.                         break;
  214.                     }
  215.                 
  216.                 }else{
  217.                     push_stack(hStack,data);
  218.                 }
  219.             
  220.             }else{
  221.                 push_stack(fmStack,data);
  222.             }
  223.         
  224.         }else{
  225.             
  226.             push_stack(mStack,data);

  227.         }

  228.     }

  229.     printf("time = %d\n",time);
  230.     
  231.     return 0;
  232. }
这个问题,只要思路清晰,实现起来还是比较简单的。
阅读(4846) | 评论(2) | 转发(12) |
给主人留下些什么吧!~~

安静的美男子2015-04-29 16:14:20

jiaziqian:哥们儿也是华清的吧..

哈哈,是我们老师!

回复 | 举报

jiaziqian2013-03-08 13:07:18

哥们儿也是华清的吧..