CS61A 2022 fall HW 01: Functions, Control

HW01对应的是Textbook的1.1和1.2

Q1: A Plus Abs B

• 题目：

  Fill in the blanks in the following function for adding a to the absolute value of b, without calling abs. You may not modify any of the provided code other than the two blanks.

  from operator import add, subdef 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>>> a_plus_abs_b(-1, 4)3>>> a_plus_abs_b(-1, -4)3"""if b < 0:f = _____else:f = _____return f(a, b)
  

• solution

      if b < 0:f = subelse:f = addreturn f(a, b)
  

  在终端里面输入python ok -q a_plus_abs_b

  

  这题其实一开始我没反应过来，愣了一下，模块也能赋值给变量

  • 再验证一下这种用法

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-k1wdMDJ4-1674571607986)(null)]

Q2: Two of Three

• 题目

  Write a function that takes three positive numbers as arguments and returns the sum of the squares of the two smallest numbers. Use only a single line for the body of the function.

  def two_of_three(i, j, k):"""Return m*m + n*n, where m and n are the two smallest members of thepositive numbers i, j, and k.>>> two_of_three(1, 2, 3)5>>> two_of_three(5, 3, 1)10>>> two_of_three(10, 2, 8)68>>> two_of_three(5, 5, 5)50"""return _____
  

  Hint: Consider using the max or min function:

  >>> max(1, 2, 3)
  3
  >>> min(-1, -2, -3)
  -3
  

• solution

  呃，写这个的时候得把copilot关掉…不然copilot秒解

  • 看到hint其实思路就比较清晰了

    把三个的平方和加起来，然后减掉最大的那个数的平方

    return i*i + j*j + k*k - max(i, j, k)**2
    

  ---

  或者还有种方法

  return min(i*i+j*j,i*i+k*k,j*j+k*k)
  

• python ok -q two_of_three

  

Q3: Largest Factor

• Write a function that takes an integer n that is greater than 1 and returns the largest integer that is smaller than n and evenly divides n.

  def largest_factor(n):"""Return the largest factor of n that is smaller than n.>>> largest_factor(15) # factors are 1, 3, 55>>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 4040>>> largest_factor(13) # factor is 1 since 13 is prime1""""*** YOUR CODE HERE ***"
  

Hint: To check if b evenly divides a, you can use the expression a % b == 0, which can be read as, “the remainder of dividing a by b is 0.”

• solution

  def largest_factor(n):"""Return the largest factor of n that is smaller than n.>>> largest_factor(15) # factors are 1, 3, 55>>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 4040>>> largest_factor(13) # factor is 1 since 13 is prime1""""*** YOUR CODE HERE ***"newlis = []for i in range(1,n):if n % i == 0:newlis.append(i)return newlis[len(newlis)-1]
  

  ---

  也可以反向做

  	factor = n - 1while factor > 0:if n % factor == 0:return factorfactor -= 1
  

Q4: Hailstone

这个真是个经典例子， 在Linux C编程里讲到死循环的时候，还有邓俊辉《数据结构》里面讲到什么是算法的时候（考虑有穷性），都用到了这个例子

• 题目

  Douglas Hofstadter’s Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle.

  1. Pick a positive integer n as the start.
  2. If n is even, divide it by 2.

3. If n is odd, multiply it by 3 and add 1.
4. Continue this process until n is 1.

The number n will travel up and down but eventually end at 1 (at least for all numbers that have ever been tried – nobody has ever proved that the sequence will terminate). Analogously（类似地）, a hailstone travels up and down in the atmosphere before eventually landing on earth.

This sequence of values of n is often called a Hailstone sequence. Write a function that takes a single argument with formal parameter name n, prints out the hailstone sequence starting at n, and returns the number of steps in the sequence:

def hailstone(n):"""Print the hailstone sequence starting at n and return itslength.>>> a = hailstone(10)105168421>>> a7>>> b = hailstone(1)1>>> b1""""*** YOUR CODE HERE ***"

Hailstone sequences can get quite long! Try 27. What’s the longest you can find?

Note that if n == 1 initially, then the sequence is one step long.
Hint: Recall the different outputs from using regular division / and floor division //

• solution

  一开始我补充了这个代码，好像导致死循环了…?

      length = 1while n!=1:print(n)length += 1if n % 2 == 0:n /= 2if n % 2 != 0:n = 3 * n + 1print(1)return length

  

  

  然后我改成了 n //= 2，还是死循环啊啊啊啊啊

  ---

  恍然大悟！下面这两个if 不构成选择结构，还是顺序结构！！！

  如果n执行完第一个if变成奇数的话，他还会执行第二个if…呜呜呜

          if n % 2 == 0:n /= 2if n % 2 != 0:n = 3 * n + 1
  

  另外死循环主要是看控制条件哪里出错了，所以原因就应该去n上面找，按照这个思路来

  
  def hailstone(n):"""Print the hailstone sequence starting at n and return itslength.>>> a = hailstone(10)105168421>>> a7>>> b = hailstone(1)1>>> b1""""*** YOUR CODE HERE ***"length = 1while n != 1:print(n)length += 1if n % 2 == 0:n //= 2elif n % 2 != 0:n = 3 * n + 1print(1)return length

这个ok的评测机制应该是用的python的Doctests吧🤔

orz，怎么说呢，这个作业，反正是我在大学没有的体验

• 最后给的这个hailstone猜想的拓展阅读材料挺有意思的
  • https://www.quantamagazine.org/mathematician-proves-huge-result-on-dangerous-problem-20191211
• 更好玩的是它给的一个网站
  • https://www.dcode.fr/collatz-conjecture