主题：[讨论]GCC入门题部分题目解答
wuchengwei
[专家分：1650] 发布于 2006-11-03 03:44:00
以下程序在VC6.0环境下测试通过
若出现程序编译不了，或需要注释的，可以加Q634419082
//////////////////////////////////////////////////////////////////////////////
//
// 1. 给定等式 A B C D E 其中每个字母代表一个数字，且不同数字对应不
// D F G 同字母。编程求出这些数字并且打出这个数字的
// / + D F G 算术计算竖式。
// ───────
// X Y Z D E
//////////////////////////////////////////////////////////////////////////////
//
// (DE+FG+FG)%100 = DE -> FG = 50
// Z = (C+D+D+1)%10
// Y = ((C+D+D+1)/10 + B)%10 && Y != 0 && Z != 0
// -> B == 9 && C +D +D +1 > 20 -> C >= 5 && D >= 5
// X != A ->X = A+1
// E = 45 - (A +9 + C +D +E + 5 +0 +X +Y +Z) = 31 - A -C -D -E -X -Y -Z
/////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
void main()
{
unsigned int a, c, d, e, x, y, z;
printf("%10s\n", "A B C D E");
printf("%10s\n", "D F G");
printf("+%9s\n", "D F G");
printf("%10s\n", "───────");
printf("%10s\n\n\n", "X Y Z D E");
for(a = 1; a < 9; a++)
{
if(a == 5)
continue;
for(c = 5; c < 9; c++)
{
if(c == a )
continue;
for(d = 5; d < 9; d++)
{
if(d == a || d == c)
continue;
x = a +1;
y = ((c +2*d +1)/10 + 9)%10;
z = (c +2*d +1)%10;
e = 31-a-c-d-x-y-z;
if(x != a && y != a && z != a && e != a
&& x != 9 && y != 9 && z != 9 && e != 9
&& x != c && y != c && z != c && e != c
&& x != d && y != d && z != d && e != d
&& x != 5 && y != 5 && z != 5 && e != 5
&& x != 0 && y != 0 && z != 0 && e != 0
&& x != y && x != z && x != e && y != z
&& y != e && z != e
&& 10000*a +9000 +100*c +10*d +e +2*(100*d +50)
== 10000*x +1000*y +100*z +10*d +e)
{
printf("%2d%2d%2d%2d%2d\n", a, 9, c, d, e);
printf("%*d%2d%2d\n", 6, d, 5, 0);
printf("+%*d%2d%2d\n", 5, d, 5, 0);
printf("%10s------------\n", "------------");
printf("%2d%2d%2d%2d%2d\n", x, y, z, d, e);
}
}
}
}
}
最后更新于：2007-06-01 02:37:00
回复列表 （共144个回复）
31 楼
wuchengwei [专家分：1650] 发布于 2006-09-05 21:57:00
//////////////////////////////////////////////////////////////////////////////
//
// 71. (最长连线) 设有一个 N×N 的方格图形，且 N 为 3 的倍数。要求在图形中
// 存放 0 或 1，相邻的 1 可以连成一条连线，连接的方法可以是行，也可以是列；
// 同时约定一条连线只能有一个起点和一个终点，图形上的点最多只能访问一次。
// 编程求最长连线. 例如 N＝6 时，有下图：
// １ ２ ３ ４ ５ ６
// ┌─┬─┬─┬─┬─┬─┐
// １ │１│１│１│０│０│１│
// ├─┼─┼─┼─┼─┼─┤
// ２ │１│１│０│１│１│１│
// ├─┼─┼─┼─┼─┼─┤
// ３ │０│０│０│１│０│１│
// ├─┼─┼─┼─┼─┼─┤
// ４ │１│１│０│１│１│１│
// ├─┼─┼─┼─┼─┼─┤
// ５ │０│１│０│０│０│０│
// ├─┼─┼─┼─┼─┼─┤
// ６ │１│１│１│１│０│０│
// └─┴─┴─┴─┴─┴─┘
// 在该图中，包含有如下的一些连线：
// １←１←１ １←１ １
// ↓ ↓ ↓
// １→１ １ １→１ １
// ↓ ↑ ↓
// １→１→１ １ １
// ↑ ↓
// １←１←１
// 在以上的连线中，最长的连线为： 表示方法：
// １ 最长连线长度：LMAX=9
// ↓ 连线：(1,6)→(2,6)→
// １→１ １ (3,6)→(4,6)→
// ↑ ↓ (4,5)→(4,4)→
// １ １ (3,4)→(2,4)→
// ↑ ↓ (2,5)
// １←１←１ 连线的表示不是唯一的，仅给出一种即可。
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define N 9 // N%3 == 0
typedef struct
{
bool cando;
bool used;
}elemtype;
elemtype maze[N][N];
typedef struct
{
unsigned int i;
unsigned int j;
}postype;
32 楼
wuchengwei [专家分：1650] 发布于 2006-09-05 21:57:00
void initmaze(elemtype maze[][N])
{
srand((unsigned)time(NULL));
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
maze[i][j].cando = (bool)(rand()%2);
maze[i][j].used = 0;
printf("%d\t", maze[i][j].cando);
}
printf("\n\n");
}
}
void next_pos(postype curpos, postype &nextpos, int dir)
{
switch (dir){
case 1:
nextpos.i = curpos.i;
nextpos.j = curpos.j+1;
break;
case 2:
nextpos.i = curpos.i+1;
nextpos.j = curpos.j;
break;
case 3:
nextpos.i = curpos.i;
nextpos.j = curpos.j-1;
break;
default:
nextpos.i = curpos.i-1;
nextpos.j = curpos.j;
}
}
bool islegal(postype pos)
{
if( pos.i >= N || pos.j >= N
||!maze[pos.i][pos.j].cando
||maze[pos.i][pos.j].used)
return false;
return true;
}
void find_line(postype curpos, postype* line, int &len)
{
postype nextpos;
if(islegal(curpos))
{
line[len].i = curpos.i;
line[len++].j = curpos.j;
maze[curpos.i][curpos.j].used = 1;
for(int i = 1; i <= 4; i++)
{
next_pos(curpos, nextpos, i);
find_line(nextpos, line, len);
}
}
}
void main()
{
int i, j, k, len;
postype line[50], start;
initmaze(maze);
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
{
start.i = i;start.j = j;len = 0;
find_line(start, line, len);
if(len)
{
for(k = 0; k < len; k++)
printf("<%d,%d>\t", line[k].i, line[k].j);
printf("\n\n");
}
}
}
33 楼
wuchengwei [专家分：1650] 发布于 2006-09-05 21:59:00
第十二题按书上做的，不会求最短路径
//////////////////////////////////////////////////////////////////////////////
//
// 12. 下图是一个集装箱仓库，阴影部分表示有集装箱存放不能通过，无阴影处为临时通
// 道。当有人要从入口处到达出口处时，必须寻找可通过路线，请你找出可完成这个过程
// 的最方便（即用最短路线）到达出口处的路径。
//
// ┎┰┰┰入口┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┒
// ┠╂╂╂──╂╂╂╂┸┸╂┸┸╂┸┸╂┸┸╂╂╂╂┸┸╂╂╂┨
// ┠╂╂╂──╂┸┸╂──╂┰┰╂┰┰╂──╂╂╂╂──╂╂╂┨
// ┠╂╂╂──╂┰┰╂┰┰╂╂╂╂╂╂╂──╂┸┸╂──╂╂╂┨
// ┠╂╂╂──╂╂╂╂╂╂╂╂╂╂╂╂╂┰┰╂┰┰╂┰┰╂╂╂┨
// ┠╂╂╂──╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂╂╂┨
// ┠╂╂╂──╂┰┰╂┰┰╂┰┰╂──╂┰┰╂──╂┰┰╂╂╂┨
// ┠╂╂╂──╂╂╂╂╂╂╂╂╂╂──╂╂╂╂──╂╂╂╂╂╂┨
// ┠╂╂╂──╂╂╂╂┸┸╂┸┸╂──╂╂╂╂──╂┸┸╂╂╂┨
// ┠╂╂╂──╂╂╂╂┰┰╂┰┰╂┰┰╂╂╂╂┰┰╂──╂╂╂┨
// ┖┸┸┸──┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸出口┸┸┸┚
///////////////////////////////////////////////////////////////////////////////迷宫是随机生成的，题目给的图看不大懂
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#include "time.h"
#define MAZE_SIZE 10 //MAZE_SIZE < 16
#define MAX_LENGTH 50
typedef struct{
unsigned int i;
unsigned int j;
}postype;
postype nextpos(postype curpos, int di){
postype pos;
switch (di){
case 1:
pos.i = curpos.i;
pos.j = curpos.j+1;
break;
case 2:
pos.i = curpos.i+1;
pos.j = curpos.j;
break;
case 3:
pos.i = curpos.i;
pos.j = curpos.j-1;
break;
default:
pos.i = curpos.i-1;
pos.j = curpos.j;
}
return pos;
}
typedef struct{
postype pos;
char type; //false--path true--wall
bool used;
}mazeelem;
void initmaze(mazeelem maze[][MAZE_SIZE]){
srand((unsigned)time(NULL));
for(int i = 0; i < MAZE_SIZE; i++){
for(int j = 0; j < MAZE_SIZE; j++){
maze[i][j].pos.i = i;
maze[i][j].pos.j = j;
maze[i][j].used = false;
maze[i][j].type = rand()%2+48;
printf("%5c", maze[i][j].type);
}
printf("\n\n");
}
}
typedef struct{
postype pos;
int di;
}stackelem;
void createse(stackelem* e, int i, int j, int di){
e->pos.i = i;
e->pos.j = j;
e->di = di;
}
typedef struct{
stackelem *base;
stackelem *top;
}stack;
void push(stack &s, stackelem *e){
createse(s.top, e->pos.i, e->pos.j, e->di);
++s.top;
}
void pop(stack &s, stackelem *e){
createse(e, (s.top-1)->pos.i, (s.top-1)->pos.j, (s.top-1)->di);
--s.top;
}
34 楼
wuchengwei [专家分：1650] 发布于 2006-09-05 21:59:00
bool pass(mazeelem maze[][MAZE_SIZE], postype pos){
if(pos.i < MAZE_SIZE && pos.j < MAZE_SIZE
&& !maze[pos.i][pos.j].used
&& maze[pos.i][pos.j].type == '0')
return true;
return false;
}
void printpath(mazeelem maze[][MAZE_SIZE], stack s){
while(s.base != s.top){
switch (s.base->di){
case 1:
maze[(s.base)->pos.i][(s.base)->pos.j].type -= 32;break;
case 2:
maze[(s.base)->pos.i][(s.base)->pos.j].type -= 17;break;
case 3:
maze[(s.base)->pos.i][(s.base)->pos.j].type -= 31;break;
default:
maze[(s.base)->pos.i][(s.base)->pos.j].type -= 18;
}
s.base++;
}
for(int i = 0; i < MAZE_SIZE; i++){
for(int j = 0; j < MAZE_SIZE; j++)
printf("%5c", maze[i][j].type);
printf("\n\n");
}
}
void maze_path(mazeelem maze[][MAZE_SIZE], postype start, postype end){
stack s;
stackelem* e = (stackelem*)malloc(sizeof(stackelem));
s.base = s.top = (stackelem*)malloc(MAX_LENGTH*sizeof(stackelem));
postype curpos;
curpos.i = start.i;
curpos.j = start.j;
do{
if(pass(maze, curpos)){
maze[curpos.i][curpos.j].used = true;
createse(e, curpos.i, curpos.j, 1);
push(s, e);
if(curpos.i == end.i && curpos.j == end.j){
printpath(maze, s);
return;
}
curpos = nextpos(e->pos, 1);
}
else{
if(s.top != s.base){
pop(s, e);
while(e->di == 4 && s.top != s.base){
pop(s, e);
maze[e->pos.i][e->pos.j].used = true;
maze[e->pos.i][e->pos.j].type = '0';
}
if(e->di < 4){
e->di++;
push(s, e);
curpos = nextpos(e->pos, e->di);
}
}
}
}
while(s.top != s.base);
printf("NO WAY!\n");
}
void main(){
mazeelem maze[MAZE_SIZE][MAZE_SIZE];
initmaze(maze);
postype start, end;
printf("start position as format <i,j>:");
scanf("%d,%d", &start.i, &start.j);
printf("end position as format <i,j>:");
scanf("%d,%d", &end.i, &end.j);
maze_path(maze, start, end);
}
35 楼
wuchengwei [专家分：1650] 发布于 2006-09-05 22:01:00
以下几道题不知道自己的想法是不是太天真了
//////////////////////////////////////////////////////////////////////////////
//
// 37. 已知 N 个正整数满足 K1+K2+...+Kn=M。求一组最佳的分解，使得
// K1*K2*....*Kn 为最大。
// 例如：N=2时，给定 K1+K2=6,当 K1=3,K2=3 时，K1*K2=9 为最大
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "assert.h"
void main()
{
unsigned int n ,sum, mod, i;
unsigned long product =1;
printf("input N and SUM spaced by space [N <= SUM]:");
scanf("%d %d", &n, &sum);
unsigned int *a = new unsigned int[n];
assert(sum >= n);
for(i = 0; i < n; i++)
a[i] = sum/n;
mod = sum%n;
for(i = 0; i < mod; i++)
a[i] += 1;
for(i = 0; i < n; i++)
{
printf("%-5d", a[i]);
product *= a[i];
}
printf("\nthe maximal product is %ld\n", product);
}
//////////////////////////////////////////////////////////////////////////////
//
// 58. 将７万元投资到Ａ，Ｂ，Ｃ三项目上，其利润见下表：
// 投资额(万元)│ １ ２ ３ ４ ５ ６ ７
// ──────┼────────────────────
// 项 Ａ │0.11 0.13 0.15 0.24 0.24 0.30 0.35
// Ｂ │0.12 0.16 0.21 0.45 0.25 0.29 0.34
// 目 Ｃ │0.08 0.12 0.60 0.26 0.26 0.30 0.35
// 如何分配投资额，使获得的利润最大。
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
void main()
{
double a[3][8] =
{
0.00, 0.11, 0.13, 0.15, 0.24, 0.24, 0.30, 0.35,
0.00, 0.12, 0.16, 0.21, 0.45, 0.25, 0.29, 0.34,
0.00, 0.08, 0.12, 0.60, 0.26, 0.26, 0.30, 0.35
};
int x, y, m, n;
double max = 0, sum;
printf("pro\\mon\t");
for(x = 1; x <= 7; x++)
printf("%d\t", x);
for(x = 0; x < 3; x++)
{
printf("\n%c\t", x+'A');
for(y = 1; y < 8; y++)
printf("%.2f\t", a[x][y]);
}
for(x = 0; x <= 7; x++)
{
for(y = 0; y <= 7-x; y++)
{
sum = x* a[0][x] + y* *(*(a+1)+y) + (7-x-y)* a[2][7-x-y];
if(sum > max)
{
max = sum;
m = x;
n = y;
}
}
}
printf("\n\nOPTIMIZATION INVEST: A= %d B= %d C= %d\nMAX TOATAL PROFIT: %.2f\n",
m, n, 7-m-n, max*10000);
}
36 楼
wuchengwei [专家分：1650] 发布于 2006-09-05 22:01:00
//////////////////////////////////////////////////////////////////////////////
//
// 74. (NOI'95.1_5) m、n为整数，且满足下列两个条件：
// ① m、n∈｛1, 2, …, k｝, (1≤k≤109)
// ② (n^2－m*n－m^2)^2＝1
// 编一程序, 由键盘输入k, 求一组满足上述两个条件的 m、n, 并且使m^2＋n^2
// 的值最大.
// 例如, 若 k＝1995, 则 m＝987, n＝1597 时, 则 m、n 满足条件, 且可使
// m^2＋n^2的值最大.
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
void main()
{
int m, n, k;
scanf("%d", &k);
for(m = k; m >0; m--)
for(n = m+1; n <= k; n++)
if(((n+m)*(n-m)-m*n) == 1)
{
printf("m = %4d n = %4d\n", m, n);
return;
}
}
贴完了，有一半题目没做
做了的题目有的写得太复杂、冗长（8、42、43、44）
没做的有的题目是完全不会做
有的应该能磨蹭出来
所有的题目中，关于递归和回溯的题目占了很大的比率
大家能帮忙做的都做下吧
37 楼
sarrow [专家分：35660] 发布于 2006-09-05 22:07:00
顶一下！
（这可以置顶吧！）
38 楼
wshong [专家分：1880] 发布于 2006-09-06 16:18:00
楼主厉害！顶下！
39 楼
freeeerf [专家分：5440] 发布于 2006-09-08 04:08:00
好啊!
我现在也在做,嘿嘿,做完了再参考你的.
40 楼
tgbtgb [专家分：490] 发布于 2006-09-10 17:06:00
太厉害了！
我来回复
您所在位置：