球钟（Ball Clock）

1．问题描述

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

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

现设初始时球队列的球数为x（27≤x≤127），球钟的三个指示器初态均为空。问要经过多少天（每天24小时），球钟的球队列才能回复原来的顺序。

2．要求：

①编写计算x个球需要多少天的算法。

②测试程序一：从键盘输入x，答案用整数形式输出到屏幕。

③测试程序二：分别计算球的个数x从27到127时，分别需要经过多少天，并把计算结果（以整数形式）保存在一个文件result.txt中。

3．测试数据：

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

typedef struct queue{ int data; struct queue *next; }QueueNode; typedef struct{ QueueNode *rear,*front; }LinQueue;

void InitiateQueue(LinQueue *Q) { Q->front=Q->rear=NULL; } int IsEmptyQueue(LinQueue *Q) { return Q->front==NULL; } void InQueue(LinQueue *Q,int item) { QueueNode *p; p=(QueueNode *)malloc(sizeof(QueueNode)); p->data=item; p->next=NULL; if(Q->front==NULL) Q->front=Q->rear=p; else{ Q->rear->next=p; Q->rear=p; } } int OutQueue(LinQueue *Q) { QueueNode *p; int x; if(IsEmptyQueue(Q)) exit(1); p=Q->front; x=p->data; if(Q->rear==p) {free(p); return x;} else{ Q->front=p->next; free(p); return x; } } int GetQueuTop(LinQueue *Q) { if(IsEmptyQueue(Q)) exit(1); return Q->front->data; } typedef struct stacknode{ int data; struct stacknode *next; }Stacknode; typedef struct{ Stacknode *top; }LinStack; void InitiateStack(LinStack *s){ s->top=NULL; } int IsEmptyStack(LinStack *s){ return s->top==NULL; } void push(LinStack *s,int item) { Stacknode *p; p=(Stacknode *)malloc(sizeof(Stacknode)); p->data=item; p->next=s->top; s->top=p; } int pop(LinStack *s) { Stacknode *p; int x; if(IsEmptyStack(s)) exit(1); p=s->top; x=p->data; s->top=p->next; free(p); return x; } int top(LinStack *s) { if(IsEmptyStack(s)) exit(1); return s->top->data; } void main(){ LinQueue Q; LinStack Ss,Sm,Sh; int i,counts=0,countm=0,counth=0,counthalfday=1,b[45],flag=0,d[45]; InitiateStack(&Ss); InitiateStack(&Sm); InitiateStack(&Sh); InitiateQueue(&Q); for(i=1;i<=45;i++) //初始化，输入1-45 InQueue(&Q,i); for(i=0;i<45;i++) b[i]=i+1; while(1){ while(countm<=11||counth==11){ while(counts<4||countm==11&&counth==11){ push(&Ss,OutQueue(&Q)); counts++; if(counts==4&&countm==11&&counth==11) {counts=0; countm=0; counth=0; for(i=0;i<4;i++) InQueue(&Q,pop(&Ss)); for(i=0;i<11;i++) InQueue(&Q,pop(&Sm)); for(i=0;i<11;i++) InQueue(&Q,pop(&Sh)); InQueue(&Q,OutQueue(&Q)); for(i=0;i<45;i++) d[i]=OutQueue(&Q); printf("排序数字:\n"); for(i=0;i<45;i++) printf("%d\t",d[i]); printf("\n\n"); InitiateQueue(&Q); for(i=0;i<45;i++) InQueue(&Q,d[i]); i=0; //判断是否跟初始化的队列一样 while(i<45) { if(b[i]==d[i]) i++; else break; } if(i==45) flag=1; if(flag==1) break; counthalfday++; } } if(flag==1) break; counts=0; for(i=0;i<4;i++) InQueue(&Q,pop(&Ss)); if(IsEmptyStack(&Sm)&&IsEmptyStack(&Sh)){ //判断是否跟初始化的队列一样 for(i=0;i<45;i++) d[i]=OutQueue(&Q); for(i=0;i<45;i++) printf("%d\t",d[i]); printf("\n\n"); InitiateQueue(&Q); for(i=0;i<45;i++) InQueue(&Q,d[i]); i=0; while(i<45) { if(b[i]==d[i]) i++; else break; } if(i==45) flag=1; if(flag==1) break; } if(countm==11) break; push(&Sm,OutQueue(&Q)); countm++; } if(flag==1) break; countm=0; for(i=0;i<11;i++) InQueue(&Q,pop(&Sm)); if(IsEmptyStack(&Sm)&&IsEmptyStack(&Sh)){ //判断是否跟初始化的队列一样 for(i=0;i<45;i++) d[i]=OutQueue(&Q); for(i=0;i<45;i++) printf("%d\t",d[i]); printf("\n\n"); InitiateQueue(&Q); for(i=0;i<45;i++) InQueue(&Q,d[i]); i=0; while(i<45) { if(b[i]==d[i]) i++; else break; } if(i==45) flag=1; if(flag==1) break; } push(&Sh,OutQueue(&Q)); counth++; } printf("总共要%d天\n",counthalfday/2);

}

这个是输入45个球的。答案上机验证过了。绝对正确！！！！！ 378 哈哈。通宵写完了~~~~~~~~大家慢慢看。经典~

[此贴子已经被作者于2005-4-30 8:52:35编辑过]

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

typedef struct queue{ int data; struct queue *next; }QueueNode; typedef struct{ QueueNode *rear,*front; }LinQueue;

void InitiateQueue(LinQueue *Q) { Q->front=Q->rear=NULL; } int IsEmptyQueue(LinQueue *Q) { return Q->front==NULL; } void InQueue(LinQueue *Q,int item) { QueueNode *p; p=(QueueNode *)malloc(sizeof(QueueNode)); p->data=item; p->next=NULL; if(Q->front==NULL) Q->front=Q->rear=p; else{ Q->rear->next=p; Q->rear=p; } } int OutQueue(LinQueue *Q) { QueueNode *p; int x; if(IsEmptyQueue(Q)) exit(1); p=Q->front; x=p->data; if(Q->rear==p) {free(p); return x;} else{ Q->front=p->next; free(p); return x; } } int GetQueuTop(LinQueue *Q) { if(IsEmptyQueue(Q)) exit(1); return Q->front->data; } typedef struct stacknode{ int data; struct stacknode *next; }Stacknode; typedef struct{ Stacknode *top; }LinStack; void InitiateStack(LinStack *s){ s->top=NULL; } int IsEmptyStack(LinStack *s){ return s->top==NULL; } void push(LinStack *s,int item) { Stacknode *p; p=(Stacknode *)malloc(sizeof(Stacknode)); p->data=item; p->next=s->top; s->top=p; } int pop(LinStack *s) { Stacknode *p; int x; if(IsEmptyStack(s)) exit(1); p=s->top; x=p->data; s->top=p->next; free(p); return x; } int top(LinStack *s) { if(IsEmptyStack(s)) exit(1); return s->top->data; } void main(){ LinQueue Q; LinStack Ss,Sm,Sh; int i,counts=0,countm=0,counth=0,counthalfday=1,b[255],flag=0,d[255],x; //counts是一分钟计算器，countm是五分钟计算器 InitiateStack(&Ss); //counth是小时计算器，counthalf是半天计算器 InitiateStack(&Sm); //数组b用来储存初始化队列，数组d用来储存变动队列 InitiateStack(&Sh); //Ss,Sm,Sh分别是一分种，五分钟，一小时栈 InitiateQueue(&Q); printf("输入钟球个数:\n"); scanf("%d",&x); for(i=1;i<=x;i++) InQueue(&Q,i); for(i=0;i<x;i++) b[i]=i+1; while(1){ while(countm<=11||counth==11){ while(counts<4||countm==11&&counth==11){ push(&Ss,OutQueue(&Q)); counts++; if(counts==4&&countm==11&&counth==11) {counts=0; countm=0; counth=0; for(i=0;i<4;i++) InQueue(&Q,pop(&Ss)); for(i=0;i<11;i++) InQueue(&Q,pop(&Sm)); for(i=0;i<11;i++) InQueue(&Q,pop(&Sh)); InQueue(&Q,OutQueue(&Q)); for(i=0;i<x;i++) d[i]=OutQueue(&Q); printf("输出排序结果:\n"); for(i=0;i<x;i++) printf("%d\t",d[i]); printf("\n\n"); InitiateQueue(&Q); for(i=0;i<x;i++) InQueue(&Q,d[i]); i=0; while(i<x) { if(b[i]==d[i]) i++; else break; } if(i==x) flag=1; if(flag==1) break; counthalfday++; } } if(flag==1) break; counts=0; for(i=0;i<4;i++) InQueue(&Q,pop(&Ss)); if(IsEmptyStack(&Sm)&&IsEmptyStack(&Sh)){ for(i=0;i<x;i++) d[i]=OutQueue(&Q); for(i=0;i<x;i++) printf("%d\t",d[i]); printf("\n\n"); InitiateQueue(&Q); for(i=0;i<x;i++) InQueue(&Q,d[i]); i=0; while(i<x) { if(b[i]==d[i]) i++; else break; } if(i==x) flag=1; if(flag==1) break; } if(countm==11) break; push(&Sm,OutQueue(&Q)); countm++; } if(flag==1) break; countm=0; for(i=0;i<11;i++) InQueue(&Q,pop(&Sm)); if(IsEmptyStack(&Sm)&&IsEmptyStack(&Sh)){ for(i=0;i<x;i++) d[i]=OutQueue(&Q); for(i=0;i<x;i++) printf("%d\t",d[i]); printf("\n\n"); InitiateQueue(&Q); for(i=0;i<x;i++) InQueue(&Q,d[i]); i=0; while(i<x) { if(b[i]==d[i]) i++; else break; } if(i==x) flag=1; if(flag==1) break; } push(&Sh,OutQueue(&Q)); counth++; } printf("天数：%d\n",counthalfday/2); } 这个是修改板，可以输入钟球个数

不用这么麻烦吧？ #include <stdio.h> #include <alloc.h> typedef struct Globule { int Globule_number ; struct Globule*next ; } GNode ;

GNode*InitializeGlobule(GNode*First,int x) { GNode*Next,*End ; int i ; End=First ; for(i=1;i<x;i++) { Next=(GNode*)malloc(sizeof(GNode)); Next->Globule_number=i ; End->next=Next ; End=Next ; } End->next=First ; return End ; } int Test(GNode*First,GNode*End,int x) { int i ; GNode*temp,*tem ; temp=First ; tem=End->next ; if(temp!=tem)return 0 ; for(i=0;i<x;i++) { if(temp->Globule_number!=i)return 0 ; else temp=temp->next ; } return 1 ; } void DelGlobule(GNode*First) { GNode* Temp0=First,*Temp1=First->next;

while(1) { free(Temp0); Temp0=Temp1; if(Temp1->next!=First)Temp1=Temp1->next; else break; }

}

void main(void) { int x ,i; GNode*First=NULL,*End=NULL; int One,Five,Hour,day; int OneSum[4],FiveSum[11],HourSum[11]; for(i=0;i<10;i++) { printf("\n输入球钟球数( 27<=x<=127) :\nx= "); scanf("%d",&x); One=0,Five=0,Hour=0,day=0 ; First=(GNode*)malloc(sizeof(GNode)); First->Globule_number=0 ; End=InitializeGlobule(First,x); while(1) { One++; if(One<5) { OneSum[One-1]=First->Globule_number ; First=First->next ; } else { Five++; while(One>1) { End=End->next ; End->Globule_number=OneSum[One-2]; One--; } One=0 ; if(Five<12) { FiveSum[Five-1]=First->Globule_number ; First=First->next ; } else { Hour++; while(Five>1) { End=End->next ; End->Globule_number=FiveSum[Five-2]; Five--; } Five=0 ; if(Hour<12) { HourSum[Hour-1]=First->Globule_number ; First=First->next ; } else { day++; while(Hour>1) { End=End->next ; End->Globule_number=HourSum[Hour-2]; Hour--; } Hour=0 ; End=End->next ; End->Globule_number=First->Globule_number ; First=First->next ; } } } if(Hour==0&&Five==0&&One==0&&Test(First,End,x)) { printf("\n\n总共要%d天\n",day/2); DelGlobule(First); break ; } } } getch(); return ; } 如果再模块化一下，再优化一下，还可更短小一点，效率更高一点。 未做容错处理.