0 做题感受

mid-term的题目本身复杂度适中，在读题的时候建议结合例子理解，许多题目过于复杂，难以用英语的从句限定完全理解。注意：
（1）list的排序
（2）print的输出要使用%format格式，而不能使用f{}format格式
（3）及时test，不要一次性写很多逻辑
（4）python自带的IDLE没有自动补全代码的功能，coding时variable name建议尽量简单，如果过长，尽量复制黏贴，而不是每次手打
（5）虽然Eric之前课程材料中有非常多excellent的解题逻辑，可是如果无法完全掌握，在限时考试中还是建议用自己的逻辑
（6）coding时优先完成task，而不要想太多代码优化的问题

1 Longest sequence of deficient numbers

A number is said to be deficient if the sum of its proper divisors is strictly smaller than itself. For instance, the proper divisors of 10 are 1, 2 and 5, which add up to 8, which is strictly smaller than 10, hence 10 is deficient, whereas the proper divisors of 12 are 1, 2, 3, 4 and 6, which add up to 16, which is greater than or equal to 12, hence 12 is not deficient. Here is the list of all deficient numbers up to 50:
1,2,3,4,5,7,8,9,10,11,13,14,15,16,17,19,21,22,23,25,26,27,29,31,32,33,34,35,37,38,39,41,43,44,45,46,47,49,50
Write a program that prompts the user to input two strictly positive integers a and b and finds out the range of the longest sequence of deficient numbers between a and b. When that sequence is not unique, the range should be that of the sequence closest to a. If a is smaller than b then that sequence is increasing, whereas if a is greater than b then that sequence is decreasing.
Here is a typical interaction:

$ python3 deficient.py
Enter two strictly positive numbers: 10 twenty
Incorrect input, giving up.
$ python3 deficient.py
Enter two strictly positive numbers: 10 20 30
Incorrect input, giving up.
$ python3 deficient.py
Enter two strictly positive numbers: 0 10
Incorrect input, giving up.
$ python3 deficient.py
Enter two strictly positive numbers: 10 10
The longest sequence of deficient numbers between 10 and 10 ranges between 10 and 10.
$ python3 deficient.py
Enter two strictly positive numbers: 12 12
There is no deficient number between 12 and 12.
$ python3 deficient.py
Enter two strictly positive numbers: 10 20
The longest sequence of deficient numbers between 10 and 20 ranges between 13 and 17.
$ python3 deficient.py
Enter two strictly positive numbers: 20 10
The longest sequence of deficient numbers between 20 and 10 ranges between 17 and 13.
$ python3 deficient.py
Enter two strictly positive numbers: 3 20
The longest sequence of deficient numbers between 3 and 20 ranges between 7 and 11.
$ python3 deficient.py
Enter two strictly positive numbers: 20 3
The longest sequence of deficient numbers between 20 and 3 ranges between 17 and 13.

解答：

import sys

try:
    temp = input("Enter two strictly positive numbers: ").split()
    if len(temp) != 2:
        raise ValueError
    a, b = int(temp[0]), int(temp[1])
    if a <= 0 or b <= 0:
        raise ValueError
except ValueError:
    print("Incorrect input, giving up.")
    sys.exit()

def deficient(n):
    if n == 1:
        return True
    total = 1
    for i in range(2, n):
        if n % i == 0:
            total += i
    if total < n:
        return True
    else:
        return False

def longest_deficient(m, n):
    sequence = []
    flag = 0
    if m > n:
        flag = 1
        m, n = n, m
    for i in range(m, n + 1):
        if deficient(i):
            start, end = i, i
            for j in range(i + 1, n + 1):
                if deficient(j):
                    end = j
                else:
                    break
            sequence.append((start, end, end - start))
    if flag == 1:
        sequence.sort(key = lambda x: (-x[2], -x[1]))
    else:
        sequence.sort(key = lambda x: (-x[2], x[0]))
    return sequence[0]
    
result = longest_deficient(a, b)
start, end = result[0], result[1]
if a > b:
    start, end = end, start

print("The longest sequence of deficient numbers between %d and %d ranges between %d and %d." % (a, b, start, end))

2 Solving a multiplication

Write a program that solves a multiplication
OEE
x EE
-----
EOEE
EOE
-------
OOEE

where E stands for an even digit and O stands for an odd digit. Of course the leading digit of any of the 5 numbers cannot be 0. Two occurrences of E can refer to the same even digit or to two distinct even digits, and two occurrences of O can refer to the same odd digit or to two distinct odd digits.
The output of your program should be of the form above, with of course the Es and the Os being replaced by appropriate digits. Still spaces are irrelevant; in particular, it is irrelevant whether digits are separated by spaces, whether x (the multiplication sign) is followed by spaces, whether there are leading spaces at the beginning of the last line. The number of - on the separating lines is also irrelevant.
Your program should not make any assumption on the actual solution (which is unique), except obvious ones on the ranges of some values.
解答：

odd = [1, 3, 5, 7, 9]
even = [0, 2, 4, 6, 8]

for i in range(100, 1000):
    if (i % 10) not in even:
        continue
    if (i // 10 % 10) not in even:
        continue
    if (i // 100) not in odd:
        continue
    for j in range(10, 100):
        if (j % 10) not in even:
            continue
        if (j // 10) not in even:
            continue
        
        middle_1 = i * (j % 10)
        if len(str(middle_1)) != 4:
            continue
        if (middle_1 % 10) not in even:
            continue
        if (middle_1 //10 % 10) not in even:
            continue
        if (middle_1 //100 % 10) not in odd:
            continue
        if (middle_1 //1000) not in even:
            continue

        middle_2 = i * (j // 10)
        if len(str(middle_2)) != 3:
            continue
        if (middle_2 % 10) not in even:
            continue
        if (middle_2 // 10 % 10) not in odd:
            continue
        if (middle_2 // 100) not in even:
            continue

        result = i * j
        if len(str(result)) != 4:
            continue
        if (result % 10) not in even:
            continue
        if (result // 10 % 10) not in even:
            continue
        if (result // 100 % 10) not in odd:
            continue
        if (result // 1000) not in odd:
            continue

        print(' ', str(i), sep = '')
        print('x ', str(j), sep = '')
        print('----')
        print(str(middle_1))
        print(str(middle_2), ' ', sep = '')
        print('----')
        print(str(result))

3 Decoding a number

Write a program that implements a function named decode, called as decode(base, number) where base is any number b between 1 and 9, and number is any nonnegative integer n, seen as encoding a set S of nonnegative integers such that for all nonnegative integers i, i belongs to S i the ith digit of n written in base b is not equal to 0 (counting the digits from 0 and starting from the right). For instance, in base 3, 586 reads as 210201 because
586=2*3^5 +1*3^4 +0*3^3 +2*3^2 +0*3^1 +1*3^0
and so, with base equal to 3, 586 encodes {5, 4, 2, 0}.
解答：

def max_power(base, number):
    max_power = 0
    while (base ** max_power) <= number:
        max_power += 1
    if max_power != 0:
        max_power -= 1
    return max_power

def decode(base, number):
    upper = max_power(base, number)
    candidate = [0] * (upper) + [upper]
    number -= (number // (base ** upper)) * (base ** upper)

    while number != 0:
        power = max_power(base, number)
        a = base ** power
        b = number // a
        candidate[power] = power
        if power == 0:
            candidate[0] = -1
        number -= a * b

    code = []
    for i in candidate:
        if i == -1:
            code.append(0)       
        if i != 0 and i != -1:
            code.append(i)
    code.sort(reverse= True)

    if not code:
        print('{}')
    else:
        print('{', sep = '', end = '')
        for j in range(len(code)):
            if j == len(code) - 1:
                print(code[j], '}', sep = '', end = '')
            else:
                print(code[j], ', ', sep= '', end = '')
        print()

decode(2, 11)
decode(3, 586)
decode(8, 4223296)
decode(9, 0)