Discussion :

[Laurran]

Bonjour!

J'ai un array à deux dimensions nxn. A[i][j]
les éléments de l'array ne peuvent être que des 1 ou des 0.
pour tous les i, c'est à dire les lignes , j'ai un certain nombre de 1, et je complète avec des 0.
Par exemple, 111100000

Donc mon array de départ pourrait être par exemple :
11110000
11000000
10000000
11111000
11111111
11111000
11100000
10000000

(les 1 sont toujours devant, et il ne peut pas y avoir de 0 entre les 1)

Le but du jeu est de trouver un algorithme qui retourne le numero de la ligne, qui a le plus de 1.
Le problème est que l'algorithme doit avoir un temps de travail en O(n) = k*n +a.

J'ai bien trouvé des algorithmes pour cela, mais ils ont tous besoin d'un temps en n².

Merci de m'aider!

Laurran

[2Eurocents]

Il te suffit de raisonner sur les colonnes, et pas sur les lignes ...

[Laurran]

J'ai bien essayé, mais je n'y suis pas arrivée :
au début, j'ai voulu additioner tous les éléments des colonnes, puis trouver à partir de quand je n'ai plus de 0, et donc de chercher quel est la ligne qui correspond.
J'ai aussi essayer d'autres choses, mais à chaque fois, j'ai besoins de n² parce que je le fais pour n colonnes à n éléments.

Est ce que vous pouvez encore un peu m'aider?
Merci merci beaucoup

[Trap D]

Peut-être en partant de la colonne n au lieu de la colonne 0.

[herve91]

J'ai des doutes pour arriver à un algorithme en O(n) = k*n.
Par contre, tu peux avoir plusieurs algorithmes selon la connaissance que tu as a priori du remplissage de la matrice. Si elle est beaucoup remplie de 1, tu peux parcourir les colonnes de la droite vers la gauche, jusqu'à rencontrer une ligne pour laquelle A[ligne][colonne] = 1.
Si tu ne connais pas le taux de remplissage, tu peux procéder par dichotomie. Tu pars de la colonne n / 2, tu parcours les lignes jusqu'à ce que :
au moins un A[ligne][colonne] = 1, dans ce cas tu réitères le processus pour la colonne 3 n / 4
tous les A[ligne][colonne] = 0, dans ce cas tu réitères le processus pour la colonne n / 4
etc.
La complexité est alors O(n) = k*n * log2(n).

[Laurran]

Merci pour vos réponses
Je n'avais pas pensé à la dichotomie. C'est très intéressant!! Merci
Je continue à chercher quand même pour un algorithme en n
Merci beaucoup!

[2Eurocents]

La solution de la dichotomie permet, effectivement, de limiter le nombre de colonnes qui seront consultées, mais aussi de restreindre le nombre de lignes à vérifier si on la combine avec une indirection (une table d'indexation des lignes - LUT ou Look Up Table).

Prenons une table, LUT, que nous remplissons avec tous les numéros de lignes.

Nous avons un intervalle de recherche, sur les n colonnes, qui est, admettons [1,n].

En appliquant la technique de la dichotomie, nous savons que nous allons nous intéresser à la colonne (1+n)/2, au milieu de notre intervalle.

Nous allons donc parcourir tous les éléments de LUT, pour examiner les éléments de A contenus dans la colonne (1+n)/2 et dans la ligne indexée par LUT.

Selon les valeurs de ces éléments de A, nous allons pouvoir constituer une nouvelle table, newLUT. Si l'élément de A contient un 1, son numéro de ligne est ajouté dans newLUT, sinon, il est défaussé.

Si newLUT est vide, après le parcours de LUT, alors c'est que la borne droite de l'intervalle de colonnes est trop loin. On la diminue, par dichotomie, et on refait la recherche en réutilisant LUT.

Si newLUT ne contient qu'une valeur, alors c'est le numéro de la ligne qui contient le plus de 1.

Si newLUT contient plusieurs valeurs, c'est que la borne gauche de l'intervalle de colonnes n'est pas assez loin. Cependant, si la borne gauche et la borne droite sont confondues, alors c'est que plusieurs lignes fournissent la solution et newLUT en est la liste. Si les bornes ne sont pas confondues, on repousse la borne gauche (dichotomie, toujours) et on refait la recherche en utilisant newLUT, donc de moins en moins de lignes à vérifier.

Je vous laisse faire la mise en musique ... mais comme au fur et à mesure qu'on avance, on parcours de moins en moins de lignes, la complexité diminue encore ... Sauf dans le cas le plus défavorable où toutes les lignes contiennent le même nombre de 1

[Matthieu Brucher]

Merci pour vos réponses
Je n'avais pas pensé à la dichotomie. C'est très intéressant!! Merci
Je continue à chercher quand même pour un algorithme en n
Merci beaucoup!

Ca m'étonnerait que ce soit possible. Il te faut de toute manière faire n comparaisons dans une colonne pour savoir s'il y a un 1 dedans, et après il te faudra toujours la dochotomie pour trouver le premier 1, donc n log(n)...

[FrancisSourd]

J'imagine que c'est un exercice... Sinon, je serai intéressé de voir l'application.

Il y a une solution en O(n). Il faut en fait parcourir le carré en diagonale.
On part de i=1 et j=1 et on note m la solution qui est initialisée à 0.
La boucle principale:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
Tant que i < n et j < n
  Si A[i][j] = 1 alors 
    m := j;
    ++j;
  Sinon
    ++i;

La solution est la valeur finale de m.
Pour l'analyse de complexité, on voit que soit i soit j est augmenté de 1 à chaque étape donc i+j est augmenté de 1 comme i+j <= 2n, il y a au plus 2n étapes.

[Matthieu Brucher]

Bien vu

[Laurran]

C'est effectivement un exercice, et il n'y a pas d'application.
Merci beaucoup pour les réponses!
Laurran