鱼C论坛

 找回密码
 立即注册
查看: 83|回复: 12

[技术交流] 成长每一点---题库11---4 Kuy(难度---三角形最大和)

[复制链接]
最佳答案
15 
发表于 2019-1-11 21:04:20 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Stubborn 于 2019-1-11 21:12 编辑

欧拉计划18题
欧拉计划67题


这是题目 18 的更难的一个版本。穷举每一种可能的路径是不可行的,因为一共有2**99  条可能的路径。就算每秒钟能处理 10**12 条路径,也需要 200 亿年来处理完所有的路径。存在一个高效的方法来处理这道题。

你的任务是编写一个函数longestSlideDown(在ruby中:) longest_slide_down,它将金字塔表示作为参数并返回其“ 最长 ”向下滑动'。例如

longestSlideDown([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]])
# => 23

算法  功能编程  声明性编程  高阶函数  功能控制流  基本语言功能   基本面

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
15 
 楼主| 发表于 2019-1-11 21:15:38 | 显示全部楼层
本帖最后由 Stubborn 于 2019-1-12 05:32 编辑
  1. def longest_slide_down(pyramid):
  2.     def findway(x, y):
  3.         if not visited[x][y]:
  4.             visited[x][y] = True
  5.             for m in move:
  6.                 nx, ny = x + m[0], y + m[1]
  7.                 if 0 <= nx < len(pyramid) and 0 <= ny <= nx:
  8.                     dp[nx][ny] = max(dp[x][y] + pyramid[nx][ny], dp[nx][ny])
  9.                     checklist.append((nx, ny))

  10.     visited = [[False] * (i + 1) for i in range(len(pyramid))]
  11.     dp = [[0] * (i + 1) for i in range(len(pyramid))]
  12.     move = [(1, 0), (1, 1)]
  13.     checklist = [(0, 0)]
  14.     dp[0][0] = pyramid[0][0]

  15.     max = 0

  16.     while True:
  17.         for i in range(len(checklist)):
  18.             findway(checklist[i][0], checklist[i][1])
  19.         if len([(j, k) for j in range(len(pyramid)) for k in range(j) if not visited[j][k]]) == 0:
  20.             visited = [[False] * (i + 1) for i in range(len(pyramid))]
  21.             checklist = [(0, 0)]
  22.             if max < max(dp[len(pyramid)-1]):
  23.                 max = max(dp[len(pyramid)-1])
  24.             else:
  25.                 break
  26.     return max
复制代码

  1. def longest_slide_down(p):
  2.     res = p.pop()
  3.     while p:
  4.         tmp = p.pop()
  5.         res = [tmp[i] + max(res[i],res[i+1])  for i in range(len(tmp))]  #把tmp的每个值。加上tmp值对应上方res较大的一个值。
  6.     return res.pop()
  7. #代码分析=========保持res为最后一列,tmp为倒数第二列
  8. aa=[[4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23],
  9.    [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
  10.    [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
  11.    [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
  12.    [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
  13.    [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
  14.    [41, 41, 26, 56, 83, 40, 80, 70, 33],
  15.    [99, 65, 4, 28, 6, 16, 70, 92],
  16.    [88, 2, 77, 73, 7, 63, 67],
  17.    [19, 1, 23, 75, 3, 34],
  18.    [20, 4, 82, 47, 65],
  19.    [18, 35, 87, 10],
  20.    [17, 47, 82],
  21.    [95, 64],
  22.    [75]]
复制代码

  1. def longest_slide_down(pyramid):
  2.         "从后面开始处理"
  3.     for i in range(len(pyramid)-2,-1,-1):  #i为13到0
  4.         for j in range(i+1):  #第一次0-13 每循环一次-1
  5.             pyramid[i][j] += max([pyramid[i+1][j],pyramid[i+1][j+1]])
  6.                 #  倒数第二列第j个值    +=   max(最后一列,j对应的二个值)
  7.     return pyramid[0][0]
复制代码

  1. class Tree(object):
  2.     value = summ = None
  3.     left = right = None
  4.    
  5.     def __init__(self, value):
  6.         self.value = value


  7. def iter_pairs(level):
  8.     it = iter(level)
  9.     a, b = Tree(next(it)), Tree(next(it))
  10.     while b.value is not None:
  11.         yield a, b
  12.         a, b = b, Tree(next(it, None))


  13. def build_tree(pyramid):
  14.     it = iter(pyramid)
  15.     root = Tree(next(iter(next(it))))
  16.     prev_level = iter([root])
  17.     for level in it:
  18.         tree_level = []
  19.         parent = next(prev_level)
  20.         
  21.         for left_tree, right_tree in iter_pairs(level):
  22.             tree_level.append(left_tree)

  23.             parent.left = left_tree
  24.             parent.right = right_tree
  25.             parent = next(prev_level, None)
  26.             
  27.         tree_level.append(right_tree)
  28.         prev_level = iter(tree_level)

  29.     return root


  30. def calc_max_sums(root):
  31.     if root is None:
  32.         return 0

  33.     if root.summ is not None:
  34.         return root.summ

  35.     root.summ = root.value + max(calc_max_sums(root.left), calc_max_sums(root.right))
  36.     return root.summ


  37. def find_max_slide(root):
  38.     if root is None:
  39.         return 0

  40.     if not (root.left and root.right):
  41.         return root.value

  42.     if root.left.summ >= root.right.summ:
  43.         return root.value + find_max_slide(root.left)
  44.    
  45.     if root.left.summ < root.right.summ:
  46.         return root.value + find_max_slide(root.right)


  47. def longest_slide_down(pyramid):
  48.     tree = build_tree(pyramid)
  49.     calc_max_sums(tree)
  50.     return find_max_slide(tree)
复制代码

  1. def longest_slide_down(tri):
  2.   while len(tri) > 1:
  3.     t0 = tri.pop()
  4.     t1 = tri.pop()
  5.     tri.append([max(t0[i], t0[i+1]) + t for i,t in enumerate(t1)])
  6.   return tri[0][0]
复制代码

  1. from operator import add
  2. def longest_slide_down(pyramid):
  3.     return reduce(lambda x, y: map(add, map(max, x[1:], x[:-1]), y), reversed(pyramid))[0]
复制代码

  1. from itertools import izip

  2. def longest_slide_down(pyramid):
  3.     sums = pyramid[-1]
  4.     for row in pyramid[-2::-1]:
  5.         sums = [a + max(b, c) for (a, b, c) in izip(row, sums, sums[1:])]
  6.     return sums[0]
复制代码

  1. def longest_slide_down(p):
  2.     p[-1] = map(max, zip(p[-1][:-1], p[-1][1:]))
  3.     p[-2] = map(sum, zip(p[-1], p[-2]))
  4.     return longest_slide_down(p[:-1]) if len(p) > 2 else p[0][0]
复制代码

  1. def longest_slide_down(pyramid):
  2.     return reduce(lambda prev, cur: map(lambda (i, el): el + max(prev[i], prev[i+1]), enumerate(cur)), reversed(pyramid))[0]
复制代码

  1. def longest_slide_down(a):
  2.   return longest_slide_down(a[:-2]+[[a[-2][i]+max(a[-1][i],a[-1][i+1]) for i in xrange(len(a[-2]))]]) if len(a)>1 else a[0][0]
复制代码

  1. longest_slide_down = lambda l:reduce(lambda x,y:[max([x[i],x[i+1]])+y[i] for i in range(len(y))],l[::-1])[0]
复制代码


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
15 
 楼主| 发表于 2019-1-12 05:32:09 | 显示全部楼层
本帖最后由 Stubborn 于 2019-1-12 05:39 编辑

@塔利班 @heidern0612 @Ice_in_left 人生苦短我用python,一行代码,最为致命,正所谓,推导虐我千百遍,只能待你如初恋,最后三个代码,推导过不去,代码直接copy过来的,可以帮忙看看哪里错了吗? 题目做多了,总觉得这个题目是不是一样推导就过去了 有推导训练集吗。班利塔大神,@塔利班 大哥@heidern0612  可以帮忙讲下倒数两个吗 ,一个推导,一个递归
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1335 
发表于 2019-1-12 10:50:39 | 显示全部楼层
多了看着就乱
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 3 天前 | 显示全部楼层
这个题目在哪里呢?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
15 
 楼主| 发表于 3 天前 | 显示全部楼层
注册列表 发表于 2019-1-19 23:08
这个题目在哪里呢?

有两个链接,欧拉计划18题,和67题,这属于67题。可以先看18题,练习下。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 前天 17:01 | 显示全部楼层
Stubborn 发表于 2019-1-19 23:15
有两个链接,欧拉计划18题,和67题,这属于67题。可以先看18题,练习下。

67和18不太一样,第一个可以枚举第二个得动归啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
15 
 楼主| 发表于 前天 17:05 | 显示全部楼层
注册列表 发表于 2019-1-20 17:01
67和18不太一样,第一个可以枚举第二个得动归啊

6行代码可以搞定,不用枚举
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 前天 17:10 | 显示全部楼层
Stubborn 发表于 2019-1-20 17:05
6行代码可以搞定,不用枚举

我从幼儿园开始就缺乏解决问题的方法,等我学学再来。。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
15 
 楼主| 发表于 前天 18:15 | 显示全部楼层
注册列表 发表于 2019-1-20 17:10
我从幼儿园开始就缺乏解决问题的方法,等我学学再来。。。。

从后面算起比较快。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 前天 20:59 | 显示全部楼层
帮我测试这段代码
lista=[]<输入列表>
ub =len(lista)
list1=[]
list2=[]
for i in range(ub-1,0,-1):
    for j in range(0,i):
        list1.append(max(lista[i-1][j]+lista[i][j],lista[i-1][j]+lista[i][j+1]))
    del lista[i]
    del lista[i-1]
    lista.append(list1)
    list1=[]
print(lista[0][0])


现学现卖不知道咋样。。。。例子的两个都没问题

评分

参与人数 1荣誉 +5 鱼币 +2 贡献 +3 收起 理由
Stubborn + 5 + 2 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
15 
 楼主| 发表于 前天 21:13 | 显示全部楼层
注册列表 发表于 2019-1-20 20:59
帮我测试这段代码
lista=[]
ub =len(lista)


做我最新的那个,==我跟新下我也准备做
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 前天 22:16 | 显示全部楼层
Stubborn 发表于 2019-1-20 21:13
做我最新的那个,==我跟新下我也准备做

我特意做了个西里古怪的。。结果忘记打return结果函数判断一部分输不出来
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2019-1-22 01:31

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表