[recursif] Plus longue sequence de 1 avec pivot 0

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 :mouarf: ), j'ai ecrit ce pseudo-algo :

Code:

---

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 :roll:
Merci à vous
Sorry

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:

---

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 ;)

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) ?

Citation:

---

Envoyé par 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) ?

---

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.

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é :)

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

Code:

---

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:

---

k <- 0

---

Ca ne serait pas plutôt

Code:

---

k <- i

---

?

Code:

---

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:

---

1 2 3

sinon solutiong = (i,head(T,i,k))

---

par

Code:

---

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 :aie:

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

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. ;)