分类： C/C++
2007-08-22 17:57:24
三．问题求解（共2题，每题5分，共计10分）
1. 75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。
2. 已知a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“a b”开头写出你的安排方案： 。
四．阅读程序（共4题，每题8分，共计32分）
1．#include
int main(){
int u[4], a, b, c, x, y, z;
scanf("%d %d %d %d", &(u[0]), &(u[1]), &(u[2]), &(u[3]));
a = u[0] + u[1] + u[2] + u[3] - 5;
b = u[0] * (u[1] - u[2] / u[3] + 8);
c = u[0] * u[1] / u[2] * u[3];
x = (a + b + 2) * 3 - u[(c + 3) % 4];
y = (c * 100 - 13) / a / (u[b % 3] * 5);
if ((x + y) % 2 == 0) z = (a + b + c + x + y) / 2;
z = (a + b + c – x - y) * 2;
printf("%d\n", x + y - z);
return 0;
}
输入：2 5 7 4
输出： 。
2．#include
int number, ndata, data[100], sum;
void solve(int s, int sign, int n){
int i;
for (i = s; i < ndata; i++){
sum += sign * (number / n / data[i]);
solve(i + 1, -sign, n * data[i]);
}
}
int main(){
int i;
scanf("%d %d", &number, &ndata);
sum = 0;
for (i = 0; i < ndata; i++) scanf("%d", &(data[i]));
solve(0, 1, 1);
printf("%d\n", sum);
return 0;
}
输入：1000 3 5 13 11
输出： 。
3．#include
char c[3][200];
int s[10], m, n;
void numara(){
int i, j, cod, nr;
for (j = 0; j < n; j++){
nr = 0; cod = 1;
for (i = 0; i < m; i++){
if (c[i][j] == '1'){
if (!cod){cod = 1; s[nr]++; nr = 0;}
}
else{
if (cod){nr = 1; cod = 0;}
else nr++;
}
}
if (!cod) s[nr]++;
}
}
int main(){
int i, j;
scanf("%d %d\n", &m, &n);
for (i = 0; i < m; i++) gets(c[i]);
numara();
for (i = 1; i <= m; i++)
if (s[i] != 0) printf("%d %d ", i, s[i]);
return 0;
}
输入：
3 10
1110000111
1100001111
1000000011
输出： 。
4．#include
const int u[3] = {1, -3, 2};
const int v[2] = {-2, 3};
int g(int n){
int i, sum = 0;
for (i = 1; i <= n; i++) sum += u[i % 3] * i;
return sum;
}
int main(){
int n, i, sum = 0;
scanf("%d", &n);
for (i = 1; i <= n; i++) sum += v[i % 2] * g(i);
printf("%d\n", sum);
return 0;
}
输入：103
输出： 。
五．完善程序 (前5空，每空2分，后6空，每空3分，共28分)
1．Joseph
题目描述:
原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是1的人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此反复直到所有的人全部出列为止。比如当n=6，m=5的时候，出列的顺序依次是5，4，6，2，3，1。
现在的问题是：假设有k个好人和k个坏人。好人的编号的1到k，坏人的编号是k+1到2k。我们希望求出m的最小值，使得最先出列的k个人都是坏人。
输入:
仅有的一个数字是k（0 < k <14）。
输出:
使得最先出列的k个人都是坏人的m的最小值。
输入样例:
4
输出样例:
30
程序：
#include
long k, m, begin;
int check(long remain){
long result = ( ① ) % remain;
if ( ② ){
begin = result; return 1;
}
else return 0;
}
int main(){
long i, find = 0;
scanf("%ld", &k);
for (m = k; ③ ; m++){
find = 1; begin = 0;
for (i = 0; i < k; i++)
if (!check( ④ )){
find = 0; break;
}
}
printf("%ld\n", ⑤ );
return 0;
}
2．逻辑游戏
题目描述:
一个同学给了我一个逻辑游戏。他给了我图1，在这个图上，每一段边界都已经进行了编号。我的任务是在图中画一条连续的曲线，使得这条曲线穿过每一个边界一次且仅穿过一次，而且曲线的起点和终点都在这整个区域的外面。这条曲线是容许自交的。
对于图1，我的同学告诉我画出这样的一条曲线（图2）是不可能的，但是对于有的图形（比如图3），画出这样一条曲线是可行的。对于给定的一个图，我想知道是否可以画出满足要求的曲线。
|
|
|
|
图1 |
图2 |
|
|
|
|
图3 |
图4 |
输入:
输入的图形用一个n×n的矩阵表示的。矩阵的每一个单元里有一个0到255之间（包括0和255）的整数。处于同一个区域的单元里的数相同，相邻区域的数不同（但是不相邻的区域里的数可能相同）。
输入的第一行是n（0
输出:
当可以画出满足题意的曲线的时候，输出“YES”；否则，输出“NO”。
输入样例:
3
1 1 2
1 2 2
1 1 2
输出样例:
YES
程序：
#include
#include
int orig, n, ns, a[102][102], bun;
int d[]={1, 0, -1, 0, 0, 1, ① };
void plimba(int x, int y){
int i, x1, y1;
a[x][y] = -a[x][y];
if (abs(a[x - 1][y]) != orig && ( ② != a[x - 1][y]
|| abs(a[x][y - 1]) != orig)) ns++;
if (abs(a[x + 1][y]) != orig && (a[x + 1][y - 1] != a[x + 1][y]
|| abs(a[x][y - 1]) != orig)) ns++;
if (abs(a[x][y - 1]) != orig && ( ③ != a[x][y - 1]
|| abs(a[x - 1][y]) != orig)) ns++;
if (abs(a[x][y + 1]) != orig && (a[x - 1][y + 1] != a[x][y + 1]
|| abs(a[x - 1][y]) != orig)) ns++;
for (i = 0; i < 4; i++){
x1 = x + d[2 * i]; y1 = y + ④ ;
if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= n && ⑤ )
plimba(x1, y1);
}
}
int main(){
int i, j;
bun = 1;
scanf("%d", &n);
for (i = 0; i <= n+1; i++)
for (j = 0; j <= n+1; j++) a[i][j] = 0;
a[0][0] = -1; a[n + 1][0] = -1;
a[0][n + 1] = -1; a[n + 1][n + 1] = -1;
for (i = 1; i <= n; i++)
for ( j = 1; j <= n; j++) scanf("%d", &(a[i][j]));
for (i = 1; i <=n ; i++)
for (j = 1; j <= n; j++){
if (a[i][j] > -1){
ns = 0; ⑥ ;
plimba(i, j);
if (ns % 2 == 1)bun = 0;
}
}
if (bun) printf("YES\n"); else printf("NO\n");
return 0;
}
