CS计算机代考程序代写 WELCOMETO EXAMPREP5

WELCOMETO EXAMPREP5

not
sponsored

We’llstartat Berkeleytome 2 10pacifictime
Worksheetcanbefound intheDrivefolder linkscsbla.orgexamprep
MusicDjangoReinhardt

MinorSwing
Beyondthesea
Brazil

Feelfreeto ask questions inthemeantime

CS 61A Structure and Interpretation of Computer Programs
Fall 2020 Quiz 5

INSTRUCTIONS

• Please review this worksheet before the exam prep session. Coming prepared will help greatly, as the TA will
be live solving without allocating much time for individual work.

• Either Sean or Derek will be on video live solving these questions. The other TA will be answering questions
in the chat. It is in your best interest to come prepared with specific questions.

• This is not graded, and you do not need to turn this in to anyone.

Below is a tree, which will be referred to as t1 in future questions.

2

1. Tree Printer

(a) Your friend wants to print out all of the values in some trees. Based on your experience in CS 61A, you
decide to come up with an unnecessarily complicated solution. You will provide them with a function
which takes in a tree and returns a node-printing function. When you call a node-printing function, it
prints out the label of one node in the tree. Each time you call the function it will print the label of a
different node. You may assume that your friend is polite and will not call your function after printing
out all of the tree’s node labels. You may print the labels in any order, so long as you print the label of
each one exactly once.

def node_printer(t):
���
>>> t1 = tree(1, [tree(2,
… [tree(5),
… tree(6, [tree(8)])]),
… tree(3),
… tree(4, [tree(7)])])
>>> printer = node_printer(t1)
>>> printer()
1
>>> printer()
4
>>> printer()
7
>>> for _ in range(5):
… printer()
3
2
6
8
5
���

lamb = ____________________________________________________________________________

def step():

nonlocal lamb

next_node, lamb = lamb()

print(_________________________________________________________________________)

for ____________________________________________________________________________

____________________________________________________________________________

return step

lamb

lamb lambda

I nextnode
lamb
print l

lamb lanbd.x.fianbdaCx.fSl
reassignedto area afunction

tovisit E thatcontains

lambda ft

labelnextnode
b in branchesnextnode
lamb lambda x f lambda X f b lamb

affordbtolamb

lamb lambda b lamb

Notes
lamb isa function

Ittakesnoinputs
Itsfirstoutputis probably a

node

Itssecondoutputisanother
functionofthesamestructure

oneachstepC callweshouldprintexactly onething
whatdowehaveaccessto

land afunction hardto
understand

t a treebutonlypointstotheroof whatifwe’reprintingnodesfartherdown
nextn.de Seemspromising
sothefirstreturnfromlandshouldbeanewuniquenode

print
labelnextnode

weneedtoprogressthroughthe wholetree
Howdowedecidewheretogonext
I

can’tuse becausethiswouldgiveus
repeats t istherootnode

weneedtoconsiderall of nextnode’schildren wewon’tvisit
nextnodeagain

becauseitonlygetsprintedonc

d
for bin branchesnextnode

Nowwhatdowedoforeachofthesebranches
Wecan’trecorse immediately weneedto send tovisitlater
d

wheredowegetnodeseachtime Fromlambs
Howmightwedothisif lambwerea list

t
mayne tovisit E selectanewnodeand

removeit fromlist
nextIode Eovisitpop ofnodestovisitinanefuture
for bin branchesnextnode

y
toVisitappendb

Let’simplementthiswith lambdafunctions

Ournextnode tovisitpopa lineisreplacedwithnextnodelamb lambC
Howdowe append tothislambdafunction

Storeinnestedlambda
functionseachoneholdsonevalueandareferencetothenextlambdafunction

y In
etsserce

a linkedlist whichyou’lllearnaboutlater

FIFA
Sofyouwanttocreate anew

lambdafunctionwhichreturns

yournewvalueandtheprevious
lambdafunction

storethisinfoinlocalvariables

forbin branchesnextnode
lamb lambdax f lambdaCx f b lamb

Finallyhowdoweinitializelamb It shouldcontaintherootnodeofthetreeanditssecondreturnvaluedoesn’tmattersince itwillneverbecalledSooneexampleconebe
lamb Lambda Ct None

3

2. Layer Generator

(a) Construct the generator function layer_gen, which takes in a tree t and returns a layer iterator of t. A
layer iterator returns label values of nodes in the tree in level order; that is, it yields the root node, then
each node from the second level, then each node from the third level and so on. Hint: consider using the
pop method of lists.

def layer_gen(t):
���
>> lg = layer_gen(t1)
>>> for node_label in lg:
… print(nodel_label)
1
2
3
4
5
6
7
8
���

___________________________________________________________________

while _____________________________________________________________:

node = ________________________________________________________

_______________________________________________________________

_______________________________________________________________

tovisit Ef
to visit
to visitpop o

print labelnode
to visitextend branchesnode

4

3. Fibonacci Generator

(a) Construct the generator function fib_gen, which returns elements of the Fibonacci sequence in order.

Hint: The solution doesn’t require any lambda functions or crazy workarounds, but instead a clever leap

of faith. Consider using the zip function.

def fib_gen():
���
>>> fg = fib_gen()
>>> for _ in range(10):
… print(next(fg))
0
1
1
2
3
5
8
13
21
34
���

yield from _____________________________________________________________

a = ____________________________________________________________________

________________________________________________________________________

for ____________________________________________________________________:

____________________________________________________________________

a

0 I 1 2 35 8
About

0 I

fibgeno
nextta

x y in ZipcarfibgenCD
yield Xty

forbgen gives

rexts D
O c I 2 3 S 8

Whatshouldweyieldfromtostart
Rememberthetwo basecasesofFibonacci fcos 0 FCD I
yield

from O D
Wedon’thaveenoughlinestokeeptrackofpreandconandtoyield

values

solet’srecorse
1

Weonlyhave0andI sofarbutthat’senoughtocreatethenext
valueinthesequence

Butwecan’treachbacktogetpreviousvalvesso
instead letsgettwo

Fibonaccisequences sidebysideoffsetby I

www.fib.gencan O 1
outputsofar

new
instanceof C

So wejustneedtocreatetwoFbgenerators onethathassteppedforwardby 1
andyieldtheirsumateachstep
tomoveaniteratorforwardwecallnext
So a fibgenC

nexta
for X y in Zip afibgenG

i

yieldXty

5

4. Partition Generator

(a) Construct the generator function partition_gen, which takes in a number n and returns a n-partition
iterator. An n-partition iterator yields partitions of n, where a partition of n is a list of integers whose
sum is n. The iterator should only return unique partitions; the order of numbers within a partition and
the order in which the partitions are returned does not matter.

def partition_gen(n):
���
>>> for partition in partition_gen(4): # note: order doesn�t matter
… print(partition)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
���

def yield_helper(j, k):

if ______________________________________________________________________________:

yield _______________________________________________________________________

elif ____________________________________________________________________________:

for _________________________________________________________________________:

yield ___________________________________________________________________

yield _______________________________________________________________________

yield _______________________________________________________________________________

forvalveinx
yieldvalue yieldfrom2

2 to CES

wewanttorotition Cate use K
Cli i i

caseddon’tusek
yieldhelper 2,2I large.SIuswehYohfafition It yieldhelped Few.heipercer

allpartitions Sj dIftyiednecpercc.cl 4ofsizeEk j o
yield.hu

elements

C

K O and j 0
Smallpart in yield helper j k k

k t smallpart
from yieldhelpercj K l

from
yieldhelperCn n

Trememberthe Fron

Similartocourtpartitions
cangiveagood

higpothesisforwhatjandkrepresent
Maytelet j Ethecurrent

numberwe’retryingtopartition couldalsousete

kEthelargestnumberwe’reallowedtopartition
with

smallest

to
yield

fromyieldhelperlan

Whycan’twejustrecorseonyieldpartitions
ideaSaywehave n 6 Thenyieldalluniquepartitionsof5andputifattheend

all uniquepartitionsof4maps23atmeend1 andsoon
Problems Doesn’t guaranteeuniqueness

2 I I l isa validpalliationof5 so
couldget 2 I I I l

111it l is avalidpartitionof4
socouldget4 2

samepartition

BASECASES
similartocountpartitions
if j o thenthereisekactyoneparlition