| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1907 人关注过本帖
标题:蛮有挑战的一道数据结构的题目,来看看,谁编一下
只看楼主 加入收藏
louh
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2005-4-29
收藏
 问题点数:0 回复次数:16 
蛮有挑战的一道数据结构的题目,来看看,谁编一下

球钟(Ball Clock

1.问题描述

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

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

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

2.要求:

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

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

③测试程序二:分别计算球的个数x27127时,分别需要经过多少天,并把计算结果(以整数形式)保存在一个文件result.txt中。

3.测试数据:

测试数据x

参考答案

27

23

45

378

87

570

88

1026

127

2415

搜索更多相关主题的帖子: 数据结构 指示器 Roman 
2005-04-29 10:28
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 

#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编辑过]


c++/C + 汇编 = 天下无敌
2005-04-30 03:49
激情依旧
Rank: 1
等 级:新手上路
威 望:2
帖 子:524
专家分:0
注 册:2005-4-4
收藏
得分:0 
晕~~~~~~~~~这个时候你竟然还在编.............看来不用上课了

生是编程人!!!!死是编程鬼!!!!颠峰人生!!!焚尽编程!!! 爱已严重死机!情必须重新启动!情人已和服务器断开连接!网恋也需要重新拨号!-----激情依旧
2005-04-30 04:42
激情依旧
Rank: 1
等 级:新手上路
威 望:2
帖 子:524
专家分:0
注 册:2005-4-4
收藏
得分:0 
通宵写程序................热情狂人~~~~~~~~~~

生是编程人!!!!死是编程鬼!!!!颠峰人生!!!焚尽编程!!! 爱已严重死机!情必须重新启动!情人已和服务器断开连接!网恋也需要重新拨号!-----激情依旧
2005-04-30 04:44
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 

#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); } 这个是修改板,可以输入钟球个数


c++/C + 汇编 = 天下无敌
2005-04-30 12:51
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 
这道题目是我目前见到最好的题目,一个字爽~~~~~~~~~~~~~~~~~~~

c++/C + 汇编 = 天下无敌
2005-04-30 12:55
激情依旧
Rank: 1
等 级:新手上路
威 望:2
帖 子:524
专家分:0
注 册:2005-4-4
收藏
得分:0 
我帮热情测试这条程序的时候,输入127。我的cpu是塞杨4 2.4G。用来运行。结果用了5分钟才运行完毕。大家可以拿这条程序去测试一下你的cpu。呵呵~~~~~~~~

生是编程人!!!!死是编程鬼!!!!颠峰人生!!!焚尽编程!!! 爱已严重死机!情必须重新启动!情人已和服务器断开连接!网恋也需要重新拨号!-----激情依旧
2005-05-01 01:08
rzd
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2005-5-6
收藏
得分:0 
牛!

2005-05-06 10:15
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 

不用这么麻烦吧? #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 ; } 如果再模块化一下,再优化一下,还可更短小一点,效率更高一点。 未做容错处理.


九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-05-06 20:02
激情依旧
Rank: 1
等 级:新手上路
威 望:2
帖 子:524
专家分:0
注 册:2005-4-4
收藏
得分:0 
强!!!

生是编程人!!!!死是编程鬼!!!!颠峰人生!!!焚尽编程!!! 爱已严重死机!情必须重新启动!情人已和服务器断开连接!网恋也需要重新拨号!-----激情依旧
2005-05-06 21:13
快速回复:蛮有挑战的一道数据结构的题目,来看看,谁编一下
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.035340 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved