Discussion :

[sorry60]

Salut

Je suis encore dans mes exos d'algo de recherche de la plus longue sequence de 1 dans un tableau binaire...
Ce coup ci l'algo doit etre recursif, et le pivot choisit n'est plus le milieu du tableau, mais un element de celui ci dont la valeur est 0.
Le but etant d'ameliorer la complexité du precedent.

En y reflechissant vaguement (c'est le matin, je suis pas encore assez reveillé pour faire de bons algos ), j'ai ecrit ce pseudo-algo :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
fonction rechSeq(T,i,j) : (p,n) // p : pos, n : longueur
   rechercher le 1er 0 en partant de la gauche
   si il n'y en a pas alors retourner (i, j-i+1)
   sinon
      solutiong = (i,position_actuelle - i + 1)
      solutiond = rechSeq(T,position_actuelle,j)
      retourner le max entre solutiong et solutiond
   fonSi
finFonction

Voilà, j'attends vos avis et commentaires, qu'on puisse echanger nos idées
Merci à vous
Sorry

[sorry60]

Voilà j'ai transformé mon pseudo-algo en algo, je l'ai posé sur papier, fais les tests sur quelques tableaux. Il a l'air de fonctionner.

Le voici :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
fonction rechSeq(T,i,i) : (p,n) // p : pos, n : long
   n <- j - i + 1
   k <- 0
   sorti <- faux
   si ( n <= 1 ) alors
      retourner(j,T[j])
   sinon
      tantque ( k < j ET sorti=faux ) faire
         si ( T[k] = 0 ) alors
            sorti <- vrai
         sinon
            k <- k + 1
         finSi
      finTantque
      si ( k=j ET T[j] = 1) alors
         retourner(i, head(T,i,j))
      sinon
         solutiong = (i,head(T,i,k))
         solutiond = rechSeq(T,k+1,j)
         retourner max(solutiong,solutiond)
      finSi
   finSi
finFonction

head(T,i,j) renvoie la taille du sous tableau de T ne contenant que des 1 entre les indices i et j, ex : T : [1,1,0,1,1], head(T,0,2) renvoie 2.

J'attends vos commentaires

[borisd]

Bonjour,
le bout de code que tu as rajouté dans rechSeq doit pas mal ressembler à tail(). Pourquoi ne pas plutôt utiliser cette fonction, qui doit te donner le même résultat (code plus lisible) ?

[sorry60]

Bonjour,
le bout de code que tu as rajouté dans rechSeq doit pas mal ressembler à tail(). Pourquoi ne pas plutôt utiliser cette fonction, qui doit te donner le même résultat (code plus lisible) ?

Quel bout de code ? car à part le detail pour la recherche du 1er 0, et les cas d'arret, je n'ai pas trop touché au pseudo-algo de mon 1er post.

[sorry60]

En tout cas, je l'ai implémenté (en C) et j'ai fait des mesures de temps, il est exactement comme il faut : moins bien que l'algo1 ( qui est en O(n) ), mieux que l'algo2 ( qui lui est en O(nlog(n)) ).

Voyons par le calcul !

Meilleur-cas : que des 1
complexité de l'ago sans la recursivité : O(n)
nombre d'appel : 1

Pire-cas : que des 0
complexité de l'ago sans la recursivité : O(2)
nombre d'appel : n

conclusion :
meilleur-cas : teta(n)
pire-cas : O(2n)


Edit : j'edite car je me suis trompé

[borisd]

En fait je ne suis pas sûr d'avoir tout bien compris

Code :

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

1
2
3
4
5
6
7
8
 
       tantque ( k < j ET sorti=faux ) faire
         si ( T[k] = 0 ) alors
            sorti <- vrai
         sinon
            k <- k + 1
         finSi
      finTantque

Cette boucle peut être simplifiée.

Code :

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

 k <- 0

Ca ne serait pas plutôt

Code :

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

k <- i

?

Code :

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

1
2
3
 
si ( k=j ET T[j] = 1) alors
         retourner(i, head(T,i,j))

Si on se trouve dans ce cas là, c'est qu'il n'y a que des 1 entre i et j, non ? Pourquoi appeler head() dans ce cas ?

Est-ce qu'on ne pourrait pas remplacer

Code :

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

1
2
3
 
      sinon
         solutiong = (i,head(T,i,k))

par

Code :

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

1
2
3
 
      sinon
         solutiong = (i,k-i)

Comme je l'ai dit, je ne suis pas sûr d'avoir tout bien saisi, donc ne t'en fais pas si tu vois pas ce que je veux dire, je n'ai pas trop eu le temps de réfléchir

[sorry60]

Oui en effet j'ai un peu trop compliqué la chose

[nletteron]

Comme quoi le pivot 0 n'est pas une si mauvaise méthode. Je n'ai pas trop eu le temps de méditer pour te répondre concrètement en privé, mais on pourrait peut être (je ne sais pas) imaginer un mélange de dichotomie et de pivot 0 pour voir ce que ça donne. J'émet un doute à cause du coup de la recherche d'un 0 dans le cas où malheureusement pas mal de 1 se trouve au centre.

J'y réfléchirais plus amplement dans la semaine.