2012年北京航空航天大学上机题
发布时间
阅读量：
阅读量
**第一题：分解整数
某些整数能分解成若干个连续整数的和的形式，例如
15 = 1 + 2＋3＋4＋5
15 = 4 + 5 + 6
15 = 7 + 8
某些整数不能分解为连续整数的和，例如：16
输入：一个整数N（N <= 10000）
输出：整数N对应的所有分解组合，按照每个分解中的最小整数从小到大输出，每个分解占一行，每个数字之间有一个空格（每行最后保留一个空格）；如果没有任何分解组合，则输出NONE。
样例输入：
15
16
样例输出：
1 2 3 4 5
4 5 6
7 8
**
NONE
/********************************* * Date：2013-3-18
* Author：ks_is_fighting
* Summary：1、flag,sum是在循环中使用的变量，每次循环前都必须初始化，要放对位置！
* 2、break跳出当前循环（for/while都可以），双重循环时就跳出一层，不用怀疑了！
**********************************/
#include <stdio.h>
int main ()
{
int n, i, j, k, flag, sum;
while (scanf ("%d", &n) != EOF)
{
flag = 0;
for (i = 1; i < n; i ++)
{
sum = 0;
for (j = i; j < n; j ++)
{
sum = sum + j;
if (sum == n)//分解成功
{
for (k = i ; k <= j; k ++)
{
flag = 1;
printf ("%d ", k);
}
printf("\n");
}
else if (sum > n)//分解失败,进行下一次分解
break;
}
}
if (flag == 0)
printf ("NONE\n");
}
return 0;
}**第二题：小岛面积
1 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 0
1 1 0 1 1 1
0 1 0 1 0 0
1 1 1 1 1 1
上面矩阵的中的1代表海岸线，0代表小岛。求小岛面积（即被1中包围的0的个数）。注意：仅求这样的0，该0所在行中被两个1包围，该0所在列中被两个1包围。
输入：第一行输入一个整数N，表示输入方阵的维数
输入一个N维方阵
输出：小岛面积
样例输入：
6
1 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 0
1 1 0 1 1 1
0 1 0 1 0 0
1 1 1 1 1 1
样例输出：
**
8
/********** **理解题目意思，对于矩阵中的0是否属于内陆，取决于该0所处的行和列上，如0满足如下条件则O为内陆，否则不是。
**(1)0所在的行，0的左边和右边必须有1
**(2)0所在的列，0的上面和下面必须有1
**所以，解题思路就是，遍历所有的行和列，记录该行或列，最左和最右（或者最上和最下）1的坐标
**然后遍历数组，当遇到0，判断是否处于记录的值的中间，是，则是内陆，面积加1，否则不加。
***********/
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int i, j, n, area, flag0, flag1;
while (scanf ("%d", &n) != EOF)
{
area = 0;
int** array = (int**)malloc(sizeof(int*)*n);
int** loc0 = (int**)malloc(sizeof(int*)*n);
int** loc1 = (int**)malloc(sizeof(int*)*n);
for (i = 0; i < n; i ++)
{
array[i] = (int*)malloc(sizeof(int)*n);
loc0[i] = (int*)malloc(sizeof(int)*2);
loc1[i] = (int*)malloc(sizeof(int)*2);
}
for (i = 0; i < n; i ++)
{
for (j = 0; j < n; j ++)
{
scanf ("%d", &array[i][j]);
}
}
for (i = 0; i < n; i ++)
{
for (j = 0; j < 2; j ++)
{
loc0[i][j] = loc1[i][j] = 0;
}
}
//找到每行每列最边上的1，然后遍历数组，判断0是否在此区间上
//行优先遍历,保存最左最有1的位置，为1的列坐标
for (i = 0; i < n; i ++)
{
flag0 = 0;//没找到最左的1
flag1 = 0;//没找到最右的1
for (j = 0; j < n; j ++)
{
if (flag0 == 0 && array[i][j] == 1)
{
flag0 = 1;
loc0[i][0] = j;//某行碰到的最左边的0，保存列坐标
}
if (flag1 == 0 && array[i][n - j - 1] == 1)
{
flag1 = 1;
loc0[i][1] = n - j - 1;//某行碰到的最右边的0，保存列坐标
}
}
}
//列优先遍历
for (j = 0; j < n; j ++)
{
flag0 = 0;//没找到最上的1
flag1 = 0;//没找到最下的1
for (i = 0; i < n; i ++)
{
if (flag0 == 0 && array[i][j] == 1)
{
flag0 = 1;
loc1[j][0] = i;//某列碰到的最上的1，保存行坐标
}
if (flag1 == 0 && array[n - i -1][j] == 1)
{
flag1 = 1;
loc1[j][1] = n - i - 1;//某列碰到的最下的1，保存行坐标
}
}
}
for (i = 0; i < n; i ++)
{
for (j = 0; j < n; j ++)
{
if (array[i][j] == 0)
{
if (j > loc0[i][0] && j < loc0[i][1] && i > loc1[j][0] && i < loc1[j][1])
{
area = area + 1;
}
}
}
}
printf ("%d\n", area);
}
return 0;
}全部评论 (0)
还没有任何评论哟~