专门开一个帖分享cs61a的答案

lilirr

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

我在刷课的过程中有些地方卡壳了，就想着在网上搜一下答案
内容最全的github上sadly发现很多错误
就想着自己把已经校正了的答案合集发上来，供以后的小伙伴们参考
另一个帖子记录进度的我会把lj放在下一楼

lilirr

RayHL 发表于 2019-7-16 06:13
请问楼主每次使用ok test之后都要我登陆账号，有解决方法嘛

在最后加--local

lilirr

暂时就写到这里之后会继续更新der
希望对大噶有用！

lilirr

hw02

HW_SOURCE_FILE = 'hw02.py'
def square(x):
return x * x
def identity(x):
return x
triple = lambda x: 3 * x
increment = lambda x: x + 1
add = lambda x, y: x + y
mul = lambda x, y: x * y
def product(n, term):
"""Return the product of the first n terms in a sequence.
n -- a positive integer
term -- a function that takes one argument
>>> product(3, identity) # 1 * 2 * 3
6
>>> product(5, identity) # 1 * 2 * 3 * 4 * 5
120
>>> product(3, square) # 1^2 * 2^2 * 3^2
36
>>> product(5, square) # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
14400
>>> product(3, increment) # (1+1) * (2+1) * (3+1)
24
>>> product(3, triple) # 1*3 * 2*3 * 3*3
162
"""
count = 1
pro = 1
while count <= n:
pro *= term(count)
count += 1
return pro
# The identity function, defined using a lambda expression!
identity = lambda k: k
def factorial(n):
"""Return n factorial for n >= 0 by calling product.
>>> factorial(4)
24
>>> factorial(6)
720
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'factorial', ['Recursion', 'For', 'While'])
True
"""
return product(n,identity)
def make_adder(n):
"""Return a function that takes an argument K and returns N + K.
>>> add_three = make_adder(3)
>>> add_three(1) + add_three(2)
9
>>> make_adder(1)(2)
3
"""
def add_k(k):
return n + k
return add_k

复制代码

lilirr

另一个记录进度的帖子在这里https://www.1point3acres.com/bbs/thread-533071-1-1.html

lilirr

hw01

from operator import add, sub
def a_plus_abs_b(a, b):
"""Return a+abs(b), but without calling abs.
>>> a_plus_abs_b(2, 3)
5
>>> a_plus_abs_b(2, -3)
5
"""
if b < 0:
f = sub
else:
f = add
return f(a, b)
'''f应该是功能名'''
def two_of_three(a, b, c):
"""Return x*x + y*y, where x and y are the two largest members of the
positive numbers a, b, and c.
>>> two_of_three(1, 2, 3)
13
>>> two_of_three(5, 3, 1)
34
>>> two_of_three(10, 2, 8)
164
>>> two_of_three(5, 5, 5)
50
"""
return max(a*a+b*b, b*b+c*c, a*a+c*c)
def largest_factor(n):
"""Return the largest factor of n that is smaller than n.
>>> largest_factor(15) # factors are 1, 3, 5
5
>>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 40
40
>>> largest_factor(13) # factor is 1 since 13 is prime
1
"""
"""
def largest_factor(n):
fac = 2
b = n%fac
while b!= 0:
fac = fac + 1
b = n%fac
if fac != n:
return int(n/fac)
else:
return 1
"""
def if_function(condition, true_result, false_result):
"""Return true_result if condition is a true value, and
false_result otherwise.
>>> if_function(True, 2, 3)
2
>>> if_function(False, 2, 3)
3
>>> if_function(3==2, 3+2, 3-2)
1
>>> if_function(3>2, 3+2, 3-2)
5
"""
'''
if condition:
return true_result
else:
return false_result
'''
def with_if_statement():
"""
>>> with_if_statement()
1
"""
if c():
return t()
else:
return f()
def with_if_function():
return if_function(c(), t(), f())
def c():
"*** YOUR CODE HERE ***"
def t():
"*** YOUR CODE HERE ***"
def f():
"*** YOUR CODE HERE ***"
def hailstone(n):
"""Print the hailstone sequence starting at n and return its
length.
>>> a = hailstone(10)
10
5
16
8
4
2
1
>>> a
7
"""
'''
def hailstone(n):
a = 1
print(n)
while n!= 1:
if n%2 == 0:
n = n/2
a = a+1
print(int(n))
else:
n = n*3 +1
a = a+1
print(int(n))
return a
'''

复制代码

lilirr

hog proj

"""CS 61A Presents The Game of Hog."""
from dice import six_sided, four_sided, make_test_dice
from ucb import main, trace, interact
GOAL_SCORE = 100 # The goal of Hog is to score 100 points.
######################
# Phase 1: Simulator #
######################
def roll_dice(num_rolls, dice=six_sided):
"""Simulate rolling the DICE exactly NUM_ROLLS > 0 times. Return the sum of
the outcomes unless any of the outcomes is 1. In that case, return 1.
num_rolls: The number of dice rolls that will be made.
dice: A function that simulates a single dice roll outcome.
"""
# These assert statements ensure that num_rolls is a positive integer.
assert type(num_rolls) == int, 'num_rolls must be an integer.'
assert num_rolls > 0, 'Must roll at least once.'
# BEGIN PROBLEM 1
n = 1
sum = 0
one_occur = 0#出现之前必须定义一下
while n <= num_rolls:
a = dice()
if a == 1:
one_occur = 1#用这个来标记1是否出现
sum = sum + a
else:
sum = sum + a
n += 1
if one_occur == 1:
return 1
else:
return sum
# END PROBLEM 1
def free_bacon(score):
"""Return the points scored from rolling 0 dice (Free Bacon).
score: The opponent's current score.
"""
assert score < 100, 'The game should be over.'
# BEGIN PROBLEM 2
tens = score//10
ones = score%10
if tens < ones:
return 2 + ones - tens
else:
return 2 + tens - ones
# END PROBLEM 2
def take_turn(num_rolls, opponent_score, dice=six_sided):
"""Simulate a turn rolling NUM_ROLLS dice, which may be 0 (Free Bacon).
Return the points scored for the turn by the current player.
num_rolls: The number of dice rolls that will be made.
opponent_score: The total score of the opponent.
dice: A function that simulates a single dice roll outcome.
"""
# Leave these assert statements here; they help check for errors.
assert type(num_rolls) == int, 'num_rolls must be an integer.'
assert num_rolls >= 0, 'Cannot roll a negative number of dice in take_turn.'
assert num_rolls <= 10, 'Cannot roll more than 10 dice.'
assert opponent_score < 100, 'The game should be over.'
# BEGIN PROBLEM 3
if num_rolls == 0:
return free_bacon(opponent_score)
else:
return roll_dice(num_rolls,dice) #参数有默认值的也是需要传递的，否则更改不了
# END PROBLEM 3
def is_swap(score0, score1):
"""Return whether one of the scores is an integer multiple of the other."""
# BEGIN PROBLEM 4
if (score0 > 1) and (score1 > 1):
if (score0 % score1 == 0) or (score1 % score0 == 0):
return True
else:
return False
else:
return False
# END PROBLEM 4
def other(player):
"""Return the other player, for a player PLAYER numbered 0 or 1.
>>> other(0)
1
>>> other(1)
0
"""
return 1 - player
def silence(score0, score1):
"""Announce nothing (see Phase 2)."""
return silence
def play(strategy0, strategy1, score0=0, score1=0, dice=six_sided,
goal=GOAL_SCORE, say=silence):
"""Simulate a game and return the final scores of both players, with Player
0's score first, and Player 1's score second.
A strategy is a function that takes two total scores as arguments (the
current player's score, and the opponent's score), and returns a number of
dice that the current player wieu ron this turn.
strategy0: The strategy function for Player 0, who plays first.
strategy1: The strategy function for Player 1, who plays second.
score0: Starting score for Player 0
score1: Starting score for Player 1
dice: A function of zero arguments that simulates a dice roll.
goal: The game ends and someone wins when this score is reached.
say: The commentary function to call at the end of the first turn.
"""
player = 0 # Which player is about to take a turn, 0 (first) or 1 (second)
# BEGIN PROBLEM 5
while (score0 <goal) and (score1 <goal):#应该同时满足
if not player:#当第一位选手玩的时候
num_rolls = strategy0(score0, score1) #strategy0返回0号选手想要扔骰子的次数,这个时候直接调用就行，不用管细节，ph3才管
score0 += take_turn(num_rolls, score1, dice) #score0应该是累积的
else:
num_rolls = strategy1(score1,score0)
score1 += take_turn(num_rolls, score0, dice)
if is_swap(score0, score1): #第二个判断和次序没有关系，只要满足互为因数就交换
score0, score1 = score1, score0
player = other(player)
# END PROBLEM 5
say = say(score0,score1)#这个格式适合say返回一个功能，需要对这个不停赋值的
return score0, score1
#######################
# Phase 2: Commentary #
#######################
def say_scores(score0, score1):
"""A commentary function that announces the score for each player."""
print("Player 0 now has", score0, "and Player 1 now has", score1)
return say_scores
def announce_lead_changes(previous_leader=None):
"""Return a commentary function that announces lead changes.
>>> f0 = announce_lead_changes()
>>> f1 = f0(5, 0)
Player 0 takes the lead by 5
>>> f2 = f1(5, 12)
Player 1 takes the lead by 7
>>> f3 = f2(8, 12)
>>> f4 = f3(8, 13)
>>> f5 = f4(15, 13)
Player 0 takes the lead by 2
"""
def say(score0, score1):
if score0 > score1:
leader = 0
elif score1 > score0:
leader = 1
else:
leader = None
if leader != None and leader != previous_leader:
print('Player', leader, 'takes the lead by', abs(score0 - score1))
return announce_lead_changes(leader)
return say
def both(f, g):
"""Return a commentary function that says what f says, then what g says.
>>> h0 = both(say_scores, announce_lead_changes())
>>> h1 = h0(10, 0)
Player 0 now has 10 and Player 1 now has 0
Player 0 takes the lead by 10
>>> h2 = h1(10, 6)
Player 0 now has 10 and Player 1 now has 6
>>> h3 = h2(6, 18) # Player 0 gets 8 points, then Swine Swap applies
Player 0 now has 6 and Player 1 now has 18
Player 1 takes the lead by 12
"""
def say(score0, score1):
return both(f(score0, score1), g(score0, score1))
return say
def announce_highest(who, previous_high=0, previous_score=0):
"""Return a commentary function that announces when WHO's score
increases by more than ever before in the game.
>>> f0 = announce_highest(1) # Only announce Player 1 score gains
>>> f1 = f0(11, 0)
>>> f2 = f1(11, 1)
1 point! That's the biggest gain yet for Player 1
>>> f3 = f2(20, 1)
>>> f4 = f3(5, 20) # Player 1 gets 4 points, then Swine Swap applies
19 points! That's the biggest gain yet for Player 1
>>> f5 = f4(20, 40) # Player 0 gets 35 points, then Swine Swap applies
20 points! That's the biggest gain yet for Player 1
>>> f6 = f5(20, 55) # Player 1 gets 15 points; not enough for a new high
"""
assert who == 0 or who == 1, 'The who argument should indicate a player.'
# BEGIN PROBLEM 7
assert who == 0 or who == 1, 'The who argument should indicate a player.'
# BEGIN PROBLEM 7
def commentary_score(score0, score1):
if not who:
now_score = score0
else:
now_score = score1
#pre_high/score在右边不会在这个frame里创造变量，在左边会创造和上一个frame里的pre_high冲突导致无法read data
score_dif = now_score - previous_score
if score_dif > previous_high:#pre_high记录最大差值，只有新最大差值出现才打印，而非出现新最大值打印
if now_score - previous_score < 2:
print(score_dif,'point! That\'s the biggest gain yet for Player', who)
else:
print(score_dif,'points! That\'s the biggest gain yet for Player', who)
return announce_highest(who,score_dif, now_score)
else:
return announce_highest(who,previous_high, now_score)
return commentary_score
# END PROBLEM 7
#######################
# Phase 3: Strategies #
#######################
def always_roll(n):
"""Return a strategy that always rolls N dice.
A strategy is a function that takes two total scores as arguments (the
current player's score, and the opponent's score), and returns a number of
dice that the current player will roll this turn.
>>> strategy = always_roll(5)
>>> strategy(0, 0)
5
>>> strategy(99, 99)
5
"""
def strategy(score, opponent_score):
return n
return strategy
def make_averaged(fn, num_samples=1000):
"""Return a function that returns the average value of FN when called.
To implement this function, you will have to use *args syntax, a new Python
feature introduced in this project. See the project description.
>>> dice = make_test_dice(4, 2, 5, 1)
>>> averaged_dice = make_averaged(dice, 1000)
>>> averaged_dice()
3.0
"""
# BEGIN PROBLEM 8
def ret_average(*arg):
n = 0
sum = 0
while n< num_samples:
sum += fn(*arg)
n +=1
return sum/num_samples
return ret_average
# END PROBLEM 8
def max_scoring_num_rolls(dice=six_sided, num_samples=1000):
"""Return the number of dice (1 to 10) that gives the highest average turn
score by calling roll_dice with the provided DICE over NUM_SAMPLES times.
Assume that the dice always return positive outcomes.
>>> dice = make_test_dice(1, 6)
>>> max_scoring_num_rolls(dice)
1
"""
# BEGIN PROBLEM 9
n = 1
max_ave = 0
while n<=10:
now_ave = make_averaged(roll_dice)
if now_ave(n,dice) > max_ave:
max_ave = now_ave(n,dice)
max_roll = n
n += 1
return max_roll
# END PROBLEM 9
def winner(strategy0, strategy1):
"""Return 0 if strategy0 wins against strategy1, and 1 otherwise."""
score0, score1 = play(strategy0, strategy1)
if score0 > score1:
return 0
else:
return 1
def average_win_rate(strategy, baseline=always_roll(4)):
"""Return the average win rate of STRATEGY against BASELINE. Averages the
winrate when starting the game as player 0 and as player 1.
"""
win_rate_as_player_0 = 1 - make_averaged(winner)(strategy, baseline)
win_rate_as_player_1 = make_averaged(winner)(baseline, strategy)
return (win_rate_as_player_0 + win_rate_as_player_1) / 2
def run_experiments():
"""Run a series of strategy experiments and report results."""
if True: # Change to False when done finding max_scoring_num_rolls
six_sided_max = max_scoring_num_rolls(six_sided)
print('Max scoring num rolls for six-sided dice:', six_sided_max)
if False: # Change to True to test always_roll(8)
print('always_roll(8) win rate:', average_win_rate(always_roll(8)))
if False: # Change to True to test bacon_strategy
print('bacon_strategy win rate:', average_win_rate(bacon_strategy))
if False: # Change to True to test swap_strategy
print('swap_strategy win rate:', average_win_rate(swap_strategy))
if False: # Change to True to test final_strategy
print('final_strategy win rate:', average_win_rate(final_strategy))
"*** You may add additional experiments as you wish ***"
def bacon_strategy(score, opponent_score, margin=8, num_rolls=4):
"""This strategy rolls 0 dice if that gives at least MARGIN points, and
rolls NUM_ROLLS otherwise.
"""
# BEGIN PROBLEM 10
if free_bacon(opponent_score) >= margin:
return 0
else:
return num_rolls
# END PROBLEM 10
def swap_strategy(score, opponent_score, margin=8, num_rolls=4):
"""This strategy rolls 0 dice when it triggers a beneficial swap. It also
rolls 0 dice if it gives at least MARGIN points. Otherwise, it rolls
NUM_ROLLS.
"""
# BEGIN PROBLEM 11
if is_swap(score,opponent_score):
if score < opponent_score:
return 0
else:
return num_rolls
elif free_bacon(opponent_score) >= margin:
return 0
else:
return num_rolls
# END PROBLEM 11
def final_strategy(score, opponent_score):
"""Write a brief description of your final strategy.
*** YOUR DESCRIPTION HERE ***
"""
# BEGIN PROBLEM 12
return 4 # Replace this statement
# END PROBLEM 12
##########################
# Command Line Interface #
##########################
# NOTE: Functions in this section do not need to be changed. They use features
# of Python not yet covered in the course.
@main
def run(*args):
"""Read in the command-line argument and calls corresponding functions.
This function uses Python syntax/techniques not yet covered in this course.
"""
import argparse
parser = argparse.ArgumentParser(description="Play Hog")
parser.add_argument('--run_experiments', '-r', action='store_true',
help='Runs strategy experiments')
args = parser.parse_args()
if args.run_experiments:
run_experiments()

复制代码

lilirr

hw03

HW_SOURCE_FILE = 'hw03.py'
#############
# Questions #
#############
def has_seven(k):
"""Returns True if at least one of the digits of k is a 7, False otherwise.
>>> has_seven(3)
False
>>> has_seven(7)
True
>>> has_seven(2734)
True
>>> has_seven(2634)
False
>>> has_seven(734)
True
>>> has_seven(7777)
True
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'has_seven',
... ['Assign', 'AugAssign'])
True
"""
"*** YOUR CODE HERE ***"
if k<10:
return k%10 ==7
else:HW_SOURCE_FILE = 'hw03.py'
#############
# Questions #
#############
def has_seven(k):
"""Returns True if at least one of the digits of k is a 7, False otherwise.
>>> has_seven(3)
False
>>> has_seven(7)
True
>>> has_seven(2734)
True
>>> has_seven(2634)
False
>>> has_seven(734)
True
>>> has_seven(7777)
True
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'has_seven',
... ['Assign', 'AugAssign'])
True
"""
"*** YOUR CODE HERE ***"
if k<10:
return k%10 ==7
else:
return k%10 == 7 or has_seven(k//10)
def summation(n, term):
"""Return the sum of the first n terms in the sequence defined by term.
Implement using recursion!
>>> summation(5, lambda x: x * x * x) # 1^3 + 2^3 + 3^3 + 4^3 + 5^3
225
>>> summation(9, lambda x: x + 1) # 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
54
>>> summation(5, lambda x: 2**x) # 2^1 + 2^2 + 2^3 + 2^4 + 2^5
62
>>> # Do not use while/for loops!
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'summation',
... ['While', 'For'])
True
"""
assert n >= 1
"*** YOUR CODE HERE ***"
if n ==1:
return term (1) #base case
else:
return term(n)+summation(n-1,term)
def square(x):
return x * x
def identity(x):
return x
triple = lambda x: 3 * x
increment = lambda x: x + 1
add = lambda x, y: x + y
mul = lambda x, y: x * y
def accumulate(combiner, base, n, term):
"""Return the result of combining the first n terms in a sequence and base.
The terms to be combined are term(1), term(2), ..., term(n). combiner is a
two-argument commutative function.
>>> accumulate(add, 0, 5, identity) # 0 + 1 + 2 + 3 + 4 + 5
15
>>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
26
>>> accumulate(add, 11, 0, identity) # 11
11
>>> accumulate(add, 11, 3, square) # 11 + 1^2 + 2^2 + 3^2
25
>>> accumulate(mul, 2, 3, square) # 2 * 1^2 * 2^2 * 3^2
72
"""
"*** YOUR CODE HERE ***"
if n == 0:
return base
else:
return combiner(term(n),accumulate(combiner,base,n-1,term)) #一定要一个代表n情况的表达式和之后的循环
#除了tree recursion一般很少两个base case的，所以当写了两个bc看能不能合并否则可能报错
def summation_using_accumulate(n, term):
"""Returns the sum of term(1) + ... + term(n). The implementation
uses accumulate.
>>> summation_using_accumulate(5, square)
55
>>> summation_using_accumulate(5, triple)
45
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'summation_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
return accumulate(add,0,n,term)
def product_using_accumulate(n, term):
"""An implementation of product using accumulate.
>>> product_using_accumulate(4, square)
576
>>> product_using_accumulate(6, triple)
524880
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'product_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
return accumulate(mul,1,n,term)
def filtered_accumulate(combiner, base, pred, n, term):
"""Return the result of combining the terms in a sequence of N terms
that satisfy the predicate pred. combiner is a two-argument function.
If v1, v2, ..., vk are the values in term(1), term(2), ..., term(N)
that satisfy pred, then the result is
base combiner v1 combiner v2 ... combiner vk
(treating combiner as if it were a binary operator, like +). The
implementation uses accumulate.
>>> filtered_accumulate(add, 0, lambda x: True, 5, identity) # 0 + 1 + 2 + 3 + 4 + 5
15
>>> filtered_accumulate(add, 11, lambda x: False, 5, identity) # 11
11
>>> filtered_accumulate(add, 0, odd, 5, identity) # 0 + 1 + 3 + 5
9
>>> filtered_accumulate(mul, 1, greater_than_5, 5, square) # 1 * 9 * 16 * 25
3600
>>> # Do not use while/for loops or recursion
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'filtered_accumulate',
... ['While', 'For', 'Recursion'])
True
"""
def combine_if(x, y):
"*** YOUR CODE HERE ***"
if pred(x):
return combiner(x,y)
else:
return y
return accumulate(combine_if, base, n, term)
def odd(x):
return x % 2 == 1
def greater_than_5(x):
return x > 5
def make_repeater(f, n):
"""Return the function that computes the nth application of f.
>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 4)(5) # square(square(square(square(5))))
152587890625
>>> make_repeater(square, 0)(5)
5
"""
"*** YOUR CODE HERE ***"
'''第一个解法'''
'''if n == 0:
return identity
elif n ==1:
return f
else:
a = f
i = 1
while i < n:
a = compose1(a,f)
i = i+1
return a'''
'''第二个解法'''
return accumulate(compose1,lambda x: x,n,lambda x:f)#注意一定是lambdax:f，如果只是f在term(n)即f(n)的时候返回的一个int 返回的f而非f(x)说明x对f没有作用，即n对increment等函数没有影响，返回的只是一个函数而已
def compose1(f, g):
"""Return a function h, such that h(x) = f(g(x))."""
def h(x):
return f(g(x))
return h
###################
# Extra Questions #
###################
quine = """
"*** YOUR CODE HERE ***"
"""
def zero(f):
return lambda x: x
def successor(n):
return lambda f: lambda x: f(n(f)(x))
def one(f):
"""Church numeral 1: same as successor(zero)"""
"*** YOUR CODE HERE ***"
def two(f):
"""Church numeral 2: same as successor(successor(zero))"""
"*** YOUR CODE HERE ***"
three = successor(two)
def church_to_int(n):
"""Convert the Church numeral n to a Python integer.
>>> church_to_int(zero)
0
>>> church_to_int(one)
1
>>> church_to_int(two)
2
>>> church_to_int(three)
3
"""
"*** YOUR CODE HERE ***"
def add_church(m, n):
"""Return the Church numeral for m + n, for Church numerals m and n.
>>> church_to_int(add_church(two, three))
5
"""
"*** YOUR CODE HERE ***"
def mul_church(m, n):
"""Return the Church numeral for m * n, for Church numerals m and n.
>>> four = successor(three)
>>> church_to_int(mul_church(two, three))
6
>>> church_to_int(mul_church(three, four))
12
"""
"*** YOUR CODE HERE ***"
def pow_church(m, n):
"""Return the Church numeral m ** n, for Church numerals m and n.
>>> church_to_int(pow_church(two, three))
8
>>> church_to_int(pow_church(three, two))
9
"""
"*** YOUR CODE HERE ***"
return k%10 == 7 or has_seven(k//10)
def summation(n, term):
"""Return the sum of the first n terms in the sequence defined by term.
Implement using recursion!
>>> summation(5, lambda x: x * x * x) # 1^3 + 2^3 + 3^3 + 4^3 + 5^3
225
>>> summation(9, lambda x: x + 1) # 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
54
>>> summation(5, lambda x: 2**x) # 2^1 + 2^2 + 2^3 + 2^4 + 2^5
62
>>> # Do not use while/for loops!
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'summation',
... ['While', 'For'])
True
"""
assert n >= 1
"*** YOUR CODE HERE ***"
if n ==1:
return term (1) #base case
else:
return term(n)+summation(n-1,term)
def square(x):
return x * x
def identity(x):
return x
triple = lambda x: 3 * x
increment = lambda x: x + 1
add = lambda x, y: x + y
mul = lambda x, y: x * y
def accumulate(combiner, base, n, term):
"""Return the result of combining the first n terms in a sequence and base.
The terms to be combined are term(1), term(2), ..., term(n). combiner is a
two-argument commutative function.
>>> accumulate(add, 0, 5, identity) # 0 + 1 + 2 + 3 + 4 + 5
15
>>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
26
>>> accumulate(add, 11, 0, identity) # 11
11
>>> accumulate(add, 11, 3, square) # 11 + 1^2 + 2^2 + 3^2
25
>>> accumulate(mul, 2, 3, square) # 2 * 1^2 * 2^2 * 3^2
72
"""
"*** YOUR CODE HERE ***"
if n == 0:
return base
else:
return combiner(term(n),accumulate(combiner,base,n-1,term)) #一定要一个代表n情况的表达式和之后的循环
#除了tree recursion一般很少两个base case的，所以当写了两个bc看能不能合并否则可能报错
def summation_using_accumulate(n, term):
"""Returns the sum of term(1) + ... + term(n). The implementation
uses accumulate.
>>> summation_using_accumulate(5, square)
55
>>> summation_using_accumulate(5, triple)
45
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'summation_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
return accumulate(add,0,n,term)
def product_using_accumulate(n, term):
"""An implementation of product using accumulate.
>>> product_using_accumulate(4, square)
576
>>> product_using_accumulate(6, triple)
524880
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'product_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
return accumulate(mul,1,n,term)
def filtered_accumulate(combiner, base, pred, n, term):
"""Return the result of combining the terms in a sequence of N terms
that satisfy the predicate pred. combiner is a two-argument function.
If v1, v2, ..., vk are the values in term(1), term(2), ..., term(N)
that satisfy pred, then the result is
base combiner v1 combiner v2 ... combiner vk
(treating combiner as if it were a binary operator, like +). The
implementation uses accumulate.
>>> filtered_accumulate(add, 0, lambda x: True, 5, identity) # 0 + 1 + 2 + 3 + 4 + 5
15
>>> filtered_accumulate(add, 11, lambda x: False, 5, identity) # 11
11
>>> filtered_accumulate(add, 0, odd, 5, identity) # 0 + 1 + 3 + 5
9
>>> filtered_accumulate(mul, 1, greater_than_5, 5, square) # 1 * 9 * 16 * 25
3600
>>> # Do not use while/for loops or recursion
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'filtered_accumulate',
... ['While', 'For', 'Recursion'])
True
"""
def combine_if(x, y):
"*** YOUR CODE HERE ***"
if pred(x):
return combiner(x,y)
else:
return y
return accumulate(combine_if, base, n, term)
def odd(x):
return x % 2 == 1
def greater_than_5(x):
return x > 5
def make_repeater(f, n):
"""Return the function that computes the nth application of f.
>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 4)(5) # square(square(square(square(5))))
152587890625
>>> make_repeater(square, 0)(5)
5
"""
"*** YOUR CODE HERE ***"
'''第一个解法'''
'''if n == 0:
return identity
elif n ==1:
return f
else:
a = f
i = 1
while i < n:
a = compose1(a,f)
i = i+1
return a'''
'''第二个解法'''
return accumulate(compose1,lambda x: x,n,lambda x:f)#注意一定是lambdax:f，如果只是f在term(n)即f(n)的时候返回的一个int 返回的f而非f(x)说明x对f没有作用，即n对increment等函数没有影响，返回的只是一个函数而已
def compose1(f, g):
"""Return a function h, such that h(x) = f(g(x))."""
def h(x):
return f(g(x))
return h
###################
# Extra Questions #
###################
quine = """
"*** YOUR CODE HERE ***"
"""
def zero(f):
return lambda x: x
def successor(n):
return lambda f: lambda x: f(n(f)(x))
def one(f):
"""Church numeral 1: same as successor(zero)"""
"*** YOUR CODE HERE ***"
def two(f):
"""Church numeral 2: same as successor(successor(zero))"""
"*** YOUR CODE HERE ***"
three = successor(two)
def church_to_int(n):
"""Convert the Church numeral n to a Python integer.
>>> church_to_int(zero)
0
>>> church_to_int(one)
1
>>> church_to_int(two)
2
>>> church_to_int(three)
3
"""
"*** YOUR CODE HERE ***"
def add_church(m, n):
"""Return the Church numeral for m + n, for Church numerals m and n.
>>> church_to_int(add_church(two, three))
5
"""
"*** YOUR CODE HERE ***"
def mul_church(m, n):
"""Return the Church numeral for m * n, for Church numerals m and n.
>>> four = successor(three)
>>> church_to_int(mul_church(two, three))
6
>>> church_to_int(mul_church(three, four))
12
"""
"*** YOUR CODE HERE ***"
def pow_church(m, n):
"""Return the Church numeral m ** n, for Church numerals m and n.
>>> church_to_int(pow_church(two, three))
8
>>> church_to_int(pow_church(three, two))
9
"""
"*** YOUR CODE HERE ***"

复制代码

lilirr

lab02

"""Lab 2: Lambda Expressions and Higher Order Functions"""
# Lambda Functions
def lambda_curry2(func):
"""
Returns a Curried version of a two-argument function FUNC.
>>> from operator import add
>>> curried_add = lambda_curry2(add)
>>> add_three = curried_add(3)
>>> add_three(5)
8
"""
def curry2(x):
def curry3(y):
return func(x,y)
return curry3
return curry2

复制代码

lilirr

lab02_extra

""" Optional problems for lab02 """
from lab02 import *
# Higher Order Functions
def compose1(f, g):
"""Return the composition function which given x, computes f(g(x)).
>>> add_one = lambda x: x + 1 # adds one to x
>>> square = lambda x: x**2
>>> a1 = compose1(square, add_one) # (x + 1)^2
>>> a1(4)
25
>>> mul_three = lambda x: x * 3 # multiplies 3 to x
>>> a2 = compose1(mul_three, a1) # ((x + 1)^2) * 3
>>> a2(4)
75
>>> a2(5)
108
"""
return lambda x: f(g(x))
def composite_identity(f, g):
"""
Return a function with one parameter x that returns True if f(g(x)) is
equal to g(f(x)). You can assume the result of g(x) is a valid input for f
and vice versa.
>>> add_one = lambda x: x + 1 # adds one to x
>>> square = lambda x: x**2
>>> b1 = composite_identity(square, add_one)
>>> b1(0) # (0 + 1)^2 == 0^2 + 1
True
>>> b1(4) # (4 + 1)^2 != 4^2 + 1
False
"""
def is_true(x):
return compose1(f,g)(x) == compose1(g,f)(x)
return is_true
def count_cond(condition):
"""Returns a function with one parameter N that counts all the numbers from
1 to N that satisfy the two-argument predicate function CONDITION.
>>> count_factors = count_cond(lambda n, i: n % i == 0)
>>> count_factors(2) # 1, 2
2
>>> count_factors(4) # 1, 2, 4
3
>>> count_factors(12) # 1, 2, 3, 4, 6, 12
6
>>> is_prime = lambda n, i: count_factors(i) == 2
>>> count_primes = count_cond(is_prime)
>>> count_primes(2) # 2
1
>>> count_primes(3) # 2, 3
2
>>> count_primes(4) # 2, 3
2
>>> count_primes(5) # 2, 3, 5
3
>>> count_primes(20) # 2, 3, 5, 7, 11, 13, 17, 19
8
"""
def count_num(n):
i, sum = 1, 0
while i<= n:
if condition(n,i):
sum +=1
i +=1
return sum
return count_num
def cycle(f1, f2, f3):
"""Returns a function that is itself a higher-order function.
>>> def add1(x):
... return x + 1
>>> def times2(x):
... return x * 2
>>> def add3(x):
... return x + 3
>>> my_cycle = cycle(add1, times2, add3)
>>> identity = my_cycle(0)
>>> identity(5)
5
>>> add_one_then_double = my_cycle(2)
>>> add_one_then_double(1)
4
>>> do_all_functions = my_cycle(3)
>>> do_all_functions(2)
9
>>> do_more_than_a_cycle = my_cycle(4)
>>> do_more_than_a_cycle(2)
10
>>> do_two_cycles = my_cycle(6)
>>> do_two_cycles(1)
19
"""
"*** YOUR CODE HERE ***"
def take_arg_n(n):
def take_arg_x(x):
sum_res,i = x,0
ori_ls = [f1,f2,f3]
func_ls = ori_ls*(n//3) + ori_ls[0:n%3]
if n == 0:
return x
else:
while i<n:
sum_res = func_ls[i](sum_res)
i +=1
return sum_res
return take_arg_x
return take_arg_n

复制代码

lilirr

lab03

""" Lab 3: Recursion and Midterm Review """
def gcd(a, b):
"""Returns the greatest common divisor of a and b.
Should be implemented using recursion.
>>> gcd(34, 19)
1
>>> gcd(39, 91)
13
>>> gcd(20, 30)
10
>>> gcd(40, 40)
40
"""
"*** YOUR CODE HERE ***"
if a%b == 0 or b%a == 0:
return min(a,b)
else:
return gcd(b,a%b)
def hailstone(n):
"""Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.
>>> a = hailstone(10)
10
5
16
8
4
2
1
>>> a
7
"""
"*** YOUR CODE HERE ***"
print(n)
step = 1
while n!=1:
if n%2 == 0:
n = int(n/2)
else:
n = int(n*3+1)
print(n)
step +=1
return step

复制代码

专门开一个帖分享cs61a的答案

注册一亩三分地论坛，查看更多干货！

评分

相关帖子