[Recursif] Recherche sequence

**sorry60** · 29/10/2006, 13h34

Bonjour à tous

Je dois ecrire un algo qui recherche la plus grande sequence de 1 dans un tableau à 1 dimension composé uniquement de 1 et de 0.

Pour cela on nous a donné quelques pistes : choisir un pivot (le milieu du tableau). Utiliser deux fonctions : head(T,i,j) qui retourne le plus long sous tableaux préfixe de T[i...j] uniquement composé de 1, et tail(T,i,j) qui retourne le plus long sous tableaux suffixe de T[i...j] uniquement composé de 1.

En m'aidant de ça et de ce que nous a dit la prof..j'ai concocté ça :

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 rechRec(T,i,j) : (p,n) // (position plus grande sequence,longueur)
  n <- j - i + 1 // taille tableau
  si n = 1 alors
    si T[i] = 0 alors retourner (0,0)
    sinon retourner (i,1)
    finSi
  sinon
    solutiong <- rechRec(T,i,i+(n/2)-1) // (p,n) de la meilleure solution à gauche
    solutiond <- rechRec(T,(n/2)+i,j) // (p,n) de la meilleure solution à droite
    si solutiong.n > solutiondroite.n alors maxsol = solutiong
    sinon maxsol = solutiond
    finSi
    g <- tail(T,i,i+(n/2)-1)
    d <- head(T,i+(n/2),j)
    longueur = g.longueur + d.longueur
    si longueur > maxsol alors
      si g est vide alors retourner(i+(n/2),longueur);
      sinon retourner(i+(n/2) - g.longueur,longueur)
    else
      retourner (maxsol)
    finSi
  finSi
finFonction

Je l'ai rapidement implémenté en C et ça n'a pas l'air de renvoyer le bon resultat

Je pense que ça vient de l'algo.. car j'ai suivit un peu sans comprendre ce que nous a dit la prof..
Car je ne vois pas trop comment il peut fonctionner cet algo

Si vous pouviez m'eclairer un peu car je patauge bien depuis une semaine

Merci pour votre aide

**Captain_JS** · 29/10/2006, 16h22

Mouais personnelement avec un nombre délimitant la position du premier 1, la longueur max des 1 et une fonction > (ou < suivant les choix), l'algo est plus simple et moins tortueux

**borisd** · 30/10/2006, 00h23

Ca n'est pas des plus simples, mais ça a l'air de fonctionner...
As-tu un exemple sur lequel ça ne marche pas ?

[edit]
Pourquoi faire

Code :

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

1
2
3
 
      si g est vide alors retourner(i+(n/2),longueur);
      sinon retourner(i+(n/2) - g.longueur,longueur)

au lieu de

Code :

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

1
2
 
      retourner(i+(n/2) - g.longueur,longueur)

?

**borisd** · 30/10/2006, 00h49

Une autre possibilité, peut-être buggée, c'est juste pour l'idée :

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
 
fonction rechRec(T,i,j) : (p,n) // (position plus grande sequence,longueur)
  n <- j - i + 1 // taille tableau
  si n = 1 alors
    si T[i] = 0 alors retourner (0,0)
    sinon retourner (i,1)
    finSi
  sinon
    milieu_g <- tail(T,i,i+(n/2)-1)
    milieu_d <- head(T,i+(n/2),j)
    longueur_milieu <-milieu_g.longueur + milieu_d.longueur
    pos_milieu <- i+(n/2) - milieu_g.longueur
    solutiond <- rechRec(T,pos_milieu+longueur_milieu,j) // (p,n) de la meilleure solution à droite
    solutiong <- rechRec(T,i,pos_milieu-1) // (p,n) de la meilleure solution à gauche
    Renvoyer la meilleure solution parmi milieu, solutiong et solutiond
  finSi
finFonction

**sorry60** · 31/10/2006, 12h43

Ca je confirme qu'il est pas evident !

Mais je n'ai pas le choix...
Il est censé être en O(log(n)) où n est la taille du tableau.

Merci pour tes infos, je vais y jeter un oeil

Je pense que mes bugs viennent de l'implementation des fonctions head() et tail() que j'ai fait un peu à la va-vite

**borisd** · 31/10/2006, 13h12

L'algorithme que j'ai proposé est en O(N) : dans tous les cas, chaque case du tableau est examinée une et unique fois (par le cas terminal (n=1) ou par une des fonctions head et tail), bien que le nombre d'appels à RechRec soit logarithmique.
Tu peux améliorer la complexité moyenne en stockant la taille maximale de la suite de 1 déjà trouvée, et en n'examinant pas les intervalles de taille inférieure (peut-être le seul intérêt de la méthode ?); aussi en affinant les intervalles gauche et droite (d'une unité à droite pour le gauche et d'une unité à gauche pour le droite, puisque ces cases contiennent forcément un 0).

Attention, le tien, par contre, examine parfois plusieurs fois chaque case du tableau.

Avoir une complexité de log(N) me semble impossible : comment savoir même seulement combien de 1 contient le tableau sans le parcourir au moins une fois ?