主题:入门必做的题
GCC
[专家分:14380] 发布于 2006-04-14 11:53:00
1. 给定等式 A B C D E 其中每个字母代表一个数字,且不同数字对应不
D F G 同字母。编程求出这些数字并且打出这个数字的
+ D F G 算术计算竖式。
───────
X Y Z D E
2. A、B、C、D、E五名学生有可能参加计算机竞赛,根据下列条件判断哪些
人参加了竞赛:
(1)A参加时,B也参加;
(2)B和C只有一个人参加;
(3)C和D或者都参加,或者都不参加;
(4)D和E中至少有一个人参加;
(5)如果E参加,那么A和D也都参加。
3. 打印一个 N*N 的方阵,N为每边 N=15 打印出下面图形
字符的个数(3<N<20), 要求最 TTTTTTTTTTTTTTT
外一层为"T", 第二层为"J", 从第三层 TJJJJJJJJJJJJJT
起每层依次打印数字 1,2,3,... TJ11111111111JT
(右图以N为15为例) TJ12222222221JT
TJ12333333321JT
TJ12344444321JT
TJ12345554321JT
TJ12345654321JT
TJ12345554321JT
TJ12344444321JT
TJ12333333321JT
TJ12222222221JT
TJ11111111111JT
TJJJJJJJJJJJJJT
TTTTTTTTTTTTTTT
4. 在N行N列的数阵中, 数K(1〈=K〈=N)在每行和每列中出现且仅
出现一次,这样的数阵叫N阶拉丁方阵。例如下图就是一个五阶拉丁方阵。
编一程序,从键盘输入N值后,打印出所有不同的N阶拉丁方阵,并统计个数。
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
5. 输入一个十进数,将其转换成 N 进制数(0<N<=16)。
回复列表 (共635个回复)
171 楼
iuhiao [专家分:1330] 发布于 2006-05-13 20:33:00
to machh
可能是中英文输入法的问题,你自己输入一下看行不行
帖上来的一般不会有什么问题的
172 楼
gdufslin [专家分:30] 发布于 2006-05-14 11:00:00
55楼的还真是牛人啊!那么多的循环我以为要很多时间,想不到运行起来比想象的快的多了!
173 楼
cokeone [专家分:30] 发布于 2006-05-14 14:20:00
第一题太夸张了。这是个虫食算式,一般的做法时间复杂度很高。下面给个官方的解法:
虫食算
【解题报告】
给出一个N进制的虫食算式,相同的字母代表相同的数字,不同的字母代表不同的数字。要求求出满足这个算式的唯一一组解,也就是字母和数字的一一对应关系.
解决方案1:
要求一一对应的关系,就可以枚举这些一一对应的关系,找出符合的一项。这样,关系总数有O(N!)个,最坏情况下必须枚举所有的关系,并且加以判断,复杂度高达O(N*N!)!
解决方案2:
大体上,从算式最后一位开始模拟运算情况,当可递推时递推,不可递推则枚举。
对于一竖列,先处理两个加数,当遇到的字母的值不确定时,则枚举当前位(注意与前面的情况判重);否则不作为。后处理和,当遇到的字母的值不确定时,可从加数部分确定的值来确定(注意与前面的情况判重和进位);否则看加数部分确定的值是否能得到和部分(注意进位)。引出矛盾就回溯。
如题目的样例:
5
ABCED
BDACE
EBBAA
它最后一位的情况是(D+E) mod N=A, 对于最后一位只要枚举D,E的情况;A 则可以由D,E的值递推而来。对于倒2位, (D+C+最后一位进位) mod N=A ;D的值可以用前面的结果;枚举C;判断A是否为(D+C+最后一位进位) mod N……
虽然复杂度还是O(N!),但这种方法限制很多(相当于剪枝)。
解决方案3:
观察题目的条件已经限制得很苛刻:N个变量,每个至少出现一次;而且正好一共有N位的算式。这样就构成了解方程的动机。这N个变量的对应N个未知量,有N位的算式对应N个方程;N个未知量,N个方程,正好可以得到唯一解。这里要注意,对解的要求很严格:必须是0至N-1的每个整数都正好出现一次。
但对每位式子的进位关系并不清楚,而进位关系正好影响了方程的常数项。枚举每位是否进位。用时 (因为首位不可能进位,无须枚举)。然后,用高斯消元法来解方程。可以在枚举之前先解出方程,枚举的时候再把参数带入。带入求解的复杂度是 。
解决方案4:
在解决方案3的基础上,我们可以对进位的枚举剪枝。观察这个竖列:A+B=C,若无进位则有A<=C且B<=C; 若有进位则有A=>C且B>=C.
若能推导出A<=B 且B>=A (A,B为任何不相等字母),则当前的枚举不可行。可用递归枚举,从后向前枚举,处理一个竖列时则加上2个不等式,看是否矛盾。数据结构用邻接矩阵。(规定A<=B,再有向图中有边<A,B>)。
例子若加进不等式A>=B ,要加入所有x(x>=A) >=y(B>=y),枚举x,y用O(n^2)得时间。再判断是否有x<=y 且x>=y.
对比这题,解法3无效,而且也不知道这个官方算法的代码实现。GCC大大,这个第一题都这么夸张了怎么循序渐进呀?
174 楼
eastcowboy [专家分:25370] 发布于 2006-05-14 18:28:00
19. (背包问题) 有 N 件物品 d1,......dN,每件物品重量为 W1,..., WN
(Wi > 0), 每件物品价值为 V1,......VN (Vi>0)。用这N件物品的某个子集
填空背包,使得所取物品的总重量<=TOTAL,并设法使得背包中物品的价值尽可
能高。
19.解答:
#include<stdio.h>
#define MAX_N 10
#define MAX_WEIGHT 20
#define MAX_VALUE 20
void bag(const int Weight[], const int Value[], const int n, const int TotalWeight)
{
int ValueReached[MAX_VALUE*MAX_N+1] = {0};
int WeightUsed[MAX_VALUE*MAX_N+1];
int LastUseIndex[MAX_VALUE*MAX_N+1];
int i,j;
const int INF = 10000000;
for(i=0; i<=MAX_VALUE*MAX_N; ++i)
WeightUsed[i] = INF;
ValueReached[0] = 1; // 记录价值为i是否可达到
WeightUsed[0] = 0; // 记录达到价值i时使用的重量
LastUseIndex[0] = -1; // 记录达到价值i所使用物品的最后一个的下标
for(i=0; i<n; ++i)
{
int w = Weight[i];
int v = Value[i];
for(j=MAX_VALUE*MAX_N-v; j>=0; --j)
{
if( !ValueReached[j] )
continue;
if( WeightUsed[j]+w > TotalWeight )
continue;
if( (!ValueReached[j+v]) || (WeightUsed[j+v]>WeightUsed[j]+w) )
{
ValueReached[j+v] = 1;
LastUseIndex[j+v] = i;
WeightUsed[j+v] = WeightUsed[j] + w;
}
}
}
for(i=MAX_VALUE*MAX_N; /*i>=0*/; --i)
if(ValueReached[i])
break;
printf("可装入物品总价值为%d\n", i);
printf("装入了以下物品:\n");
// 注意:输出的顺序是“反”的,如果要“正”的,需另外处理
j=LastUseIndex[i];
while( j != -1 )
{
printf("第%d件\t", j+1);
i -= Value[j];
j = LastUseIndex[i];
}
printf("\n");
}
int main(void)
{
int i;
int TotalWeight,n;
int w[MAX_N], v[MAX_N];
printf("输入背包可承受的最大重量:\n");
scanf("%d", &TotalWeight);
printf("输入物品的件数:\n");
scanf("%d", &n);
for(i=0; i<n; ++i)
{
printf("输入第%d件物品的重量:\n", i+1);
scanf("%d", w+i);
printf("输入第%d件物品的价值:\n", i+1);
scanf("%d", v+i);
}
bag(w, v, n, TotalWeight);
return 0;
}
175 楼
eastcowboy [专家分:25370] 发布于 2006-05-14 18:29:00
20. (N皇后) 在国际象棋的棋盘上放置N个皇后,使其不能互相攻击,即任意
两个皇后不能处在棋盘的同一行,同一列,同一斜线上,试问共有多少种摆法?
20.解答:
#include<stdio.h>
#define MAX 20
static int N;
static int Count;
static int map[MAX];
static int used[MAX];
void Solve(int start)
{
int i,j;
if( start == N )
{
++Count;
printf("Answer #%d:\n", Count);
for(i=0; i<N; ++i)
{
for(j=0; j<map[i]; ++j)
printf("□");
printf("■");
for(j=map[i]+1; j<N; ++j)
printf("□");
printf("\n");
}
printf("\n");
return;
}
for(i=0; i<N; ++i)
{
if( used[i] )
continue;
for(j=0; j<start; ++j)
if( map[j]+j==i+start || map[j]-j==i-start )
break;
if( j<start )
continue;
used[i] = 1;
map[start] = i;
Solve(start+1);
used[i] = 0;
}
}
int main(void)
{
int i;
scanf("%d", &N);
Count = 0;
for(i=0; i<N; ++i)
used[i] = 0;
Solve(0);
return 0;
}
176 楼
eastcowboy [专家分:25370] 发布于 2006-05-14 18:37:00
21. 请设计一个程序,由计算机把1...8的八个自然数填入图中,使得横、
竖、对角任何两个相邻的小方格中的两个数是不连续的。(下图右侧的 4 个图
为禁止的情形).
┌─┐ ┌─┐ ┌─┐
│ │ │4│ │8│
┌─┼─┼─┐ └─┼─┐ ┌─┼─┘
│ │ │ │ │5│ │7│
├─┼─┼─┤ └─┘ └─┘
│ │ │ │ ┌─┐
└─┼─┼─┘ │6│ ┌─┬─┐
│ │ ├─┤ │1│2│
└─┘ │7│ └─┴─┘
└─┘
21.解答:
思路分析:把方块按下图所示编号。
┌─┐
│0│
┌─┼─┼─┐
│1│2│3│
├─┼─┼─┤
│4│5│6│
└─┼─┼─┘
│7│
└─┘
和0相邻的有:1,2,3
和1相邻的有:0,2,4,5
和2相邻的有:0,1,3,4,5,6
和3相邻的有:0,2,5,6
和4相邻的有:1,2,5,7
和5相邻的有:1,2,3,4,6,7
和6相邻的有:2,3,5,7
和7相邻的有:4,5,6
由此得到一个二维数组:(-1表示结束)
static int Neighbor[8][7] =
{
{1,2,3,-1},
{0,2,4,5,-1},
{0,1,3,4,5,6,-1},
{0,2,5,6,-1},
{1,2,5,7,-1},
{1,2,3,4,6,7,-1},
{2,3,5,7,-1},
{4,5,6,-1}
};
如果按照0,1,2,3,4,5,6,7的顺序放数字,则先放的不需要考虑是否和后放的冲突,只需要后放的去考虑是否与先放的冲突。
所以原数组可减掉一部分,变为:
static int Neighbor[8][7] =
{
{-1},
{0,-1},
{0,1,-1},
{0,2,-1},
{1,2,-1},
{1,2,3,4,-1},
{2,3,5,-1},
{4,5,6,-1}
};
利用递归可写出程序如下:
#include<stdio.h>
static int Neighbor[8][7] =
{
{-1},
{0,-1},
{0,1,-1},
{0,2,-1},
{1,2,-1},
{1,2,3,4,-1},
{2,3,5,-1},
{4,5,6,-1}
};
static int map[8];
static int used[8];
static int count;
void Print()
{
printf("Answer #%d:\n", count);
printf(
" ┌─┐\n"
" │%2d│\n"
"┌─┼─┼─┐\n"
"│%2d│%2d│%2d│\n"
"├─┼─┼─┤\n"
"│%2d│%2d│%2d│\n"
"└─┼─┼─┘\n"
" │%2d│\n"
" └─┘\n",
map[0], map[1], map[2], map[3],
map[4], map[5], map[6], map[7]);
printf("\n");
}
void Solve(int start)
{
int i,j;
if( start == 8 )
{
++count;
Print();
return;
}
for(i=0; i<8; ++i)
{
if( used[i] )
continue;
j = 0;
while( Neighbor[start][j] != -1 )
{
int tmp = map[Neighbor[start][j]] - 1;
if( tmp==i+1 || tmp==i-1 )
break;
++j;
}
if( Neighbor[start][j] != -1 )
continue;
used[i] = 1;
map[start] = i+1;
Solve(start+1);
used[i] = 0;
}
}
int main(void)
{
count = 0;
Solve(0);
return 0;
}
运行结果:
Answer #1:
┌─┐
│ 2│
┌─┼─┼─┐
│ 5│ 8│ 6│
├─┼─┼─┤
│ 3│ 1│ 4│
└─┼─┼─┘
│ 7│
└─┘
Answer #2:
┌─┐
│ 2│
┌─┼─┼─┐
│ 6│ 8│ 5│
├─┼─┼─┤
│ 4│ 1│ 3│
└─┼─┼─┘
│ 7│
└─┘
Answer #3:
┌─┐
│ 7│
┌─┼─┼─┐
│ 3│ 1│ 4│
├─┼─┼─┤
│ 5│ 8│ 6│
└─┼─┼─┘
│ 2│
└─┘
Answer #4:
┌─┐
│ 7│
┌─┼─┼─┐
│ 4│ 1│ 3│
├─┼─┼─┤
│ 6│ 8│ 5│
└─┼─┼─┘
│ 2│
└─┘
177 楼
wwc160 [专家分:0] 发布于 2006-05-14 20:50:00
好题
178 楼
shui228112 [专家分:10] 发布于 2006-05-14 21:59:00
好难呀!
对于我来说!!
179 楼
yueming [专家分:60] 发布于 2006-05-15 17:52:00
14题
main()
{
int n,i,j,temp;
int *a;
scanf(" %d",&n);
a=(int *)malloc(sizeof(int)*n*2);
for(i=0;i<n;i++)
*(a+i)=0;
for(;i<2*n;i++)
*(a+i)=1;
if(n%2==0)
for(i=1,j=n;i<n;i+=2,j+=2)
{
temp=*(a+i);
*(a+i)=*(a+j);
*(a+j)=temp;
}
else
for(i=1,j=n+1;i<n;i+=2,j+=2)
{
temp=*(a+i);
*(a+i)=*(a+j);
*(a+j)=temp;
}
for(i=0;i<n*2;i++)
printf(" %d",*(a+i));
printf("\n");
}
180 楼
zy1121 [专家分:7950] 发布于 2006-05-16 10:44:00
9. 四人玩火柴棍游戏,每一次都是三个人赢,一个人输。输的人要按赢者手中的火柴
数进行赔偿,即赢者手中有多少根火柴棍,输者就赔偿多少根。现知道玩过四次后, 每人恰好输过一次, 而且每人手中都正好有16根火柴。问此四人做游戏前手中各有 多少根火柴? 编程解决此问题
#include <stdio.h>
int main()
{
int arr[4]={16,16,16,16},i,j;
for(j=3;j>=0;j--)
for(i=0;i<=3;i++)
if(i!=j){arr[i]/=2;arr[j]+=arr[i];}
for(i=0;i<=3;i++)printf("%d ",arr[i]);
getch();
return 0;
}
我来回复