大家好！《请你编程》又与你们见面了。本期《请你编程》的题目虽然存在一定难度，但如果仔细阅读题目内容，理解给出的程序要求，再结合范例，就能找到本题的解题思想。希望爱好编程的朋友们本着“重在参与”的精神投入进来，关心和支持《请你编程》。现在，请看本期福建读者叶毓睿的答案。
9903请你编程解题思路：
将柱子的位置视为点，距离走廊左端、上端的长度即该点的横、纵坐标。各点连接可以构成许多不同的路径，我们只观察那些从上端能到达下端，且无回头方向的完整路径。每一条路径都有一条最长的线段，将所有路径的最长线段选取出来，其中最短的那条，就是能通过走廊最胖的胖子的直径。
本程序采用递归算法：先把各点按纵坐标从小到大排序，以最上端的点为基准点。从基准点出发，寻找纵坐标比它大的点作为当前基准点。调用递归函数顺序连接比当前基准点纵坐标大的点，直至最下端。记录这条路径的最长线段，返回递归调用，再连接其他比当前基准点纵坐标大的点，一直到最下端的点成为基准点为止。将每次记录的最长线段与前次相比，取其短者参与下一次比较。最后得到的最短者即为所求。
源程序：
＃include ″math.h″
＃include ″stdio.h″
＃define Points 200 /＊定义可能输入的最大点数＊/
int A[Points][2] , X=0 , Y=1 , n , i ;
double Min_MaxDis ;
void Sort() /＊将所有点按纵坐标从小到大排序＊/
{ int i , j , TempX , TempY ;
for(i=0 ; i<n ; i＋＋)
for(j=i＋1 ; j<n ; j＋＋)
if(A[j][Y]<A[i][Y])
{ TempX=A[i][X] ; TempY=A[i][Y] ;
A[i][X]=A[j][X] ; A[i][Y]=A[j][Y] ;
A[j][X]=TempX ; A[j][Y]=TempY ;
}}
double Dis(int m , int n) /＊计算两个点的距离＊/
{ unsigned Sum ;
Sum=(A[m][X]－A[n][X])＊(A[m][X]－A[n][X])＋(A[m][Y]－A[n][Y])＊(A[m][Y]－A[n][Y]);
return sqrt(Sum) ;}
void NextDatumPoint(int i , double MaxDis1)
/＊递归函数：其中i为当前基准点对应的数组下标，MaxDis1为从上端到下端的某条固定路径中的最长线段，而前面的全局变量Min_MaxDis则为所有最长线段中最短的一条。＊/
{int ii ;
double dis ;
ii=i ;
for(i=ii＋1 ; i<n ; i＋＋)
if(dis=Dis(i,ii),(A[i][Y]>A[ii][Y])&&(dis<100－A[ii][Y])&&(dis<A[i][Y]))
/＊基准点只连接纵坐标比它大的点，且这两点的距离比它们到上下端的距离还小＊/
NextDatumPoint( i , (MaxDis1>dis)?MaxDis1:dis ) ;
/＊选取MaxDis1与dis中的较大者作为递归调用的实参变量＊/
if(100－A[ii][Y]>MaxDis1)
MaxDis1=100－A[ii][Y] ;/＊若纵坐标最大的点到下端的距离更大,则赋给MaxDis1＊/
if(MaxDis1<Min_MaxDis)
Min_MaxDis=MaxDis1 ;/＊依次比较所有的MaxDia1，将最小值赋给Min_MaxDis＊/
}
main ()
{ void NextDatumPoint(int i , double MaxDis1) ;
FILE ＊fp ;
double MaxDis ;
printf(″\n″) ;
if( (fp=fopen(″Fatman.txt″,″rt″))==NULL )
{ printf(″\nCan not open file fatman.txt ! ″) ; getch() ; exit(1); }
fscanf(fp,″%d″,&n) ;
while(n!=0) /＊若n值不为0，则输入一组各点的横纵坐标，并显示判断结果＊/
{for(i=0 ; i<n ; i＋＋) fscanf(fp,″%d%d″,&A[i][X],&A[i][Y]) ;
Sort() ;
Min_MaxDis=100 ;
for(i=0 ; i<n ; i＋＋)
{ MaxDis=A[i][Y] ;
NextDatumPoint(i , MaxDis);}
printf(″\n\t能通过走廊最胖的胖子的直径是: %8.5f ″,Min_MaxDis) ;
fscanf(fp,″%d″,&n) ;}
fclose(fp) ;}
9905请你编程题目：
有一家核电厂要存储一批核物质。存储的形式是在地上挖若干个坑，把核物质埋在坑里，而且这些坑正好排成一条直线。但是由于核物质放得太密集的话会发生核爆炸，经过计算，核电厂发现如果连续3个坑中放的都是核物质就会发生核爆炸。所以必须在某些坑中放入一些非核物质来把核物质隔离开。很明显，如果放置不当的话，有很多种组合会发生核爆炸。例如：把核物质记为1，非核物质记为0，在有4个坑的情况下，有3种组合1110，0111，1111会发生核爆炸。核电厂知道坑的数目，但不知道在这种情况下会有多少种组合会发生核爆炸。现在就请你编一个程序，帮他们计算一下。
程序要求如下：
1、输入数据从文本文件howmany.txt中读取。文件格式为：第一行为一个整数n，表示有n组输入数据。以下n行，每行包括一个整数i，表示有i个坑，i<32。
2、输出到屏幕上，输出为n行，每行包括两个整数i、k，表示如果有i个坑的话，就有k种组合会发生核爆炸。
输入范例：
2
3
4
输出范例：
3 1
4 3
来稿请寄磁盘稿或用E－mail投稿，请写明解题思路和源程序(包含详细的注解)，将来稿寄到电脑报编辑部的收信地址或E－mail邮箱，同时欢迎提供请你编程的题目。来稿截止日期：1999年5月15日
本期获奖者名单：
林 岳(天津)孙铁钢(四川)张玉源(重庆)吴德涛(广西)石 麟(新疆)方 镜(安徽)向 军(浙江)冉晓容(天津)张 利(甘肃)张 静(重庆)
每位获奖者将获得苦丁香公司提供的光盘一张。
本文出自：《电脑报》1999年04月5日第13期
|
