Version interactive avec LaTeX compilé
CONCOURS ENSAM - ESTP - ECRIN - ARCHIMEDE
Epreuve d'Informatique MP durée 3 heures
L'usage de la calculatrice est interdit
Indiquez en tête de copie ou de chaque exercice le langage utilisé.
1. Calendrier
Écrire la fonction
dateValide données j, m, a : entiers résultat : booléen
qui retourne Vrai si la date représentée par le triplet
dateValide données j, m, a : entiers résultat : booléen
qui retourne Vrai si la date représentée par le triplet
Règles de validité d'une date :
- janvier, mars, mai, juillet, août, octobre, décembre ont 31 jours ;
- avril, juin, septembre, novembre ont 30 jours ;
- février a 29 jours si l'année est bissextile, 28 sinon;
- une année est bissextile si :
- pour les années séculaires (1900,2000, etc.), elle est divisible par 400,
- pour les autres années, si elle est divisible par 4 ;
- on se limitera aux dates postérieures au 15 octobre 1582, date de mise en application en France de ces règles (calendrier Grégorien).
2. Résistance équivalente
Écrire la fonction
resistanceEquivalente données r: liste de réels
résultat : réel
qui retourne la valeur de la résistance équivalente aux résistances en parallèle dont les valeurs sont contenues dans la liste
3. Sous-suite de trois nombres de somme maximale.
Écrire la fonction
indiceTripletMaximal données lst : liste d'entiers
résultat : entier
qui retourne l'indice du premier élément du triplet de somme maximale dans la liste de nombres 1 st, supposée de cardinal au moins égal à 3 .
Par exemple, pour la liste suivante
| liste |
|
|
|
|
|
|
|
|
|
| indice | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
la fonction retournerait 3 , indice du premier élément du triplet
4. Suite ordonnée des multiples de 2,3 et 5 .
Le but de ce problème est de construire la suite ordonnée des entiers de la forme
Cette suite commence par
| liste |
|
|
|
|
|
|
|
|
|
|
|
|
||||
| indice | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
Principe :
La liste étant en cours de construction, l'élément suivant de la liste sera à choisir parmi les nombres suivants :
Dans l'exemple,
Le plus petit étant 18, c'est l'élément à ajouter à la liste. Les indices concernés par le choix (ici
| liste |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
| indice | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|
|
||||||||||||||||
|
|
|
|||||||||||||||
|
|
||||||||||||||||
Écrire, selon ce principe, le programme qui construit la liste triée des
5. Suites de Fibonacci
Une suite de Fibonacci généralisée est définie par
Plusieurs méthodes peuvent être envisagées pour calculer le
1. Méthode récursive simple
On n'utilise pas de variable locale, on se contente de réécrire dans le langage utilisé la définition mathématique.
Écrire la fonction :
qui retourne le
2. Méthode itérative
On utilise une boucle avec trois variables locales :
- une variable contient l'avant dernier élément de la suite;
- une variable contient le dernier élément;
- une variable contient le nouvel élément.
Écrire la fonction :
qui retourne le
3. La méthode la plus efficace : récursive par matrices
- Montrer (mathématiquement) que
- Écrire une fonction de multiplication de deux matrices carrées
. - Écrire une fonction d'élévation à la puissance
d'une matrice carrée de en utilisant le principe d'exponentiation rapide :
- Ecrire la fonction :
qui retourne le
- On estime que si une addition prend une unité de temps, une multiplication en coûte 4 et une division 7. Au niveau du coût arithmétique, comparer les méthodes fibo2 et fibo3 pour calculer
.
Tournez la page S.V.P.
Exercices de recherche
Pour ces deux problèmes, vous n'êtes pas guidés. Essayez de proposer un algorithme permettant de répondre aux questions posées.
6. Suites oscillantes
Soit
- Montrer (mathématiquement) que la suite
est périodique à partir d'un certain rang - Écrire la fonction
periode données f: fonction; a : entier
résultat p : entier; e : entier
qui étant donné une fonction
7. Plateau maximal
Écrire la fonction
indicePlateauMaximal données lst : liste d'entiers
résultat : entier
qui retourne l'indice du premier élément de la plus grande sous-liste constante de lst, liste croissante au sens large de nombres entiers.
Dans l'exemple suivant,
| liste |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| indice | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
la fonction retournerait 8 (indice de début de la plus longue sous-liste constante)