#Python版块活动# 挖(Qiang)钻(Yu)石(Bi) ---结束

挥舞乾坤

1. def zs(data):
   
2.     data = [[[each, ''] for each in eachline] for eachline in data];fx = {0:'L', 1:'M', 2:'R'}
   
3.     for x in reversed(range(len(data) - 1)):
   
4.         for y in range(len(data[x])):
   
5.             maxs = max(data[x+1][y:y+3]);data[x][y][0] += maxs[0];data[x][y][1] = '{0}{1}'.format(fx[data[x+1][y:y+3].index(maxs)],  maxs[1])
   
6.     return tuple(data[0][0])
   

复制代码

看了@wei_Y 版主之前的一个帖子,<<最优?步步贪婪，误入歧途！>>,借鉴了大神的算法,只能算是抄袭.

挥舞乾坤

保留原来的那个吧,后一个不算数

ft3312591

有兴趣来看下

lightninng

自己顺着树遍历的路子想了半天，最后搁浅，然后看了wei_Y同学的算法，表示给跪，然后翻到了他的这个贴子http://bbs.fishc.com/forum.php?mod=viewthread&tid=54578&ctid=1

觉得这个暴力随机方法很有趣试着实现了一下

1. import random
   
2. def ran_dirc(geo):
   
3.     col = 0;path = []#记录最大收集数和对应路径
   
4.     depth = len(geo)
   
5.     for i in range((1000*depth**2)):
   
6.         col_temp = 0;path_temp = []#记录本次的收集数和路径
   
7.         position  = 0              #记录在一层中的位置
   
8.         for layer in range(depth):
   
9.             #更新钻石数
   
10.             col_temp += geo[layer][position]
    
11.             dirction = random.choice([-1,0,1])
    
12.             #更新新的位置
    
13.             if dirction == -1 :
    
14.                 path_temp.append("L")
    
15.             elif dirction == 0 :
    
16.                 path_temp.append("M")
    
17.                 position += 1
    
18.             else:
    
19.                 path_temp.append("R")
    
20.                 position += 2
    
21.         #更新最收集数和对应路径
    
22.         if col < col_temp:
    
23.             path_temp.pop()
    
24.             path = path_temp
    
25.             col = col_temp
    
26.     return col,"".join(path)

复制代码

然后下面是结果 ：

1. (8, '')
   
2. (5, 'R')
   
3. (23, 'LL')
   
4. (24, 'LMR')
   
5. (38, 'RRRR')
   
6. (41, 'MRLRL')
   
7. (49, 'RLMLRL')
   
8. (49, 'MRMMMLM')
   
9. (71, 'MMLMRRLL')
   
10. (66, 'MMLLRRLRR')
    
11. (78, 'MMRLRRMRLR')
    
12. (83, 'LLRLLLRMRLL')

复制代码

参与一下。嘿嘿~~

天国浪子

来看看，学习哈经验

天国浪子

我觉得，要计算从序列第2行开始，前面0行，1行取最大数值即可（此行任意一个均能挖到下一行）。

微风拂面

有的测试答案路径是不唯一的，

微风拂面

代码如果用列表的index（）内置函数，会让代码好看并少一点，（我没用是把题目理解意思歪了，Σ( ° △ °|||)︴）

1. path_dic_in = 0
   
2. def dig(test_data):
   
3.     def maxNumber(datali):
   
4.         global path_dic_in
   
5.         if datali[0] >= datali[1] and datali[0] >= datali[2]:
   
6.             path_dic_in = 0
   
7.             return datali[0]
   
8.         if datali[1] > datali[0] and datali[1] >= datali[2]:
   
9.             path_dic_in = 1
   
10.             return datali[1]
    
11.         if datali[2] > datali[1] and datali[2] > datali[0]:
    
12.             path_dic_in = 2
    
13.             return datali[2]
    
14.     def set_tree(n1, m1,digpath):
    
15.         tree[n1][m1] += maxNumber(tree[n1+1][m1:m1+3])
    
16.         digpath[n1][m1] =  path_dic[path_dic_in] + digpath[n1+1][m1+path_dic_in]
    
17.     tree = test_data
    
18.     n = len(tree)
    
19.     m = len(tree[n-1])
    
20.     path_dic = {0:'L',1:'M',2:'R'}
    
21.     digpath = [['' for i in range(len(tree[j-1]))]for j in range(1,len(tree)+1)]
    
22.     while n > 1 :
    
23.         i = 0
    
24.         while i <= m -3:
    
25.             set_tree(n-2, i,digpath)
    
26.             i = i + 1
    
27.         n = n-1
    
28.         m = m -2
    
29.    
    
30.     return (tree[0][0],digpath[0][0])

复制代码

微风拂面

我C用得比较多，最近才开始用python，研究了一下用python登陆网站下载数据，

戴宇轩

微风拂面 发表于 2015-3-15 18:03
代码如果用列表的index（）内置函数，会让代码好看并少一点，（我没用是把题目理解意思歪了，Σ( ° △ °| ...

呃。。BIF是可以用的, 想好了再发, 还有时间!

微风拂面

挥舞乾坤 发表于 2015-3-14 14:19
结果:

用递归写的,效率很低,再想想别的方法.

代码很精练，不过对test_6也是找到一条路径，没有找到得到最大值的全部路径，个人觉得应该是dict的key是唯一，一些最大值被新的最大值的路径覆盖掉，

戴宇轩

微风拂面 发表于 2015-3-15 19:33
代码很精练，不过对test_6也是找到一条路径，没用找到全部的路径，认真看了一下，应该是dict的可以只能唯 ...

题目要求: 不管怎么走, 数量对就OK了

戴宇轩

排名中。。。

微风拂面

戴宇轩 发表于 2015-3-15 20:21
题目要求: 不管怎么走, 数量对就OK了

嗯，我只是想怎么编写一个能找到全部路径的方法，

lightninng

话说。楼上的朋友想的真是全面。自己都没想过还有多种路径的情况。不过考虑一下还挺有意思的。按照wei_Y同学的代码改编了一个搜索所有路径的函数，返回值为[最大收集数,[路径列表]]

1. def dug(dia):
   
2.         path_dic = {0:'L',1:'M',2:'R'}
   
3.         #自底向上更新每个结点的值为由此结点向下可以挖到的最多钻石数
   
4.         for i in reversed(range(len(dia)-1)):
   
5.                 # 底层开始取值
   
6.                 for j in range(len(dia[i])):
   
7.                         max_list = [dia[i+1][j], dia[i+1][j+1], dia[i+1][j+2]]
   
8.                         max_dia = max(max_list)
   
9.                         # 取最大值。
   
10.                         dia[i][j] = dia[i][j] + max_dia
    
11.         result = [dia[0][0],[]]#存放最后结果
    
12.         #参照二叉树遍历思想用一个栈来存放可能收集到最多钻石的路径
    
13.         stack = [("",0,0)]   #根结点入栈，栈中的元素为：由上层挖到该结点所经过的路径、结点的位置组成的三元组
    
14.         while stack != []:
    
15.             node = stack.pop()
    
16.             if node[1] == (len(dia) - 1):
    
17.                 result[1].append(node[0]) #如果是最底层结点则将路径输出
    
18.                 continue
    
19.             max_list = [dia[node[1]+1][node[2]], dia[node[1]+1][node[2]+1], dia[node[1]+1][node[2]+2]]
    
20.             max_next = max(max_list)
    
21.             #将下一层可以收集到最多钻石的结点入栈
    
22.             if max_list[0] == max_next:
    
23.                 stack.append((node[0]+'L',node[1]+1,node[2]))
    
24.             if max_list[1] == max_next:
    
25.                 stack.append((node[0]+'M',node[1]+1,node[2]+1))
    
26.             if max_list[2] == max_next:
    
27.                 stack.append((node[0]+'R',node[1]+1,node[2]+2))
    
28.         return result

复制代码

测试结果为

1. [8, ['']]
   
2. [5, ['R']]
   
3. [23, ['LL']]
   
4. [24, ['LMR']]
   
5. [38, ['RRRR']]
   
6. [41, ['MRLRM', 'MRLRL']]
   
7. [49, ['RLMLRL', 'RLLMRL']]
   
8. [49, ['MRMMMLM']]
   
9. [71, ['MMLMRRLL']]
   
10. [66, ['MMLLRRLRR']]
    
11. [78, ['MMRLRRMRLR', 'MMRLRRMMMR']]
    
12. [83, ['LLRLLLRMRRL', 'LLRLLLRMRLL', 'LLRLLLRMLRL', 'LLRLLLRMLLR']]

复制代码

戴宇轩

lightninng 发表于 2015-3-15 22:13
话说。楼上的朋友想的真是全面。自己都没想过还有多种路径的情况。不过考虑一下还挺有意思的。按照wei_Y同 ...

呃, 要不是因为我作业没写完, 早就出排名了。。。

尽快写好。。。

lightninng

戴宇轩 发表于 2015-3-15 22:21
呃, 要不是因为我作业没写完, 早就出排名了。。。

尽快写好。。。

哈哈。小同学你好。写作业还要来耍论坛~~
话说都是看大神写。自己的方法半天也想不出来。略忧伤。不过想了想楼上说的问题还挺有意思的。

挥舞乾坤

这种活动真的很好,每次参与都能学到新的东西,以后要多搞搞.@～风介～ @wei_Y @戴宇轩

挥舞乾坤

哇.土豪,10币两次,领了再说

lightninng

戴宇轩 发表于 2015-3-15 22:21
呃, 要不是因为我作业没写完, 早就出排名了。。。

尽快写好。。。

为了有钱买python的课后题 。我好像学了不少东西啊~~~
小同学，你很给力~~
:handshake