本文主要是介绍MOOC数据结构与算法Python版-第六周编程作业，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1 铺瓷砖（10分）
题目内容：
给定一个长度为N的区域，及4种不同长度的瓷砖：灰瓷砖（长为1格）、红瓷砖（长为2格）、绿瓷砖（长为3格）与蓝瓷砖（长为4格），求所有不同的铺满整个区域的方法数。
例如：当N=5时，共有15种铺满区域的方法，示意图如下：
输入格式:
一个自然数N
输出格式：
一行数字，表示不同的方法总数
输入样例：
5
输出样例：
15
时间限制：500ms内存限制：32000kb
程序代码1：
def dfs(N):if N == 0:return 0if N == 1:return 1if N == 2:return 1 + dfs(N-1)if N == 3:return 1 + dfs(N-1) + dfs(N-2)if N == 4:return 1 + dfs(N-1) + dfs(N-2) + dfs(N-3)else:return dfs(N-1) + dfs(N-2) + dfs(N-3) + dfs(N-4)
N = int(input())
print(dfs(N))
程序代码2：
def tile(sizelist, space, knownresult):num = 0if space == 0:return 1elif knownresult[space] != 0:return knownresult[space]else:for i in [t for t in sizelist if t <= space]:num = num + tile(sizelist, space - i, knownresult)knownresult[space] = numreturn numsizelist = [1, 2, 3, 4]
space = eval(input())
knownresult = [0] * (space + 1)
print(tile(sizelist, space, knownresult))2 分发糖果（10分）
题目内容：
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
-
每个孩子至少分配到 1 个糖果。
-
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
输入格式:
一个列表，以文本格式的有效Python表达式给出
输出格式：
一行数字，表示满足分配条件所需的最少糖果数
输入样例：
[1,2,2]
输出样例：
4
注：可行的分配方案为1、2、1 颗糖果；第三个孩子只得到1颗糖果也满足题目条件
示例代码模板：
- def candy(ratings):
- # code here
- pass
- lst = eval(input())
- print(candy(lst))
时间限制：500ms内存限制：32000kb
程序代码：
def candy(ratings):sum = 0length = len(ratings)c_list = [1 for i in range(length)]for i in range(1,length):if ratings[i] > ratings[i-1]:c_list[i] = c_list[i-1] + 1for i in range(length-2, -1, -1):if ratings[i] > ratings[i+1] and c_list[i] <= c_list[i+1]:c_list[i] = c_list[i+1] + 1for i in range(length):sum += c_list[i]return sumlst = eval(input())
print(candy(lst))
3 表达式按不同顺序求值（10分）
题目内容：
给定一个表达式字符串，求出按不同的求值顺序可能得到的所有结果
输入格式:
一行字符串，仅包含0-9与运算符+、-与*
注：字符串保证三种运算符左右均为数字字符
输出格式：
所有不重复的可能的结果，从小到大排序并以半角逗号","分隔
输入样例：
2*3-4*5
输出样例：
-34,-14,-10,10
注：
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
示例代码模板：
- def findWays(expr):
- # 用于将字符串转为数字与运算符，供参考
-
nums, ops = [], []
- num = 0
- for c in expr:
- if '0' <= c <= '9':
- num = num * 10 + ord(c) - 48
- else:
- ops.append(c)
- nums.append(num)
- num = 0
- else:
- nums.append(num)
- # code here
- expr=input()
- print(findWays(expr))
时间限制：500ms内存限制：32000kb
程序代码：
class Solution():def findWays(self, expr):# 用于将字符串转为数字与运算符，供参考nums, ops = [], []num = 0for c in expr:if '0' <= c <= '9':num = num * 10 + ord(c) - 48else:ops.append(c)nums.append(num)num = 0else:nums.append(num)# 递归运算def calc(nums, ops):if not ops:return [nums[0]]if len(ops) == 1:if ops[0] == '+':return [nums[0] + nums[1]]elif ops[0] == '-':return [nums[0] - nums[1]]else:return [nums[0] * nums[1]]res = []for i in range(len(ops)):for num1 in calc(nums[:i + 1], ops[:i]):for num2 in calc(nums[i + 1:], ops[i + 1:]):res.append(calc([num1, num2], [ops[i]])[0])return resreturn calc(nums, ops)l = input()
s = Solution()
a = (list(set(s.findWays(l))))
a.sort()
print(",".join(str(i) for i in a))可惜这个用例5超时，还得改进。
这篇关于MOOC数据结构与算法Python版-第六周编程作业的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
