1. #1
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 7
    Points : 3
    Points
    3

    Par défaut Recherche de milieux dans un tableau

    Bonjour,
    Mon but est d'améliorer la complexité de ma solution au problème suivant :
    On a un tableau d'entiers t = [t1 < t2 ... < tn]. Le but est de compter le nombre de triplets ti , tk , tj tels que tk - ti = tj - tk.
    Ma solution s'exécute en O(n²) (en Python):

    s = 0
    for k in range(1, n-2):
    i,j = k-1, k+1
    temp = 2 * t[k]
    while i >= 0 and j < n:
    if t[i] + t[j] == temp:
    s+=1
    i-=1
    j+=1
    elif t[i] + t[j] < temp:
    j+=1
    else:
    i-=1

    Par exemple, [1,3,4,5] va donner s = 2.

    Y a-t-il une solution plus efficace ?
    Merci

  2. #2
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Recherche de milieux dans un tableau

    Bonjour,

    L'idée de partir de (k), puis d'élargir les bornes (i, j) est inattendue.
    J'ai pratiqué un peu le Python, et la lecture de ton programme - pour autant que je l'ai bien compris - appelle deux remarques:
    a) (k) ne varie-t-il pas entre (2) et (n - 1), puisqu'il est strictement compris entre (i) et (j), donc entre (1) et (n) ?
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     ... On a un tableau d'entiers t = [t1 < t2 ... < tn] ... 
    for k in range(1, n-2):
    b) Le programme fonctionne-t-il correctement sur des listes très dissymétriques, par exemple:
    t = (1, 4, 9, 16, 25, 36, 41, 49, 64, 81, 100) ?

    La suite étant ordonnée, je serais spontanément parti des indices extrêmes; tu traduiras facilement ce qui suit:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    FOR k:= 1 TO n DO u[k]:= 2 * t (k );
    s:= 0;
    FOR i:= 1 TO (n - 2) DO
      FOR j:= (i + 2) TO n DO
        BEGIN
          a:= t[i] + t[j]; 
          FOR k:= (i + 1) TO (j -1) DO
            IF (u[k]=a) THEN Inc(s)
     ...
    Le calcul des valeurs doubles est consigné une fois pour toutes dans un second tableau (u) isotype de (t).
    La complexité n'est sans doute pas diminuée, mais les calculs un peu plus rapides sur une plus longue liste.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  3. #3
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    Merci de ta réponse
    Effectivement, en fait t = [t0 < t1 ... < t(n-1)]
    Donc le n-2 devient n-1 (le range va aller de 1 à n-2)

    Ensuite, je pense qu'il fonctionne : pour le prouver, on peut d'abord dire que un élément "milieu" est forcément entre 1 et n-2:
    -si tk-1 et tk+1 marchent, alors on incrémente s (premier cas) et on sais que tk-1 ne marchera avec rien d'autre (puisque les éléments sont distincts et triés) et c'est la même chose pour tk+1 -si tk-1 + tk+1 < 2*tk, alors on sais que tk+1 ne marchera avec rien à gauche de tk (puisque tout les ti avec i<k-1 sont plus petits que tk-1)
    -on a la même chose pour le cas >

    Merci pour ta proposition : à première vue elle est en n^3, mais je vois comment la passer en n².

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 510
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 510
    Points : 3 152
    Points
    3 152

    Par défaut

    J'ai l'impression que la solution de Wiwaxia est beaucoup plus lente que la solution proposée par GreenHor.

    La solution de GreenHor me paraît quasiment optimisée. On doit quand même pouvoir faire mieux en passant par des dictionnaires. Si on reprend les données de Wiwaxia, on va inverser le stockage, en disant Dico[1] = 1,Dico[4] = 2,Dico[9]=3 etc ...
    Ainsi quand on a calculé 2*t[k] - t[i], on peut déterminer immédiatement si il existe un j tel que t[j] = 2*t[k]-t[i], plutôt que passer par une boucle. Mais par rapport à la solution de GreenHor, le bénéfice me paraît minime.

    Si on veut,on doit aussi pouvoir stocker d'une part les t[i] impairs, et d'autre part les t[i] pairs... et ainsi, pouvoir aller plus vite. Si t[i] + t[j] = 2*t[k], forcément t[i] et t[k] sont de même parité. Mais le bénéfice paraît minime.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    Merci !
    n² est vraiment trop pour moi, alors je pense que mon vrai problème (duquel découle celui-ci) a une solution plus rapide qui n'utilise pas cette simplification.

  6. #6
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 510
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 510
    Points : 3 152
    Points
    3 152

    Par défaut

    Et par curiosité, n est de quel ordre de grandeur, et aussi, les t[k] sont de quel ordre de grandeur ?
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  7. #7
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    Les deux sont de l'ordre du million, et j'ai une seconde pour tout faire

  8. #8
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Recherche de milieux dans un tableau

    J'ai oublié de tenir compte de la nécessaire parité de la somme (ce qui automatiquement réalisé dans le cas de ton programme), et cela dispense d'effectuer la moitié (en gros) des vérifications:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    FOR k:= 1 TO n DO u[k]:= 2 * t (k );
    s:= 0;
    FOR i:= 1 TO (n - 2) DO
      FOR j:= (i + 2) TO n DO
        BEGIN
          a:= T[i] + t[j];
          IF (a MOD 2 =0) THEN 
            FOR k:= (i + 1) TO (j -1) DO
              IF (u[k]=a) THEN Inc(s)
     ... 
        END;


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  9. #9
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    Merci ! Je vois, mais avec un million, mon programme tourne en quelques minutes, alors qu'il faut que je passe à moins d'une seconde, alors il y a forcément une simplification avec le problème initial.

  10. #10
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 510
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 510
    Points : 3 152
    Points
    3 152

    Par défaut

    Il faut que tu passes à moins d'une seconde .. parfois, mon patron me demande un outil pour aller de Paris à Marseille en 3 minutes, et je lui réponds : je n'ai pas de solution, désolé.
    En terme d'algorithme, tu peux envisager un pré-traitement pour séparer les t[i] pairs des impairs, ça va diviser par quasiment 2 le temps de traitement, mais il faudra en plus ce pré-traitement, et ça va compliquer un peu le traitement. Personnellement, je ne vois vraiment pas d'autre amélioration.

    Ensuite, il y a d'autres aspects. On ne met plus en cause l'algorithme, mais l'aspect purement I.T. Pour ces questions, il y a probablement des sous-forimes plus adaptés que le forum algorithme.

    Ici, tu utilises du Python. Pour les boucles, Python est très lent comparé à du C par exemple. Je ne connais pas le ratio, mais à algorithme égal, en utilisant du C, tu vas nettement améliorer la performance. Est-ce que ça va suffire, je ne sais pas, mais je n'exclue pas.

    Tu peux aussi passer par de la parallélisation. Par défaut, avec une boucle comme celle que tu proposes, tu as un seul processeur qui bosse. Si d'une façon ou un autre, tu confies un quart du boulot à chacun de tes 4 processeurs, tu divises le temps par 4. A vérifier, en regardant la charge des processeurs dans le gestionnaire de taches quand tu fais tourner ton programme actuel.


    Dernier point, tu dis que tu as n = 1 Million de valeurs, comprises en gros entre 0 et 1 ou 2 millions... Et donc, tu as probablement des valeurs en doubles ou en triples ... Si tu as T[i]=T[i+1]=T[i+2] , tu vas recenser le triplet
    (i,i+1,i+2) comme solution au problème, est-ce voulu ?
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  11. #11
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    Ahaha non non, je suis étudiant en maths et j'ai simplifié l'exo 5 de Prologin en ça, ce qui apparemment risque d'être insuffisant.
    Je vais continuer à chercher, mais merci pour votre aide !

  12. #12
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Recherche de milieux dans un tableau

    Une variante de l'algorithme précédent, qui consiste à arrêter l'énumération de (k) dès que l'on a atteint ou dépassé la limite cherchée permet de réduire le temps de calcul d'un facteur ~ 2.4
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
         Nr:= 0; 
         FOR i:= 1 TO (Nval - 2) DO
           FOR j:= (i + 2) TO Nval DO
             BEGIN
               s:= L_1[i] + L_1[j];
               IF (s MOD 2 =0) THEN
                 BEGIN
                   k:= i+1;
                   WHILE (L_2[k]<s) DO Inc(k);
                   IF (L_2[k]=s) THEN Inc(Nr)
                 END
             END;
    Mais cela reste effectivement très lourd, le temps de calcul étant proportionnel à (Nval)3.

    Par contre une 3me version, dans laquelle on impose au 3me paramètre (k) la valeur initiale médiane (i + j) DIV 2 réduit le temps d'un facteur ~ 30 à 64 (pour Nval = 4000 à 8000).

    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
         Nr:= 0; 
         FOR i:= 1 TO (Nval - 2) DO
           FOR j:= (i + 2) TO Nval DO
             BEGIN
               s:= L_1[i] + L_1[j];
               IF (s MOD 2 =0) THEN
                 BEGIN
                   k:= (i + j) DIV 2;
                   IF (L_2[k]>s) THEN REPEAT
                                        Dec(k)
                                      UNTIL (L_2[k]<=s)
                                 ELSE WHILE (L_2[k]<s) DO Inc(k);
                   IF (L_2[k]=s) THEN Inc(Nr)
                 END
             END;
    Mieux encore, l'augmentation du temps de calcul deviens moins rapide, celui-ci apparaissant désormais proportionnel à (Nval)2.
    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
    Nval	     Ntrip  Version 1  Version 2  Version 3  Ntrip/Nval2
    
     1000	     45716     0.28 s     0.16 s     0.03 s     0.045716
     
     2000	    178846     2.30 s     1.03 s     0.05 s     0.044712
    
     4000	    719519    17.98 s     7.66 s     0.25 s     0.044970
    
     8000	   2856693   143.12 s    58.95 s     0.92 s     0.044636
    
    10000      4466663                           1.48 s     0.044667
    
    30000     40785915	                    17.43 s     0.045329
    
    100000   454508146                         200.20 s     0.045451
    Le nombre de triplets trouvés (i, k, j) apparaît lui aussi proportionnel à (Nval)2; il paraît donc difficile d'espérer un algorithme moins lourd, puisque le dénombrement des solutions implique de les énoncer une par une (à moins qu'une astuce de programmation ne permette leur regroupement).
    Les résultats ont été obtenus à partie de séquences aléatoires strictement croissantes, définies par la relation de récurrence:
    t[k + 1] = t[k] + 1 + Random(10) .

    Le code initialement proposé par greenHor semble pour l'instant le meilleur.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  13. #13
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 510
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 510
    Points : 3 152
    Points
    3 152

    Par défaut

    Peux-tu donner un lien vers l'énoncé original de l'exercice ?
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  14. #14
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 474
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 474
    Points : 3 905
    Points
    3 905

    Par défaut

    salut

    si c'est des triplet un simple boucle avec un pas de 2 devrais suffir

    K := 1;
    While K <= N-1 do
    Begin
    if Tab[K-1] - Tab[K] = Tab[K] - Tab[K+1] Then
    Selection(Tab,K)
    Inc(K,2)
    End;
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  15. #15
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 510
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 510
    Points : 3 152
    Points
    3 152

    Par défaut

    @Anapurna
    Non, si on prend l'exemple donné au début, avec le jeu de données [1,3,4,5], il y a 2 solutions ... et ce sont les triplets (1,3,5) et (3,4,5).
    Les 3 valeurs i,j,k ne sont donc pas forcément consécutives.
    Pour un exercice de programmation, ça aurait été un peu trop simple.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  16. #16
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 474
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 474
    Points : 3 905
    Points
    3 905

    Par défaut

    Salut

    ok ... après je connais pas le niveau de développement demandé ^^
    effectivement cela complexifie un peu le truc
    je suppose qu'il ne cherche pas des valeur symétrique par rapport au pivot non plus ?

    bon on sais que k et la valeur pivot
    donc la recherche d'un cote et de l'autre seras limite par cette valeur pivot

    IMin => K-1..0 (GAUCHE)
    IMax =< K+1..N (DROITE)
    On sais que la liste est trié par ordre croissant

    EcartMin := Tab[K] - Tab[K-IMin]
    EcartMax := Tab[K+IMax] - Tab[K]
    la recherche est valide que si (EcartMin <= EcartMax) et que Imax est entre K+1..N
    tes boucle de recherche peuvent etre inverse des que tu depasse la moitie du tableau
    il est préférable de faire tes recherche sur la parti la plus petite

    je verrais bien un truc dans ce genre la
    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
    37
    38
    39
    40
    S :=0
    While K < N-1 do 
    begin
       if  K < (N DIV 2) Then 
       BEGIN
           I := K-1
           While  I > 0 do 
           BEGIN 
             IMIN :=  TAB[K]-TAB[I]
             IMAX :=  TAB[K+1]-TAB[K]
             J:= K+1 
             While IMAX <=  IMIN Do 
             BEGIN
                IMAX :=  TAB[J]-TAB[K]
                IF IMAX =  IMIN Then 
                   S := S+1;
                INC(J)
             END
              DEC(I)
           END
       END
       ELSE
       BEGIN
           J := K+1
           While  J < N do 
           BEGIN 
             I:= K-1 
             IMIN :=  TAB[K]-TAB[I]
             IMAX :=  TAB[J]-TAB[K]
             While IMAX >=  IMIN Do 
             BEGIN
                IMIN :=  TAB[K]-TAB[I]
                IF IMAX =  IMIN Then 
                   S := S+1;
                DEC(I)
             END
              INC(J)
           END
       END; 
    END;
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  17. #17
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    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
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    Crêpes parfaites – Qualification 2018
    
    Niveau 5
    Énoncé
    
    Joseph Marchand se lance un défi, il doit produire une crêpe tout en se promenant sur la plage, promenade qui doit satisfaire certaines contraintes qu'il a définies à l'avance.
    
    Il a commencé par dessiner des disques à certains endroits sur le sol qu'il numérote de 0 à N - 1, le disque 0 correspondant à l'emplacement de son stand à crêpes. Sur chacun d'entre eux, il plante une pancarte indiquant 2 directions pointant chacune vers respectivement 2 autres emplacements.
    
    Sa promenade doit commencer à l'instant 0 au niveau de son stand et à chaque disque rencontré il doit prendre une des deux directions indiquées selon le critère suivant :
    
        la première si le nombre de 1 dans l'écriture binaire du nombre de disques déjà rencontrés est pair
    
        la seconde sinon
    
    Joseph tient à ce que sa crêpe soit parfaite, pour cela il faut impérativement qu'elle soit retournée pile au milieu du temps de cuisson. Pour pouvoir réaliser une telle crêpe il faut donc qu'il se trouve au niveau de son stand aux instants T, T+t puis T+2t où T est l'instant de début de cuisson, et t la durée de mi-cuisson, cela sachant qu'il met exactement une seconde (il est très rapide) pour se déplacer d'un disque à l'autre.
    
    À l'instant 0 il met en marche sa poêle, et il ne peut pas lancer directement la cuisson d'une crêpe, il lui faudra attendre au moins son prochain retour sur son stand. Par ailleurs, comme il n'est pas infatigable, Joseph arrêtera sa promenade après la seconde L (il peut encore arrêter la cuisson d'une crêpe à cet instant).
    
    Combien Joseph a-t-il de manières différentes de réaliser une crêpe parfaite ?
    Entrée
    
    La première ligne contiendra 2 entiers L et N, la durée de sa promenade et le nombre de disques qu'il a tracés sur le sol. N lignes suivront, la i-ème d'entre elles contiendra 2 entiers qui correspondront dans l'ordre aux 2 directions sur le i-ème disque.
    Sortie
    
    Vous afficherez un seul entier : le nombre de manières différentes pour Joseph de réaliser une crêpe parfaite pendant sa promenade.
    Contraintes
    
        1≤N≤2 500
        1≤L≤2 000 000
    
    Attention ! Il n'y a pas de tests de performance pour ce problème, c'est à dire que pour valider les tests de correction il faut déjà avoir la bonne complexité (ie une solution correcte mais trop lente sera jugée non valide).
    Contraintes d'exécution
    
    Utilisation mémoire maximum
        64000 kilo-octets
    Temps d'exécution maximum
        1000 millisecondes
    
    Exemples d'entrée/sortie
    
    Exemple d'entrée
    
        9 3
        1 2
        1 2
        0 0
    
    Exemple de sortie
    
        1
    
    Commentaire
    
        Joseph commence à compter :
    
            0 a un nombre pair (0) de bits à 1, il va donc au disque 1
            1 a un nombre impair (1) de bits à 1, il va donc au disque 2
            2 a un nombre impair (1) de bits à 1, il va donc au disque 0 (son stand à crêpe)
            3 a un nombre pair (2) de bits à 1, il va donc au disque 1
            4 a un nombre impair (1) de bits à 1, il va donc au disque 2
            5 a un nombre pair (2) de bits à 1, il va donc au disque 0 (son stand à crêpe)
            6 a un nombre pair (2) de bits à 1, il va donc au disque 1
            7 a un nombre impair (3) de bits à 1, il va donc au disque 2
            8 a un nombre impair (1) de bits à 1, il va donc au disque 0 (son stand à crêpe)
    
        Joseph peut donc commencer à faire cuire une crêpe après 3 secondes, il retombera sur son stand à crêpe 3 secondes plus tard pour la retourner et enfin, 3 secondes après pour la manger.
    
    Exemple d'entrée
    
        11 3
        0 1
        2 0
        0 1
    
    Exemple de sortie
    
        5
    
    Commentaire
    
        Les 5 manières de cuire une crêpe parfaite sont :
    
            3s par côté en commençant à T=1
            1s par côté en commençant à T=9
            3s par côté en commençant à T=4
            4s par côté en commençant à T=3
            2s par côté en commençant à T=7
    Voilà voilà, le problème est beaucoup plus compliqué et je vais devoir faire ça autrement qu'en listant les retours à 0 bêtement.
    Merci pour vos aides !

  18. #18
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 510
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 510
    Points : 3 152
    Points
    3 152

    Par défaut

    L'énoncé du problème est compliqué. Mais le volume de données est a priori moindre que ce que tu disais.
    Si tu as 1000 disques, et 2000000 secondes, Joseph va passer 'statistiquement' 2000 fois par le disque n°0. Tu as donc 2000 nombres compris entre 0 et 2000000.

    Ce que je ferais :

    Tb est un tableau de L booléens ( L = 2000000 au max
    TB2 est un tableau de 0 entiers. // On va allouer des enregistrementq dans ce tableau autant que nécessaire (à chaque passage par le disque n°0).

    On parcours le circuit du marchand de crèpes.
    A chaque fois qu'il passe par le disque n°0, on fait :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    tb[i]= 1  // i = le chronomètre.
    nb_passages_par_0 ++
    tb2[nb_passages_par_0] = i
    Et immédiatement, on essaie de voir si on peut 'finir la cuisson d'une crèpe' :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    j = nb_passages_par_0 -1 ; ok = vrai
    tantque ok = vrai
      instant_j = tb2[j]
      k = 2*instant_j - i 
      si k <= 0 alors 
          ok = faux
      sinon
          si tb[k] = 1 alors compteur ++
      fin
      j--
    fin
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  19. #19
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Ils ont des chapeaux ronds, vive la Bretagne

    Si l'on avait été immédiatement informés de la dégustation de crêpes, on aurait pu s'attaquer sainement au problème après quelques bolées de cidre.

    La suite (s[t]) des (L + 1) positions successives de la randonnée sur les (N) disques vérifie une relation de récurrence utilisant
    a) la position actuelle (s[k]), ainsi que les correspondances figurant dans le tableau initial,
    b) la suite booléenne de Prouhet-Thue-Morse,
    et l'on cherche les retours au stand de crêperie (s = 0) à des instants également espacés, donc des triplets d'entiers (i, j, k) vérifiant:
    s[i] = s[j] = s[k] = 0 ; 2*j = i + k .

    Le dénombrement des triplets est réalisable par récurrence, en ajoutant les éventuels nouveaux qui associent l'instant actuel (k)
    à deux instants antérieurs (i = k - 2*h , j = k - h); par exemple en codant:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Inc(k);
    IF (S[k]=0) THEN
      BEGIN
        i:= k; j:= k;
        WHILE (i>2) DO 
          BEGIN
            Dec(i, 2); Dec(j);
            IF ((s[i]=0) AND (s[j]=0)) THEN Inc(Ntrip)
          END
      END;
    La bouteille de chouchen est encore à moitié pleine, il me faut un remontant .


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  20. #20
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Recherche de milieux dans un tableau

    L'étude la plus rapide des longs parcours envisagés oblige à recourir à une programmation dynamique, et à considérer l'ensemble des (N) positions possibles du randonneur comme un graphe polycyclique, dont chaque sommet comporte deux pointeurs orientés vers les directions associées.
    Les instructions suivantes permettent de construire l'objet considéré, les directions étant déterminées par un procédé arithmétique (au lieu d'un choix manuel, comme dans l'énoncé du sujet).
    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
     CONST NmaxP = 10;
    
     TYPE P_Point = ^Point;
          Point = RECORD  Valeur: Word;
                          Suiv_1, Suiv_2: P_Point  END;
          LstP = ARRAY[0..(NmaxP - 1)] OF P_Point;
    
     PROCEDURE InitDir(VAR Gr_: LstP);
       VAR h, i, j, k: Word;
       BEGIN
         FOR k:= 0 TO (NmaxP - 1) DO New(Graphe[k]);
         FOR k:= 0 TO (NmaxP - 1) DO
           WITH Gr_[k] DO
             BEGIN
               Valeur:= k;
               h:= 3 * k; i:= (h + 1) MOD NmaxP; Suiv_1:= Gr_[i];
               h:= 7 * k; j:= (h + 2) MOD NmaxP; Suiv_2:= Gr_[j]
             END
       END;
    
      InitDir(Graphe);
    La suite de Prouhet-Thue-Morse, quant à elle, résulte du doublement réitéré en 19 étapes du doublet initial (True, False), avec inversion systématique des termes; La longueur finale du tableau est de 220 = 1048576 .
    Son comportement remarquable peut être vérifié sur l'observation des 128 premières et 128 dernières valeurs.
    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
     CONST B_20 = 1048576; // = 2^20
    
     TYPE LstB = ARRAY[0..(B_20 - 1)] OF Bool;
    
     VAR Morse: LstB;
    
     PROCEDURE InitM(VAR M_: LstB);
       VAR i: Byte; k, Min, Max: Z_32;
       BEGIN
         E(1015); Wt(12, 15, 'Min   Max - 1');
         Min:= 1; //Max:= 2;
         M_[0]:= True; M_[1]:= False;
         FOR i:= 1 TO 19 DO
           BEGIN
             Max:= 2 * Min; Min:= Max; Max:= 2 * Min;
             FOR k:= Min TO (Max - 1) DO M_[k]:= NOT M_[k - Min];
           END
       END;
    
      InitM(Morse);
    Nom : Graphe N=10.png
Affichages : 28
Taille : 1,7 Ko__Nom : Suite_Morse.png
Affichages : 28
Taille : 8,1 Ko


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Rechercher un objet dans un tableau d'objet
    Par mikaelm dans le forum Ruby
    Réponses: 6
    Dernier message: 11/06/2007, 18h58
  2. [Tableaux] question recherche et tri dans un tableau
    Par nicopoal dans le forum Fonctions
    Réponses: 7
    Dernier message: 25/01/2007, 17h41
  3. [Tableaux] Rechercher les doublons dans un tableau
    Par jym_22 dans le forum Fonctions
    Réponses: 5
    Dernier message: 15/11/2006, 10h47
  4. Rechercher une valeur dans un tableau
    Par pafi76 dans le forum Access
    Réponses: 2
    Dernier message: 29/06/2006, 15h23
  5. Faire une recherche de texte dans un tableau de variable
    Par alexxx69 dans le forum VB 6 et antérieur
    Réponses: 5
    Dernier message: 19/02/2006, 14h12

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo