Jean-Jacques Lévy   Yves Robert

20 décembre 2000 -- 2h






Avertissement On attachera une grande importance à la clarté, à la précision, à la concision de la rédaction. Les sections A et B sont indépendantes.

A. Décompositions d'entiers

Soit n ³ 0 un entier fixé. Une décomposition de n est un k-uplet d'entiers (a1, a2, ..., ak) tel que ai ³ 1 pour 1 £ i £ k et a1 + a2 + ... + ak = n. On ordonne les décompositions additives de n par l'ordre lexicographique. Par exemple si n = 10,
(2,5,1,1,1) < (2,5,2,1) < (3,7) < (4,1,1,1,1,2).
Formellement, l'ordre lexicographique (l'ordre du dictionnaire) est défini de la manière suivante: (a1, a2, ... ak) < (b1, b2, ... b) ssi ai = bi pour 1 £ i £ m pour un m tel que 0 £ m £ k et soit m = k < , soit am+1 < bm+1. Noter que cet ordre est total.

On représente les décompositions sous forme de listes chaînées contenant successivement les valeurs a1, a2, ..., ak.


Question 1Préciser la structure de donnée sous forme d'une classe ListeDecomp en Java. Ecrire une fonction static boolean estDecomp(ListeDecomp d, int n) qui vérifie si la liste d représente bien une décomposition de n.


Question 2Donner toutes les décompositions du nombre 5 dans l'ordre lexicographique. Combien de chiffres sont modifiés dans une décomposition pour obtenir la suivante?


Question 3Ecrire la fonction static boolean estMax(ListeDecomp d, int n) qui vérifie si une liste d est une décomposition de n sans successeur dans l'ordre lexicographique.


Question 4Etant donnée une décomposition d de n qui n'est pas la plus grande, écrire la fonction static ListeDecomp suivante(ListeDecomp d) qui renvoie la décomposition suivante de d (dans l'ordre lexicographique).

B. Partage équilibré de périmètre

Soit un polygone dont la suite des longueurs des côtés á a0, a1, a2, ..., an-1 ñ est stockée dans un tableau unidimensionnel d'entiers de taille n ³ 2. Soit une paire d'indices (i,j), avec 0 £ i < n et 0 £ j < n; ces indices déterminent deux portions de périmètres, l'une de longueur åk=ij-1 ak et l'autre de longueur åk=ji-1 ak, où tous les indices sont pris modulo n. On cherche la (en fait, une) paire d'indices qui minimise la valeur absolue de la différence des deux portions de périmètre qu'ils déterminent, i.e.
 
min
0 £ i, j < n
D(i,j)  avec  D(i,j) = ½
½
½
½
j-1
å
k=i
ak   -  
i-1
å
k=j
ak ½
½
½
½

Le polygone est représenté par un tableau int[ ] a donnant les longueurs de tous ses cotés.

Nous allons construire des solutions de plus en plus efficaces. Le coût d'une solution est défini comme le nombre d'opérations élémentaires (addition d'entiers, accès à un tableau, etc) qu'elle effectue. (Rappel: en Java, l'expression x modulo n s'écrit x % n.)


Question 5Quel serait l'ordre de grandeur O(nx) du coût de la méthode suivante, trop naïve pour que nous l'écrivions en Java: pour toutes les paires (i,j), calculer la différence D(i,j) et prendre le minimum?


Question 6Ecrire une fonction static int perimetre(int[] a) qui renvoie le périmètre total du polygone décrit par a.


Question 7Pour un indice i donné, soit d(i) le premier indice tel que åk=id(i) ak > p/2, où p est le périmètre (et les indices sont toujours pris modulo n).

a) Montrer que l'indice j tel que D(i, j) = min 0 £ j < n D(i,j) est égal soit à d(i) soit à d(i)+1.

b) Ecrire une fonction static void partage1(int[] a) qui calcule et imprime la solution optimale (i,j,D(i,j)). On veut que le coût de la fonction partage1(a) soit en O(n2).


Question 8On demande maintenant d'écrire une fonction static void partage2(int[] a) similaire à la fonction précédente mais dont le coût est en O(n), i.e. linéaire en n. Il est impératif de justifier le principe de votre algorithme avant d'écrire la fonction.

This document was translated from LATEX by HEVEA.