WelanceLee 发表于 2017-6-13 14:53
来一道扩展题，同样的思路可解
我们把场地分为一个个的格子，给每个格子标定一个整数，代表这个格子所代表的地面的海拔高度。
比赛的参赛者可以从任意一个格子开始，但只能向相邻的四个格子移动，并且目地格子的高度必须
小于现在所在格子的高度。我们假设从一个格子滑行到另一个格子所用的时间为1个单位时间。
现在告诉你滑雪场的大小为n*m, 并给你一个n行m列的整数二维列表H，表示每个格子的海拔高度。
请你计算出在这个场地上最长能滑行多少时间。
如：
n = 4
m = 4
H= [
,
,
,
]
则输出 6.
jerryxjr1220 发表于 2017-6-13 15:08
来一道扩展题，同样的思路可解
def slide(x, y, i):
global mmax
for mv in moves:
lx = x + mv
ly = y + mv
if -1 < lx < n and -1 < ly < m and H < H:
slide(lx, ly, i + 1)
if mmax < i:
mmax = i
n = 5
m = 4
H = [ for j in range(n)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
ma = 0
for i in range(n):
for j in range(m):
mmax = 0
slide(i, j, 0)
if ma < mmax:
ma = mmax
print(ma)
有个问题啊，就是递归函数里的变量何时需要声明为全局变量，这里n，m都没有声明就可以通过，但是mmax没有声明就不可以运行，这是为什么呢？
WelanceLee 发表于 2017-6-13 16:04
有个问题啊，就是递归函数里的变量何时需要声明为全局变量，这里n，m都没有声明就可以通过，但是mmax没 ...
因为mmax在递归过程中不断在赋值，如果你不声明全局变量的话，递归调用就会出错。
m，n的值应该是没有变化吧，不管何时调用都是不变的。
WelanceLee 发表于 2017-6-13 16:04
有个问题啊，就是递归函数里的变量何时需要声明为全局变量，这里n，m都没有声明就可以通过，但是mmax没 ...
更新一个动态规划的算法
import copy
n = 4
m = 4
H= [
,
,
,
]
dp = [ * m for i in range(n)]
bk = [[]]
while dp != bk:
bk = copy.deepcopy(dp)
queue = [ for i in range(n) for j in range(m)]
d = [, , [-1, 0], ]
while queue:
q = queue.pop(0)
for v in d:
nq = + v, q + v]
if 0 <= nq < n and 0 <= nq < m and H]] < H]]:
dp]] = max(dp]] + 1, dp]])
else:
continue
print(dp)
print(max((max(i) for i in dp)))
来看下算法
学习
{:5_90:}
6666666666666666
看看
学习喽
maze = [
,
,
,
,
,
,
]
a,b = 0,0
end = (3,5)
maze = 8
n = 2
def turn(a,b,n):
#设置方向和步长
t = [,,,[-1,0]]
#递归终结条件，到达终点坐标
if a == 3 and b==5:
#条件式返回，终止递归，且和下面的return 1 形成单一返回
return 1
#每一步的每一种可能
for i in t:
a1,b1 = a,b
a1 += i
b1 += i
#确定下一个落脚点的条件
if 0<=a1<=6 and 0<=b1<=5:
if maze == 1:
#防止无限 原地前进返回
maze = 8
#呼应最终的返回条件
if turn(a1,b1,n+1) == 1:
return 1
#一旦此条路不通，当重新启用下一种可能之前，
#当前脚下的地点初始化
maze = 1
turn(a,b,n)
for i in maze:
jerryxjr1220 发表于 2017-3-2 20:11
这题会解了那就来做做“欧拉计划的81~83题”吧，同样的最优路径搜索问题，应该也可以解了。
81、82题可 ...
先给大神拜个新年啊~
虽然这几天一直忙着玩，但从春节前一直记挂着你说的欧拉83题，有空就想想，今天总算静下心来解决了{:9_227:}
代码很乱，思路是先用动态规划法大致取一个值，然后利用这个值不断探索，取小于这个值的路径，然后
继续利用得到下一个较小的路径总和值，继续循环。最后得到了正确的结果，写过递归，但是运行速度太慢
慢慢慢慢慢，放弃了，最后是用循环解出来的，大概三四秒。想过很多方案都失败了，中间不断的受挫，还
好坚持了下来.
import shuzimigong as sh
t = sh.t.split('\n')
s = [[] for i in range(80)]
for i in range(80):
for each int.split(','):
s.append(int(each))
right = {(0,0):s}
right1 = {}
t = [(-1,0),(1,0),(0,1),(0,-1)]
def move():
count = s
a = 0
b = 0
while True:
if a == 79 and b == 79:
break
if a == 79 and b != 79:
count += s
b += 1
elif a != 79 and b == 79:
count += s
a += 1
else:
count += min(s,s)
if s <= s:
a += 1
else:
b += 1
print(count)
return count
def go(a,b,c,count):
q = [(a,b,c)]
while len(q) != 0:
(a,b,c) = q.pop(0)
for i in t:
a1 = a + i
b1 = b + i
if 0<=a1<80 and 0<=b1<80:
c1 = c + s
if c1 <count:
if (a1,b1) == (79,79):
print(c1)
return c1
if (a1,b1) not in right:
q.append((a1,b1,c1))
right[(a1,b1)] = c1
if (a1,b1) in right:
if c1 < right:
if (a1,b1,right[(a1,b1)]) in q:
q.remove((a1,b1,right[(a1,b1)]))
right[(a1,b1)] = c1
right1[(a1,b1)] = (a,b)
q.append((a1,b1,c1))
def main():
global right
global right1
count = move()
while True:
a = 0
b = 0
c = s
right = {(0,0):s}
right1 = {}
t = go(a,b,c,count)
if t != None:
count = t
else:
print(count)
break
main()
JAY饭 发表于 2018-2-21 21:11
先给大神拜个新年啊~
虽然这几天一直忙着玩，但从春节前一直记挂着你说的欧拉83题，有空就想想，今天总 ...
新年好！
过年还记着解题，为你的努力点个赞！{:10_275:}
666
888888
学习一下
学习学习，谢谢！
感谢分享这么牛逼的文件快点看
{:5_90:}