一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 568|回复: 8
收起左侧

[CS61A]Discussion02:Recursion

[复制链接] |试试Instant~ |关注本帖
sky420 发表于 2015-5-6 22:30:08 | 显示全部楼层 |阅读模式

[其他]cs61a #1 - 4@UCBerkely

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 AveMaleficum 于 2015-5-7 01:34 编辑

同上一个lab一样是对recursion的学习,请大家尽量用纸笔完成discussion
http://gaotx.com/cs61a//disc/disc02.pdf


补充内容 (2015-5-9 13:05):
我的答案
http://gaotx.com/blogs/2015/05/10/cs61a-disc02/

评分

1

查看全部评分

AveMaleficum 发表于 2015-5-7 01:35:07 | 显示全部楼层
这个discussion都可以加学分的。
怎么才能证明认真做了这个discussion?手机拍图片?
回复 支持 反对

使用道具 举报

 楼主| sky420 发表于 2015-5-7 01:49:11 | 显示全部楼层
嗯,也是个办法,不过有的画environment diagram,画一个一张纸就满了。
回复 支持 反对

使用道具 举报

FFFelix 发表于 2015-5-7 08:57:13 | 显示全部楼层
sky420 发表于 2015-5-7 01:49
嗯,也是个办法,不过有的画environment diagram,画一个一张纸就满了。

有的一张纸都画不下
回复 支持 反对

使用道具 举报

 楼主| sky420 发表于 2015-5-7 09:58:12 | 显示全部楼层
FFFelix 发表于 2015-5-7 08:57
有的一张纸都画不下

恩恩,加油吧。不过画一画确实有助于理解
回复 支持 反对

使用道具 举报

geminiiiiiii 发表于 2015-5-10 21:00:04 | 显示全部楼层
1.1
#1
def countdown(n):

        if n <= 0:
                return
        else:
                print(n)
                countdown(n - 1)
#2
def countup(n):
        if n == 1:
                print(1)
                return
        else:
                countdown(n - 1)
                print(n)
#3
def expt(base, power):
        if power == 0:
                return 1
        elif power < 0:
                return expt(base, power+1) / base
        else:
                return expt(base, power-1) * base
#4
def is_prime(n):
#5
def sum_primes_up_to(n):
        if n == 2:
                return 2
        elif is_prime(n):
                return sum_primes_up_to(n-1) + n
        else:
                return sum_primes_up_to(n-1)
2.1
#1
def count_stair_ways(n):
        if n == 1:
                return 1
        elif n ==2:
                return 2
        else:
                count_stair_ways(n-1) + count_stair_ways(n-2)

#2
def pascal(row, column):
        if column < 0 or row < 0:
                return 0
        elif column ==0:
                return 1
        else:
                return pascal(row-1, column)+ pascal(row-1, column-1)
#3
def has_sum(sum, n1, n2):
        if sum < min(ni,n2)
                return False
        elif sum == n1 or sum ==n2:
                return True
        else: has_sum(sum-n1, n1, n2) or has_sum(sum-n2, n1, n2)




评分

1

查看全部评分

回复 支持 反对

使用道具 举报

go7going 发表于 2015-5-13 00:56:30 | 显示全部楼层
这个discussion的代码并不难 难的是算法
对于木有学过算法的小白 基本上都是看答案做出来的=。=

""""
def countdown(n):
    if n>0:
        print(n)
        return countdown(n-1)

countdown(5)
"""""
""""
def expt(base, power):
    if power==0:
        return 1
    elif power<0:
        return expt(base,power+1)/base
    else:
        return expt(base, power-1)*base
print expt(3,2)

"""""
""""
def is_prime(n):
    def helper(k):
        if k >= n:
         return True
        if n % k == 0:
         return False
        return helper(k + 1)
    return helper(2)



def sum_primes_up_to(n):
    if n<=1:
        return 0
    elif is_prime(n):
        return n+sum_primes_up_to(n-1)
    else:
        return sum_primes_up_to(n-1)

print sum_primes_up_to(5)
"""""
""""
def count_stair_ways(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        n==3
        return 3
    return count_stair_ways(n-1) + count_stair_ways(n-2)

def pascal(row, column):
    if column == 0:
        return 1

    elif row == 0:
        return 0
    else:
        return pascal(row - 1, column) + pascal(row - 1, column - 1)


def has_sum(sum, n1, n2):

    if sum == n1 or sum == n2:
        return True
    if sum < min(n1, n2):
        return False
    return has_sum(sum - n1, n1, n2) or has_sum(sum - n2, n1, n2)

another way:
这道题感觉很难想出来 尤其是木有学算法的情况下。
def has_sum(sum, n1, n2):
    def helper(cur_sum):
        if cur_sum == sum:
            return True
        if cur_sum > sum:
            return False
        return helper(cur_sum + n1) or helper(cur_sum + n2)
    return helper(0)
"""""
""""
def sum_range(lower, upper):
    def summed(print_min, print_max):
        if lower <= print_min and print_max <= upper:
            return True
        if upper < print_min:
            return False
        return summed(print_min + 50, print_max + 60) or summed(print_min + 130, print_max + 140)
    return summed(0, 0)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

jy_121 发表于 2015-5-18 11:27:49 | 显示全部楼层
# 1. Print out a countdown using recursion.

def countdown(n):
        if(n <= 0):
                return
        print(n)
        countdown(n-1)


#2.  Is there an easy way to change countdown to count up instead?

Move the print statement to after the recursive call.


#3.  Write a procedure expt(base, power), which implements the exponent function.

def expt(base, power):
        if(power == 0):
                return 1
        else:
                return base*expt(base,power - 1)


#4.  Fill in the is prime function, which returns True if n is a prime number and False otherwise.
def is_prime(n):
        def helper(k):
                if(k >= n):
                        return True
                if(n % k == 0):
                        return False
                return helper(k+1)
        return helper(2)


#5.  Write sum primes up to(n), which sums up every prime up to and including n. Assume you have an is prime() predicate.

def sum_primes_up_to(n):
        if(n == 1):
                return n
        elif is_prime(n)
                return n + sum_primes_up_to(n-1)
        else:
                return sum_primes_up_to(n-1)


#2.1  Exercises:
        def count_stair_ways(n):
                if(n == 1):
                        return 1
                elif(n == 2):
                        return 2
                else:
                        return count_stair_ways(n-1) + count_stair_ways(n-2)


#2.2  Pascal’s triangle
        def pascal(row, column):
                if(column == 0):
                        return 1
                elif(row == 0):
                        return 0
                else:
                        return pascal(row - 1, column) + pascal(row - 1, column - 1)

#3           The TAs want to print handouts for their students.

def has_sum(sum, n1, n2):
        if(n1 == sum or sum == n2):
                return True
        if(sum < min(n1,n2)):
                return False
        else:
                return has_sum(sum - n1,n1,n2) or has_sum(sum - n2,n1,n2)

# Try a helper function: it makes the next one easier to solve
def has_sum(sum, n1, n2):
        def helper(cur_sum):
                if cur_sum == sum:
                        return True
                if cur_sum > sum:
                        return False
                return helper(cur_sum + n1) or helper(cur_sum + n2)
        return helper(0)


def summed(print_min, print_max):
        if lower <= print_min and print_max <= upper:
                return True
        if upper < print_min:
                return False
        return summed(print_min + 50, print_max + 60) or
                summed(print_min + 130, print_max + 140)
return summed(0, 0)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

wuxiaomin98 发表于 2015-5-23 08:31:05 | 显示全部楼层
# This is for cs61a discussion 2

def countdown(n):
    """ 1.1.1
    >>> countdown(3)
    3
    2
    1
    """
    if n <= 0:
            return
    print(n)
    countdown(n - 1)

def expt(base, power):
        """ 1.1.3

        >>> expt(3, 2)
        9
        >>> expt(2, 3)
        8
        """
        if power == 0:
                return 1
        else:
                return base * expt(base, power - 1)

def is_prime(n):
        # 1.1.4
    def helper(k):
        if(k >= n):
            return True
        if(n % k == 0):
            return False
        return helper(k+1)
    return helper(2)

def sum_primes_up_to(n):
        # 1.1.5
        if n <= 1:
                return 0
    elif is_prime(n):
            return n + sum_primes_up_to(n - 1)
    else:
            return sum_primes_up_to(n - 1)

def count_stair_ways(n):
        # 2.1.1
        if n == 1:
                return 1
        elif n == 2:
                return 2
        else:
                return count_stair_ways(n - 1) + count_stair_ways(n - 2)

def pascal(row, column):
        # 2.1.2
        if column == 0:
                return 1
        elif row == 0:
                return 0
        else:
                return pascal(row - 1, column) + pascal(row -  1, column - 1)
   
def has_sum(sum, n1, n2):
        # 2.1.3
        if sum == n1 or sum == n2:
                return True
        if sum < min(n1, n2):
                return False
        return has_sum(sum - n1, n1, n2) or has_sum(sum - n2, n1, n2)
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 12:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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