Vous pouvez poser ici vos questions relatives au devoir maison 2 d'informatique.
Question subsidiaire : quelle est la mesure d'équilibre du tableau ci-contre ?
Devoir maison d'informatique
vendredi, décembre 26 2014. Lien permanent La classe de PC › Devoirs
4 réactions
1 De Romain Validire - 26/12/2014, 12:12
Message transféré de Guillaume
Donc, pour la fonction mes(T), on a mes(Te) = 2, mes(Td) = 0 et mes(Tr) = 1.
Mon problème se construit à partir du tableau suivant :
T? = [[1,0,1,0] , [1,1,0,1] , [0,1,0,0] , [1,0,1,1] ]
T? ressemble beaucoup à Td ... et du coup mes(T?) = ???
J'hésite entre dire 0 ou 2, car le sous-tableau 2x2 n'est pas équilibré, MAIS en regardant bien, le sous-tableau 4x4 l'est.
Résumé ainsi, pour un tableau de taille NxN, la mesure d'équilibre est le plus grand entier k, s'il existe, tel que le sous-tableau extrait en partant du coin supérieur gauche de taille 2k x 2k est équilibré.
Si k n'existe pas, on pose mes(T) = 0.
Pour comprendre la fonction, faut-il que tous les tableaux extraits à partir de k = 1 soit équilibré pour que mes(T) renvoie la plus grande valeur de k tel que le sous-tableaux de taille 2(k+1)x2(k+1) ne le soit plus ... ou suffit-il d'avoir ne serait-ce qu'un sous-tableau équilibré ?
Par exemple car c'est compliqué à expliquer mais plus simple à comprendre en pratique, prenons les tableaux Te, Tr et T? défini plus haut.
- pour Te, les sous-tableaux 2x2 et 4x4 sont tous deux équilibrés. En revenant à la définition, mes(Te) = 2
- pour Tr, le sous-tableau 2x2 est équilibré mais pas celui de taille 4x4. De même mes(Tr) = 1
- pour T?, le sous-tableau 2x2 n'est pas équilibré alors que celui 4x4 l'est. Donc, mes(T?) = 0 ou 2 ?
Merci de me diriger dans la bonne direction.
2 De Romain Validire - 26/12/2014, 12:22
Pour reprendre vos mots : il suffit "d'avoir ne serait-ce qu'un sous-tableau équilibré". On retient alors la taille la plus grande.
Dans votre exemple : le sous-tableau 4*4 de T? n'est pas équilibré (il y a 9 fois 1).
Mais par exemple pour : Tmodif= [[1,0,1,0] , [1,1,0,1] , [0,1,0,0] , [1,0,1,0] ] on a une mesure égale à 2.
J'espère avoir répondu à la question.
3 De Rouquier Guillaume - 26/12/2014, 15:47
Excusez moi, je me suis trompé pour mon tableau, j'ai mis effectivement un 1 en trop.
Comme j'ai compris, je vais résumer ainsi :
- si dans un tableau T de taille NxN, il y a plusieurs sous-tableaux équilibrés, la fonction mes(T) retourne la valeur de k tel que le plus grand tableau de taille 2k x 2k soit équilibré
- mais, s'il n'y en a qu'un (de taille quelconque), la fonction renvoie la valeur de k associé à la taille de ce sous-tableau
- s'il n'y en a aucun, mes(T) retourne 0
Merci beaucoup, il ne reste plus qu'à écrire la fonction maintenant.
4 De Romain Validire - 26/12/2014, 18:36
Vous avez tout à fait raison.
Formellement on pourrait dire : étant donné un tableau binaire T de taille 2n, l'ensemble des entiers k tels que le sous-tableau T[0:2k,0:2k] est équilibré est un sous-ensemble majoré de IN. S'il est vide on pose mes(T)=0 ; s'il est non vide alors il est majoré : on note mes(T) son plus grand élément.