Exo Type 10- 2014

Exercice type 10 - 2014

# -*- coding: utf-8 -*-
# Katia Barré  - Lycée Lesage Vannes

import random

#--- question 1 ----------------------------------------------------------------
print
('\n --- Question 1 --- ')

def comptage(L, N):
   
"""

    N : entier > 10
    L : liste d'entiers de [0, N - 1]
    Renvoie une liste P telle que P[k] est le nombre d'occurence de k dans L

   
"""
    P = [0] * N
   
for x in L:
        P
[x] += 1
   
return P

N = 5
mL
= [random.randint(0, N - 1) for i in range(20)]
print
('Liste L = ', mL)
print
('Comptage(L, 5) = ', comptage(mL, N))

#--- question 2 ----------------------------------------------------------------
print
('\n --- Question 2 --- ')

def tri(L, N):
   
"""

    N : entier
    L : liste d'entiers de [0, N - 1]
    Renvoie la liste L triée par ordre croissant

    """

    P
= comptage(L, N)
    Q
= []
   
for i in range(N):
       
for k in range(P[i]):
            Q
.append(i)
   
return Q

#--- question 3 ----------------------------------------------------------------
print
('\n --- Question 3 --- ')

print
('        L = ', mL)
print
('tri(L, 5) = ', tri(mL, N))

#--- question 4 ----------------------------------------------------------------
print
('\n --- Question 4 --- ')
print
('En notant M = len(L),')
print
('La fonction comptage est de complexité O(M + N), de même que la fonction tri.')
print
('Le tri par insertion est de complexité O(N^2).')

print('Le tri par fusion est de complexité O(N ln(N)).')

 

--- Question 1 ---

Liste L =  [0, 0, 4, 0, 4, 0, 3, 3, 1, 1, 2, 4, 3, 1, 3, 4, 0, 1, 3, 3]
Comptage(L, 5) =  [5, 4, 1, 6, 4]

 --- Question 2 ---

 --- Question 3 ---

        L =  [0, 0, 4, 0, 4, 0, 3, 3, 1, 1, 2, 4, 3, 1, 3, 4, 0, 1, 3, 3]
tri(L, 5) =  [0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4]

 --- Question 4 ---

En notant M = len(L),
La fonction comptage est de complexité O(M + N), de même que la fonction tri.
Le tri par insertion est de complexité O(N^2).
Le tri par fusion est de complexité O(N ln(N)).

Search