主题：[讨论]请教两道题！A+B和回溯！速度！50分！
刚过桥DE米线
[专家分：0] 发布于 2011-09-29 19:41:00
1. a+b（sum.bas/ sum.pas/ sum.c）
【问题描述】
相信a+b问题对大家来说，应该不陌生了吧。给出两个整数a和b，求a和b的和。
【输入文件】
第一行一个整数N（N<100），表示求和的数字对数；
接下来N行，每行两个整数a和b。
【输出文件】
N行，每行一个数表示两个数a，b的和。
【样例输入】
1
3 5
【样例输出】
8
【数据范围】
对于70%的数据，0<=a,b<=1000；
对于100%的数据，0<=a,b<=10100。
2. 蚂蚁(ant.bas/ ant.pas/ ant.c)
【问题描述】
蚂蚁在回家路上，他的任务自然是回家。蚂蚁在一个w*h个方格的地图上。每秒钟他能向上下左右四个方向移动一格，但不能离开地图。由于蚂蚁体能有限，每秒钟他要消耗1点HP, 刚开始时他有满HP6点。他可以沿路通过进食来补满HP（即6点），只要他走到有食物的格子，他不需要任何时间即可进食完毕。一个格子上的食物量对于小蚂蚁来说是庞大的，只要他愿意，每次经过这个格子都有吃不完的食物。
一旦蚂蚁的HP降到0，他将死去，就算到了某个有食物的格子才死去，他也不能通过进食补满HP。即使再家门口死去，他也不能算完成任务回到家中。
地图上有5种格子：
数字0：表示障碍物，蚂蚁不能走到这个格子上，更不能跨越。
数字1：表示空地，蚂蚁可以自由行走
数字2：表示蚂蚁出发点，他也是一片空地。
数字3：表示蚂蚁的家。
数字4：表示有食物在上面的空地。
你能告诉蚂蚁先生他能否安全回家，如果能，最短需要多长时间呢？
【输入格式】
第一行，表示宽w和长h。
下面h行，每行w个数字来描述地图。
【输出格式】
一行，若蚂蚁不能回家，输出-1,否则输出蚂蚁回家所需最短时间。
【输入样例】
3 3
2 1 1
1 1 0
1 1 3
【样例输出】
4
【数据规模】
0<w,h<9
第一题要用高精度，我不知道如何不让时间超标
第二题要用回溯，我不会
回复列表 （共9个回复）
沙发
codepk [专家分：2800] 发布于 2011-09-30 18:05:00
第一题a+b 最多才2w多,整型的范围是正负3w多,不需要高精度吧？
DEFINT A-Z
DIM map(9, 9, 2)
DIM stack(3000, 4)
INPUT w, h
FOR i = 1 TO h
FOR j = 1 TO w
INPUT map(i, j, 1)
IF map(i, j, 1) = 2 THEN
posX = j
posY = i
END IF
NEXT
NEXT
sp = 1
min = 9999
stack(1, 1) = posY
stack(1, 2) = posX
stack(1, 3) = 0
stack(1, 4) = 6
map(posY, posX, 2) = 6
WHILE sp > 0
posY = stack(sp, 1)
posX = stack(sp, 2)
stack(sp, 3) = stack(sp, 3) + 1
way = stack(sp, 3)
hp = stack(sp, 4) - 1
IF way = 1 THEN
posY = posY - 1
ELSEIF way = 2 THEN
posX = posX - 1
ELSEIF way = 3 THEN
posY = posY + 1
ELSEIF way = 4 THEN
posX = posX + 1
ELSEIF way = 5 THEN
map(posY, posX, 2) = 0
sp = sp - 1
END IF
IF hp > 0 AND way < 5 AND posY > 0 AND posY <= h AND posX > 0 AND posX <= w THEN
stat = map(posY, posX, 1)
IF stat = 3 THEN
IF sp < min THEN min = sp
ELSEIF stat <> 0 THEN
IF stat = 4 THEN
hp = 6
END IF
lost = map(posY, posX, 2)
IF hp > lost THEN
sp = sp + 1
stack(sp, 1) = posY
stack(sp, 2) = posX
stack(sp, 3) = 0
stack(sp, 4) = hp
map(posY, posX, 2) = hp
END IF
END IF
END IF
WEND
IF min < 9999 THEN
PRINT min
ELSE
PRINT -1
END IF
板凳
幽灵密码 [专家分：3510] 发布于 2011-09-30 18:36:00
- -stack作名称很容易被误解成模拟栈的
3 楼
幽灵密码 [专家分：3510] 发布于 2011-10-01 12:31:00
原题不是10100,是10的100次方吧
4 楼
幽灵密码 [专家分：3510] 发布于 2011-10-01 13:38:00
[color=FF0000]DECLARE FUNCTION Add$ (a$, b$)
OPEN "Sum.in" FOR INPUT AS #1
OPEN "Sum.out" FOR OUTPUT AS #2
CLS
INPUT #1, n
FOR z = 1 TO n
INPUT #1, s$
p = INSTR(s$, " ")
a$ = LEFT$(s$, p - 1)
b$ = RIGHT$(s$, LEN(s$) - p)
PRINT #2, Add$(a$, b$)
NEXT z
CLOSE
END
FUNCTION Add$ (a$, b$)
la = LEN(a$)
lb = LEN(b$)
IF la < lb THEN SWAP la, lb: SWAP a$, b$
FOR i = 1 TO la
a = VAL(MID$(a$, la + 1 - i, 1))
IF i <= lb THEN b = VAL(MID$(b$, lb + 1 - i, 1)) ELSE b = 0
c = a + b + jw
jw = c \ 10
c = c MOD 10
s$ = LTRIM$(STR$(c)) + s$
NEXT i
IF jw <> 0 THEN s$ = "1" + s$
Add$ = s$
END FUNCTION[/color]
第一题 无数组
5 楼
qndk [专家分：0] 发布于 2011-10-03 11:10:00
全能教育机构QQ571231951.
★重金打造,权威操作★[★
和您携手面临造价工程师，雅思，托福，公务员，报关员，报检员，拍卖师等等考试困难 ，再创辉煌！
我们 的宗旨：实力第一、信誉第一、服务第一、质量保证 内部渠道；过率100%，本机构从事考试行业多年，信誉保证，质量可靠。咨询QQ571231951，TEL:13552229332.. http://www.qndk666.com/
6 楼
刚过桥DE米线 [专家分：0] 发布于 2011-10-08 20:22:00
广告滚！
7 楼
刚过桥DE米线 [专家分：0] 发布于 2011-10-08 20:22:00
感谢唐铭康！
8 楼
刚过桥DE米线 [专家分：0] 发布于 2011-10-08 20:34:00
是的，是10 的100 次方
9 楼
王19991122 [专家分：70] 发布于 2011-11-24 19:53:00
本人不才，用高精度编了一个程序，希望可以帮上楼主
CLS
INPUT n
DIM c$(n), a(1001), b(1000)
FOR i = 1 TO n
INPUT a$, b$
l = LEN(a$)
l1 = LEN(b$)
IF l1 > l THEN SWAP a$, b$: SWAP l, l1
FOR j = 1 TO l
a(j) = VAL(MID$(a$, j, 1))
NEXT j
FOR j = 1 TO l1
b(j) = VAL(MID$(b$, j, 1))
NEXT j
FOR j = 1 TO l
x = a(j) + b(j)
a(j + 1) = a(j + 1) + x \ 10
a(j) = x MOD 10
NEXT j
m = l + 1
IF a(l + 1) = 0 THEN m = l
FOR j = m TO 1 STEP -1
c$(i) = c$(i) + LTRIM$(STR$(a(j)))
a(j) = 0
NEXT j
NEXT i
FOR i = 1 TO n
PRINT c$(i),
NEXT i
我来回复
您所在位置：