2005 年上半年程序员考试试题下午试卷 第四题 看不懂

假设一个剧场有N*N个座位，顾客买票时可以提出任意有效的座号请求。下面用二维数组a[N][N]模拟剧场中的座位，a[i][j]等于0表示第i排第j列(0≤I , j≤N-1)的票尚未售出。
　　函数int Find ( int a[][N] , int R , int *row , int *col )的功能是：在部分票已售出的情况下，找出剧场中的R*R个空座位，要求这些座位的排列形成一个正方形。若找到满足要求的一个座位排列，则函数返回1，并算出该正方形左上角的行、列号；若未找到，返回0；
　　例如，一个7×7个座位的剧场如下图(a)所示，已售出部分座位的剧场如下图(b)所示，图中阴影部分表示已售出的座位，从图(b)中找出3×3正方形空座位如图(c)中斜线区所示。


int Find ( int a[][N] , int R , int *row , int *col )
{ 
　int i,j,k,c,t; int FOUND = 0;
　for ( i=0 ; !FOUND && i<N-R+1;i++ ) { /* 从第0排开始查找 */
　　__(1)__ ;
　　while ( j <N-R+1 && !FOUND ) {
　　　for ( k=0; ___(2)___ && a[i][j+k] = = 0; k++)；/* 查找第i排连续的R个空座位 */
　　　if ( k >=R ){ /* 查找第i排连续的R个空座位 */
　　　　for ( c=0 ; c < R ; c++ ) { /* 查找其余的R*(R-1)个座位 */
　　　　　for ( t = 1 ; t < R ; t++ )
　　　　　　if (a[ __(3)__ ] [j+c] !=0 ) break;
　　　　　if ( t <R ) break;
　　　　} /* for */
　　　　if ( ___(4)___ ) FOUND =1;
　　　} /* if */
　　　___(5)___ ;
　　} /* while */
　} /* for i */
　if ( FOUND ) {
　　*row = i-1 ; *col = j-1; /* 计算正方形区域的左上角坐标*/
　　return 1;
　}
　return 0;
}

参考答案：
(1) j = 0
(2) k<R
(3) i+t
(4) c==R
(5) j++

能帮忙解释一下吗？

14 个解决方案

#1

挺容易懂的吧，除了有点乱

#2

int Find ( int a[][N] , int R , int *row , int *col ) 
{  
　int i,j,k,c,t; int FOUND = 0; 
　for ( i=0 ; !FOUND && i <N-R+1;i++ ) { /* 从第0排开始查找 */ 
　　__(1)__ ; 
　　while ( j  <N-R+1 && !FOUND ) { 
　　　for ( k=0; ___(2)___ && a[i][j+k] = = 0; k++)；/* 查找第i排连续的R个空座位 */ 
　　　if ( k >=R ){ /* 查找第i排连续的R个空座位 */ 
　　　　for ( c=0 ; c  < R ; c++ ) { /* 查找其余的R*(R-1)个座位 */ 
　　　　　for ( t = 1 ; t  < R ; t++ ) 
　　　　　　if (a[ __(3)__ ] [j+c] !=0 ) break; 
　　　　　if ( t  <R ) break; 
　　　　} /* for */ 
　　　　if ( ___(4)___ ) FOUND =1; 
　　　} /* if */ 
　　　___(5)___ ; 
　　} /* while */ 
　} /* for i */ 
　if ( FOUND ) { 
　　*row = i-1 ; *col = j-1; /* 计算正方形区域的左上角坐标*/ 
　　return 1; 
　} 
　return 0; 
} 

#3

这个程序有点乱，但是还是可以看得懂的
首先你要明白命题人所采用的解题方法和思路

这个问题 的代码采用的逐行扫描的方式枚举所有的可以形成方形的位置
虽然算法不太好但是应该算是比较好理解的

#4

我也想知道，正在找這方面的資料~~~~~

#5

学习ing

#6

看不懂...

#7

int Find ( int a[][N] , int R , int *row , int *col ) 
{  
　int i,j,k,c,t; int FOUND = 0; 
　for ( i=0 ; !FOUND && i <N-R+1;i++ ) { /* 从第0排开始查找 */ 
　　j = 0; //从第0列开始找
　　while ( j  <N-R+1 && !FOUND ) { 
　　　for ( k=0; k <R && a[i][j+k] = = 0; k++)；/* 查找第i排连续的R个空座位 */ 
　　　if ( k >=R ){ /* 查找第i排连续的R个空座位 */ 
　　　　for ( c=0 ; c  < R ; c++ ) { /* 查找其余的R*(R-1)个座位 用c作为列来遍历找到的一排大于R个空座*/ 
　　　　　for ( t = 1 ; t  < R ; t++ ) //用t遍历排
　　　　　　if (a[ i+t ] [j+c] !=0 ) break;//a[t][c]是当前点的相对坐标，a[ i+t ] [j+c]为绝对坐标
　　　　　if ( t <R ) break; 
　　　　} /* for */ 
　　　　if ( c==R ) FOUND =1; 
　　　} /* if */ 
　　　j++; 
　　} /* while */ 
　} /* for i */ 
　if ( FOUND ) { 
　　*row = i-1 ; *col = j-1; /* 计算正方形区域的左上角坐标*/ 
　　return 1; 
　} 
　return 0; 
} 

#8

说说那里看不懂啊 
还是把C学懂了吧
这样会好点的啊

#9

哎  自以为学得还可以了
但原来还差很多很多  
我是自学的   不知道该怎么更进一步了
请指教

#10

多上机实践，独立编出程序，

#11

原来这就是传说中的程序员考试。

#12

引用 11 楼 lin_style 的回复:

原来这就是传说中的程序员考试。

跟普通的计算机三级没啥区别啊。。

#13

幸好今年没有参加，不然又要多出几十块钱了（往年也参加过，但是没有过）。

#14

不懂.