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())