ca reste de l'economie de bout chandelle. L'algo ets et reste un truc lineaire et memory bound.
ca reste de l'economie de bout chandelle. L'algo ets et reste un truc lineaire et memory bound.
@Arzar: as-tu testé avec les tests U que j'ai mis? Chez moi, l'algo de iradrille et le tiens modifié me renvoient 3 dans le cas de deux séquences identiques.
Aurais tu un exemple pour lequel le code que j'ai mis (qui est la traduction de l'algo d'Astraya ) ne fonctionne pas? (j'ai beau chercher, je vois pas ce qui pourrait clocher)
[Edit] je viens de voir que c'est voulu par Iradrille, sachant que l'OP sur ce point n'a pas répondu sur le comportement souhaité
Si j'ai bien compris la définition de "dominer": une liste L domine une liste R si pour tout i L[i] <= R[i].
Je pense que l'astuce n'est pas de parcourir toute la liste.
Si on a L[0]<R[0] alors on pose comme hypothèse que c'est vrai pour tout i et on s'arète dès que notre hypothèse est invalidée.
Comme on travail sur des listes l'utilisation des index n'est peut être pas le plus judicieux...
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
25
26
27
28
29
30
31
32
33
34
35
36 enum Dominant { L2Dominant, L1Dominant, SaisPas }; int compareListe(QList<int> & L1, QList<int> & L2) { if(L1.size()>0 && L1.size() == L2.size()) { QList<int>::const_iterator it1 = L1.begin(); QList<int>::const_iterator it2 = L2.begin(); Dominant d = SaisPas; while(it1!=L1.end()) { if(*it1!=*it2) { if(SaisPas==d) d = (*it1<*it2)?L1Dominant:L2Dominant; else if( (*it1<*it2)?L1Dominant:L2Dominant != d) return 0; } ++it1; ++it2; } if(d==L1Dominant) return 1; if(d==L2Dominant) return 2; } return 0; }
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager