CentraleSupélec LMF, UMR CNRS 9021
Département informatique Laboratoire Méthodes Formelles
Bât Breguet, 3 rue Joliot-Curie Bât 650 Ada Lovelace, Université Paris Sud
91190 Gif-sur-Yvette, France Rue Noetzlin, 91190 Gif-sur-Yvette, France
TD n°2 et 3 SIP

Le sujet SIP-TD02-03.pdf

Éléments de corrigé

#############
# Exercice 1
#############
# Exemple of documentation in docstrings.
# A docstring is a string enclosed between triple double quotes. It documents
# the entity that is just above it. Here, the docstring documents the "max" function.
# The documentation can be accessed through the __doc__ attribute of the item, or 
# with the "help()" function. Try "help(max)" after loading this file in the python console.
# Lines that start with ">>>" are considered as tests, and the following line gives the expected result.
# These tests can be run using the testmod() function of the doctest module (see at the end of this file).
def max(a,b) :
    """
    :param a: an integer
    :param b: an integer
    :return: the largest of a and b
    >>> max(2,3)
    3
    >>> max(2,2)
    2
    >>> max(3,2)
    3
    """
    if a > b :
        return a
    else:
        return b

def max3(a, b, c):
    return max(max(a, b), c)

#############
# Exercice 2
#############
# On ne peut pas mettre un argument positionnel après un argument par mot-clef
def print_argument(a, b = 6) :
    print("Arguments: {} and {}".format(a, b))

#############
# Exercice 3
#############
def euclidian_div(a, b, euclidian=True, remainder=False) :
    if euclidian :
        if remainder:
            return (a//b, a%b)
        else:
            return a//b
    return a/b
# euclidian étant par défaut True, il suffit de préciser que remainder est True lui aussi
euclidian_div(2,3,remainder=True)
# Cela donne la même chose que :
euclidian_div(2,3,True,True)

#############
# Exercice 4
#############
balance = 0

def deposit(amount) :
    global balance
    balance += amount

def withdraw(amount) :
    global balance
    if amount > balance :
        amount = balance
    balance-= amount
    return amount

#############
# Exercice 5
#############
def variadic(*args, **kwargs):
    print("Positional: ", args)
    print("Keyword: ", kwargs)

#############
# Exercice 6
#############
# sum(l) returns the sum of the elements of list l
def average(*numbers):
    length = len(numbers)
    if length == 0 :
        return None
    else:
        return sum(numbers) / length

#############
# Exercice 7
#############
# Version using "continue" to skip multiples of 5
def mult_of_3_not_5(n):
    for i in range(n) :
        if i % 5 == 0 :
            continue  # skip multiples of 5
        if i % 3 == 0 :
            print(i)

# A better way to do the same thing
def mult_of_3_not_5_ok(n) :
    for i in range(n) :
        if (i % 5 != 0) and (i % 3 == 0) :
            print(i)

## First divider of an integer n
# We assume that we want the first divider that is greater than 1...

# A version with a while loop
def first_divider_naive(n) :
    div = 2
    while n % div != 0 :
        div += 1
    return div

# A version with a for loop
def first_divider_naive_2(n):
    for div in range(2,n+1) :
        if n % div == 0 :
                return div

# A version with a for loop and a break, as required in the text of the question
def first_divider_naive_3(n):
    for div in range(2,n+1) :
        if n % div == 0 :
            break
    return div

# An optimized version that looks for dividers only up to the square root of n
import math
def first_divider(n):
    for div in range(2,math.floor(math.sqrt(n)+1)) :
        if n % div == 0 :
                return div
    return n

#############
# Exercice 8
#############
# A prime number has no other dividers that 1 and itself
def is_prime(n):
    return first_divider(n) == n

# Check if the Goldbach conjecture is true for n
def is_goldbach(n) :
    # Get the primes smaller than n
    primes = [p for p in range(2,n) if is_prime(p)]
    OK = False
    for p in primes :
        if n-p in primes :
            # If both p and n-p are primes, n is the sum of two primes
            return True
    # We did not find a pair of primes whose sum is n
    return False

# Check if all even numbers greater that 2 up to n satisfy the Golbach conjecture
def goldbach(n) :
    # The first even number greater that 2 is 4, then we step by 2 and stop before n+1
    for k in range(4, n+1, 2) :
        if not is_goldbach(k) :
            return False
    return True

#############
# Exercice 9
#############
# Assuming we can move n-1 disks from tower i to tower k using tower j as a temporary place,
# it is easy to do the same for n disks :
#   - firstly, move n-1 disks from i to j using k as a temporary tower
#   - secondly, move the remaining tower from i to k
#   - finally, move n-1 disks from the temporary tower j to tower k using i as the temporary tower
# Proving that these moves obeys the movement rules and give the correct result is not so easy.
def hanoi(n, i, j, k) :
    if n > 0 :
        hanoi(n - 1, i, k, j)
        print("Move one disk from {} to {}".format(i,k))
        hanoi(n - 1, j, i, k)

#############
# Exercice 10
#############
# The "normal" iterative version
def digit_sum_iter(n) :
    digsum = 0
    while n > 0 :
        digsum += n % 10  # n%10 is the last digit of n
        n //= 10          # n//10 is n without its last digit
    return digsum

# A version that goes through the digits by iterating over the string that represents n
def digit_sum2(n) :
    return sum([int(d) for d in str(n)])

# Recursive version
def digit_sum_rec(n) :
    if n < 10 :
        return n
    return n % 10 + digit_sum_rec(n // 10)

# A recursive version that goes through the digits by slicing the string that represents n
# (May not be the most efficient way to do this!)
def digit_sum_rec2(n) :
    if len(str(n)) == 1 :
        return int(n)
    return int(str(n)[0]) + digit_sum_rec2(str(n)[1:])

#############
# Exercice 11
#############
# Digital root: apply digit_sum until the result fits on one digit
def digital_root_iter(n) :
    while n > 9 :
        n = digit_sum_iter(n)
    return n

def digital_root_rec(n) :
    if n > 9 :
        return digital_root_rec(digit_sum_rec(n))
    return n

#############
# Exercice 12
#############
# A function that returns a dictionary of the frequency of each letter in a string
# The complexity of this function is proportional to the length of the string
# because accessing a dictionary entry is made in (amortized) constant time.
def frequencies(s):
    freq = {}
    for l in s:
        if l in freq :
            freq[l] += 1
        else:
            freq[l] = 1
    return freq

# s1 and s2 are anagrams if they have the same frequencies
# The complexity of this function is proportional to the sum of the lengths of the strings.
# Sorting the strings and comparing the results is at least proportional to n.ln(n) 
# if n is the length of the strings.
def anagram(s1, s2) :
    f1 = frequencies(s1.replace(' ', '').lower())
    f2 = frequencies(s2.replace(' ', '').lower())
    return f1 == f2

#############
# Exercice 13
#############
# The first version returns -1 as soon as the searched element is not at the first position in the list.
# The second version returns len(i)-1 instead of -1 when the element is not in the list
# The third version returns -1 when the searched item is not the last one in the list
# The fourth version skips the first item in the list, and returns 0 instead of -1 when the item is not found in the list
# The fifth version loops forever when the searched item is not the first one (i is not incremented)
# The last version always returns -1 (it does not enter the loop because p is initially -1).

# A working version is :
def occ(el, li):
    for i in range(len(li)) :
        if el == li[i] :
            return i
    return -1

#############
# Exercice 14
#############
# Reversing a list in an iterative way:
# We go through the list in reverse order and append each item to the resulting list
def reverse_iter(l):
    res = []
    # We start at len(l)-1, the position of the last item, and go backwards to 0
    for i in range(len(l)-1, -1, -1) :
        res.append(l[i])
    return res

# Reversing a list in a recursive way:
# We append the head of the list to the reversed tail of the list
# (The head of a list is its first item, the tail is the list of the remaining items)
def reverse_rec(l):
    if len(l) < 2 :
        return l
    ll = reverse_rec(l[1:])
    ll.append(l[0])
    return ll

# More efficient recursive version, using an "accumulator" to build the result.
# reverse_aux is an auxiliary function which takes two arguments:
#   l is the remaining items of the list to inverse
#   res is the prefix of the inverted list
def reverse_aux(l, res) :
    if len(l) == 0 :    # reversing the empty list requires no more operations
        return res
    res.insert(0, l[0]) # else, insert the first remaining item as the head of the inverse
    return reverse_aux (l[1:], res) # and do the same with the remaining items of the list

# This function initializes the accumulator to the empty list
def reverse_rec2(l):
    return reverse_aux(l,[])

# When this file is imported (using "import td2"), __name__ is the name of the module ("td2" here).
# When this file is run as a python script, __name__ is "__main__".
# Therefore, the following code is executed only when the file is run as a script.
if __name__ == "__main__" :
    # We run the tests that are in the doctrings of this module
    import doctest
    print(doctest.testmod())