厦门做网站优化,电子商务市场营销,北京网站建设公司 蓝纤科技,郑州企业建设网站技术Q1: Compose
编写一个高阶函数composer#xff0c;它返回两个函数func和func_adder。 func是一个单参数函数#xff0c;它应用到目前为止已经组合的所有函数。这些函数将首先应用最新的函数#xff08;参见doctests和示例#xff09;。 func_adder用于向我们的组合添加更多…Q1: Compose
编写一个高阶函数composer它返回两个函数func和func_adder。 func是一个单参数函数它应用到目前为止已经组合的所有函数。这些函数将首先应用最新的函数参见doctests和示例。 func_adder用于向我们的组合添加更多函数当调用另一个函数g时func_adder应该返回一个新的func和一个新的func_adder。
如果没有参数传入composer则返回的func是恒等函数。
举例来说 add_one lambda x: x 1square lambda x: x * xtimes_two lambda x: x x f1, func_adder composer()f1(1)
1 f2, func_adder func_adder(add_one)f2(1)
2 # 1 1 f3, func_adder func_adder(square)f3(3)
10 # 1 (3**2) f4, func_adder func_adder(times_two)f4(3)
37 # 1 ((2 * 3) **2) 提示你的func_adder应该返回两个参数func和 func_adder. 我们知道什么函数返回func和func_adder 这个提示真的神来之笔由于compose返回 func func_adder这两个函数 所以func_adder应该是以新func为形参的compose函数 func lambda x:func(g(x)) g(x)作为原函数的参数x 逐级嵌套 如图 def composer(funclambda x: x):Returns two functions -one holding the composed function so far, and anotherthat can create further composed problems. add_one lambda x: x 1 mul_two lambda x: x * 2 f, func_adder composer() f1, func_adder func_adder(add_one) f1(3)4 f2, func_adder func_adder(mul_two) f2(3) # should be 1 (2*3) 77 f3, func_adder func_adder(add_one) f3(3) # should be 1 (2 * (3 1)) 99def func_adder(g):*** YOUR CODE HERE ***return composer(lambda x:func(g(x)))return func, func_adder pass: PS D:\pycharm\python document\CS61A class homework\hw03 python3 ok -q composerAssignment: Homework 3
OK, version v1.18.1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Running tests---------------------------------------------------------------------
Test summary1 test cases passed! No cases failed.Q4: Count change
Once the machines take over, the denomination of every coin will be a power of two: 1-cent, 2-cent, 4-cent, 8-cent, 16-cent, etc. There will be no limit to how much a coin can be worth.
Given a positive integer total, a set of coins makes change for total if the sum of the values of the coins is total. For example, the following sets make change for 7:
7 1-cent coins5 1-cent, 1 2-cent coins3 1-cent, 2 2-cent coins3 1-cent, 1 4-cent coins1 1-cent, 3 2-cent coins1 1-cent, 1 2-cent, 1 4-cent coins
Thus, there are 6 ways to make change for 7. Write a recursive function count_change that takes a positive integer total and returns the number of ways to make change for total using these coins of the future. Hint: Refer the implementation of count_partitions for an example of how to count the ways to sum up to a total with smaller parts. If you need to keep track of more than one value across recursive calls, consider writing a helper function. 分析作者把此题核心分为两个函数
divide函数
作用
求 对于total 满足1------小于total的最大2的倍数 面值美分 的排列种类
核心
将一种情况分为两种情况即
当前有最大数的排列数量 和 无当前最大数的数量
举个例子如图(函数实现过程) max1
求的是 小于total的最大2的倍数
def divide(total,num):if num1:return 1if totalnum:return divide(total,num/2)return divide(total-num,num)divide(total,num/2)def max1(total):if total1:return 1if total0:return max1(total//2)*2
def count_change(total):Return the number of ways to make change for total. count_change(7)6 count_change(10)14 count_change(20)60 count_change(100)9828 from construct_check import check # ban iteration check(HW_SOURCE_FILE, count_change, [While, For])True*** YOUR CODE HERE ***if total1:return 1return divide(total,max1(total))pass结果
PS D:\pycharm\python document\CS61A class homework\hw03 python3 ok -q count_changeAssignment: Homework 3
OK, version v1.18.1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Running tests---------------------------------------------------------------------
Test summary1 test cases passed! No cases failed.Q5: Towers of Hanoi
一个经典的难题称为塔的河内是一个游戏包括三个 杆和许多不同尺寸的圆盘圆盘可以在任何杆上滑动。 这个谜题从n磁盘开始磁盘按照大小的升序整齐地堆叠在一起 start棒顶部最小形成圆锥形。
拼图的目的是将整个堆叠移动到end杆 遵守以下规则
一次只能移动一个磁盘。每次移动包括从其中一根杆上取下顶部最小的圆盘 把它滑到另一个杆上在其他可能已经被 存在于该杆上。不能将磁盘放在较小磁盘的顶部。
完成move_stack的定义它将打印出执行以下操作所需的步骤 将n盘从start棒移动到end棒不违反 规则提供的print_move函数将打印出移动 从给定的origin到给定的destination的单个磁盘。 提示在一张纸上画出几个带有各种n的游戏并尝试 找到一个适用于任何n的磁盘运动模式。在你的解决方案中 当你需要移动任何数量的 小于n的圆盘从一个棒到另一个棒。如果你需要更多帮助 以下提示。 分析
核心拆分思想动态规划dp
对于n个盘子需要从起点到终点的问题可以转化为
1.将n个盘子需要从起点到非起点或终点,
2.第n个盘子从起点到终点
3.再将n-1盘子放到终点的过程
1其中对于n2的情况即递归终点需要模拟出相应过程 注意n1需要额外说明
如图所示 def print_move(origin, destination):Print instructions to move a disk.print(Move the top disk from rod, origin, to rod, destination)def move_stack(n, start, end):Print the moves required to move n disks on the start pole to the endpole without violating the rules of Towers of Hanoi.n -- number of disksstart -- a pole position, either 1, 2, or 3end -- a pole position, either 1, 2, or 3There are exactly three poles, and start and end must be different. Assumethat the start pole has at least n disks of increasing size, and the endpole is either empty or has a top disk larger than the top n start disks. move_stack(1, 1, 3)Move the top disk from rod 1 to rod 3 move_stack(2, 1, 3)Move the top disk from rod 1 to rod 2Move the top disk from rod 1 to rod 3Move the top disk from rod 2 to rod 3 move_stack(3, 1, 3)Move the top disk from rod 1 to rod 3Move the top disk from rod 1 to rod 2Move the top disk from rod 3 to rod 2Move the top disk from rod 1 to rod 3Move the top disk from rod 2 to rod 1Move the top disk from rod 2 to rod 3Move the top disk from rod 1 to rod 3assert 1 start 3 and 1 end 3 and start ! end, Bad start/end*** YOUR CODE HERE ***n_s0if 1!start and 1!end:n_s1if 2!start and 2!end:n_s2if 3!start and 3!end:n_s3if n1:print_move(start,end)returnif n2:print_move(start,n_s)print_move(start,end)print_move(n_s,end)returnmove_stack(n-1,start,n_s)print_move(start,end)move_stack(n-1,n_s,end)pass情况
PS D:\pycharm\python document\CS61A class homework\hw03 python3 ok -q move_stackAssignment: Homework 3
OK, version v1.18.1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Running tests---------------------------------------------------------------------
Test summary1 test cases passed! No cases failed.Q6: Anonymous factorial
The recursive factorial function can be written as a single expression by using a conditional expression. fact lambda n: 1 if n 1 else mul(n, fact(sub(n, 1)))fact(5)
120
However, this implementation relies on the fact (no pun intended) that fact has a name, to which we refer in the body of fact. To write a recursive function, we have always given it a name using a def or assignment statement so that we can refer to the function within its own body. In this question, your job is to define fact recursively without giving it a name!
Write an expression that computes n factorial using only call expressions, conditional expressions, and lambda expressions (no assignment or def statements). Note in particular that you are not allowed to use make_anonymous_factorial in your return expression. The sub and mul functions from the operator module are the only built-in functions required to solve this problem:
from operator import sub, muldef make_anonymous_factorial():Return the value of an expression that computes factorial. make_anonymous_factorial()(5)120 from construct_check import check # ban any assignments or recursion check(HW_SOURCE_FILE, make_anonymous_factorial, [Assign, AugAssign, FunctionDef, Recursion])Truereturn lambda n : (lambda x, function : 1 if x 1 else x * function(x - 1, function))(n, lambda x, function : 1 if x 1 else x * function(x - 1, function))
分析 from operator import sub, muldef make_anonymous_factorial():def function(x, function):if(x 1):return 1else:return function(x - 1, function) * xreturn lambda n : function(n, function) 我采取了High-order Function的方法
定义一个将自身作为参数的函数。
从更深层次的角度来讲
这不过是将“函数”的Abstraction程度降低了一层将 “函数寻址”这一行为显式地实现了
将function()用lambda表达出来即
lambda x, function : 1 if x 1 else x * function(x - 1, function)
合并即以下答案
1.lambda x:
函数体
( lambda x,function:function(x-1function)*x if x0 else 1)
参数
(x,lambda x,function:function(x-1function)*x if x0 else 1)
另外一种形式
2.
lambda x:
函数体
(lambda x,function:function(x-1,function)*x if x0 else 1)
参数
(x-1,lambda x,function:function(x-1,function)*x if x0 else 1)
*x if x0 else 1
错误分析
function(未给出定义) 1.error:
(lambda x,function:function(x-1,function)*x if x0 else 1)
(x-1,function)*x if x0 else 1
2.error:
(lambda x,function:function(x-1,function)*x if x0 else 1)
(x,function)
pass情况
PS D:\pycharm\python document\CS61A class homework\hw03 python3 ok -q make_anonymous_factorialAssignment: Homework 3
OK, version v1.18.1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Running tests---------------------------------------------------------------------
Test summary1 test cases passed! No cases failed.Backup... 100% complete
Backup past deadline by 1245 days, 3 hours, 43 minutes, and 25 secondsOK is up to date完整答案
HW_SOURCE_FILE__file__def composer(funclambda x: x):Returns two functions -one holding the composed function so far, and anotherthat can create further composed problems. add_one lambda x: x 1 mul_two lambda x: x * 2 f, func_adder composer() f1, func_adder func_adder(add_one) f1(3)4 f2, func_adder func_adder(mul_two) f2(3) # should be 1 (2*3) 77 f3, func_adder func_adder(add_one) f3(3) # should be 1 (2 * (3 1)) 99def func_adder(g):*** YOUR CODE HERE ***return composer(lambda x:func(g(x)))return func, func_adderdef g(n):Return the value of G(n), computed recursively. g(1)1 g(2)2 g(3)3 g(4)10 g(5)22 from construct_check import check # ban iteration check(HW_SOURCE_FILE, g, [While, For])True*** YOUR CODE HERE ***if n3:return nelse:return g(n-1)2*g(n-2)3*g(n-3)def g_iter(n):Return the value of G(n), computed iteratively. g_iter(1)1 g_iter(2)2 g_iter(3)3 g_iter(4)10 g_iter(5)22 from construct_check import check # ban recursion check(HW_SOURCE_FILE, g_iter, [Recursion])True*** YOUR CODE HERE ***if n3:return nelse:f11f22f33f43*f12*f2f3while n4:f1f2f2f3f3f4f43*f12*f2f3n-1return f4def missing_digits(n):Given a number a that is in sorted, increasing order,return the number of missing digits in n. A missing digit isa number between the first and last digit of a that is not in n. missing_digits(1248) # 3, 5, 6, 74 missing_digits(1122) # No missing numbers0 missing_digits(123456) # No missing numbers0 missing_digits(3558) # 4, 6, 73 missing_digits(35578) # 4, 62 missing_digits(12456) # 31 missing_digits(16789) # 2, 3, 4, 54 missing_digits(19) # 2, 3, 4, 5, 6, 7, 87 missing_digits(4) # No missing numbers between 4 and 40 from construct_check import check # ban while or for loops check(HW_SOURCE_FILE, missing_digits, [While, For])True*** YOUR CODE HERE ***if n//100:return 0lastn%10nn//10if n%10last:declast-1-n%10else:dec0return missing_digits(n)decdef divide(total,num):if num1:return 1if totalnum:return divide(total,num/2)return divide(total-num,num)divide(total,num/2)def max1(total):if total1:return 1if total0:return max1(total//2)*2
def count_change(total):Return the number of ways to make change for total. count_change(7)6 count_change(10)14 count_change(20)60 count_change(100)9828 from construct_check import check # ban iteration check(HW_SOURCE_FILE, count_change, [While, For])True*** YOUR CODE HERE ***if total1:return 1return divide(total,max1(total))def print_move(origin, destination):Print instructions to move a disk.print(Move the top disk from rod, origin, to rod, destination)def move_stack(n, start, end):Print the moves required to move n disks on the start pole to the endpole without violating the rules of Towers of Hanoi.n -- number of disksstart -- a pole position, either 1, 2, or 3end -- a pole position, either 1, 2, or 3There are exactly three poles, and start and end must be different. Assumethat the start pole has at least n disks of increasing size, and the endpole is either empty or has a top disk larger than the top n start disks. move_stack(1, 1, 3)Move the top disk from rod 1 to rod 3 move_stack(2, 1, 3)Move the top disk from rod 1 to rod 2Move the top disk from rod 1 to rod 3Move the top disk from rod 2 to rod 3 move_stack(3, 1, 3)Move the top disk from rod 1 to rod 3Move the top disk from rod 1 to rod 2Move the top disk from rod 3 to rod 2Move the top disk from rod 1 to rod 3Move the top disk from rod 2 to rod 1Move the top disk from rod 2 to rod 3Move the top disk from rod 1 to rod 3assert 1 start 3 and 1 end 3 and start ! end, Bad start/end*** YOUR CODE HERE ***n_s0if 1!start and 1!end:n_s1if 2!start and 2!end:n_s2if 3!start and 3!end:n_s3if n1:print_move(start,end)returnif n2:print_move(start,n_s)print_move(start,end)print_move(n_s,end)returnmove_stack(n-1,start,n_s)print_move(start,end)move_stack(n-1,n_s,end)from operator import sub, muldef make_anonymous_factorial():Return the value of an expression that computes factorial. make_anonymous_factorial()(5)120 from construct_check import check # ban any assignments or recursion check(HW_SOURCE_FILE, make_anonymous_factorial, [Assign, AugAssign, FunctionDef, Recursion])Truereturn lambda x:(lambda x,function:function(x-1,function)*x if x0 else 1)(x-1,lambda x,function:function(x-1,function)*x if x0 else 1)*x if x0 else 1
