Discussion :

[Cuve9]

Salut tout le monde,

Voilà mon problème :

j'essaye de trier les lignes d'un tableau de valeur dans l'ordre lexicographique.

J'ai déjà écrit un algorithme qui compare deux vecteurs de taille 4 dans l'ordre lexicographique. Je voudrais donc l'adapter pour trier les lignes d'un tableau dans l'ordre lexicographique mais je suis complètement bloqué...

Voilà mon algo :

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
 
program lexico
 
implicit none
 
integer, dimension(4) :: V=(/1,2,3,5/)
integer, dimension(4) :: M=(/1,2,3,6/)
integer :: i
logical :: b
i=1
b=.TRUE.
do while ((i.NE.5) .AND. (b))
   if (V(i).GT.M(i)) then
    write(*,"('M est avant V.')")
    b=.FALSE.
   elseif (V(i).LT.M(i)) then
       write(*,"('V est avant M.')")
       b=.FALSE.
   else
        i=i+1
 
   end if
end do
 
end program lexico

Je vous remercie d'avance pour votre aide.

Bonne soirée (ou bonne journée)

[Cuve9]

Si une personne pouvais me donner un petit coup de main, je serais extrêmement reconnaissant... Parce que là, je suis au point mort, je n'avance pas dans mon programme.
J'ai besoin de faire ce tri pour pouvoir continuer...

Merci,

[LittleOwl]

Bonjour,

Si j'ai bien saisi votre problème, vous souhaitez trier un tableau d'entiers à 2 dimensions (N lignes et M colonnes) selon l'ordre lexicographique.
Une façon de résoudre ce problème consiste à implanter un algorithme de tri dans le programme principal qui fait appel à une fonction permettant de comparer 2 vecteurs selon l'ordre lexicographique (le corps de cette fonction correspond au programme que vous avez écrit, moyennant quelques adaptation).

Par exemple, le canevas ci-dessous implante cette approche en utilisant l'algorithme du tri bulle pour trier le tableau. Cette algorithme de tri n'est pas le plus efficace, mais il est suffisant pour des tableaux de petites tailles et il est simple à écrire.

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
 
program lexico
 
implicit none
 
integer, dimension(N,M) :: t = (/.../) ! Tableau à trier
 
integer :: i, j
 
do i = 1, N
  do j = i+1, N
     if (CMP(t(i,:),t(j,:)) == .FALSE.) then
       call SWAP(t(i,:),t(j,:)
    end if
  end do
end do
 
contains
 
boolean function cmp(a,b)
 
integer, dimension(:), intent(in) :: a,b
 
! Compare 2 tableaux de dimensions 1 selon l'ordre lexicographique
! renvoie .TRUE. si a <= b
! renvoie .FALSE. si a > b
 
....
 
end function cmp
 
subroutine swap(a,b)
 
integer, dimension(:), intent(in) :: a,b
 
! echange les valeurs des tableaux de dimensions 1 a et b
 
....
 
end subroutine swap
 
end program lexico

En espérant que cette indication vous sera utile. Cordialement.

[Cuve9]

Bonjour,

Merci pour votre réponse, je commençais à perdre espoir.

J'ai écrit un code mais il y a deux-trois erreurs qui subsistent, j'ai mis en pièce jointe une capture d'écran des erreurs qui apparaissent lorsque je compile.

Voilà le code :

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
program lexico
 
implicit none
 
integer, parameter :: nbl=5
integer, parameter ::  nbc=3
integer,parameter, dimension(2) :: profil=(/nbl,nbc/)
integer, parameter, dimension(nbl*nbc) :: V=(/1,3,5,6,2,11,2,3,5,8,9,13,7,15,1/) ! Tableau à trier
integer, dimension(nbl,nbc) :: T=reshape(V,profil)
integer :: i, j
logical :: booleen
integer, dimension(1,nbc) :: Vec 
 
 
do i = 1, nbl
  do j = i+1,nbc
     if (CMP(T(i,:),T(j,:)).EQ..FALSE.) then
         Vec=T(i,1:nbc)
         T(i,1:nbc)=T(j,1:nbc)
         T(j,1:nbc)=Vec
    end if
  end do
end do
 
write(*,*)
write(*,"('Voici le tableau T dont les lignes sont triees dans l''ordre lexicographique')")
write(*,*)
 
 do i=1,nbl
      write(*,*) T(i,1:nbc)
    end do
 
contains
 
function CMP(a,b)
 
integer, dimension(:,:), intent(in) :: a,b
integer :: i
logical:: booleen
logical :: CMP
 
! Compare 2 tableaux de dimensions 1 selon l'ordre lexicographique
! renvoie .TRUE. si a <= b
! renvoie .FALSE. si a > b
 
i=1
booleen=.TRUE.
do while ((i.NE.5) .AND. (booleen))
   if (a(i,:).GT.b(i,:)) then
    booleen=.FALSE.
   elseif (a(i,:).LE.b(i,:)) then
       booleen=.TRUE.
   else
        i=i+1
    end if
end do
end function cmp
 
 
 
end program lexico

Encore un grand merci pour votre aide.

Ps : j'ai l'impression que votre code ne compare entre les différentes lignes que les éléments situées dans la première colonne ... Est-ce qu'il compare également les éléments situé dans les autres colonnes ?

Bien cordialement

[__dardanos__]

Salut,
J'ai corrigé les petits problèmes.

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
program lexico
    implicit none
    integer, parameter :: nbl=5, nbc=3
    integer :: i, j
    logical :: ok
    integer, dimension(:), allocatable :: Vec
    integer, dimension(:,:), allocatable :: T
 
    T = reshape( (/1,3,5,6,2,11,2,3,5,8,9,13,7,15,1/), (/nbl,nbc/) )
 
    do
        ok = .true.
        do i = 1, size(T,1)
            do j = i+1, size(T,1)
                if (.not. CMP( T(i,:), T(j,:) ) ) then
                    Vec = T(i,:) ; T(i,:) = T(j,:) ; T(j,:) = Vec
                    ok = .false.
                end if
            end do
        end do
        if (ok) exit
    enddo
 
    write(*,"('Voici le tableau T dont les lignes sont triees dans l''ordre lexicographique')")
    do i = 1, size(T,1)
        write(*,'(99i4)') T(i,:)
    end do
 
contains
 
    function CMP(a,b)
        integer, dimension(:), intent(in) :: a, b
        integer :: k
        logical :: CMP
 
        ! Compare 2 tableaux de dimensions 1 selon l'ordre lexicographique
        ! renvoie .TRUE. si a <= b
        ! renvoie .FALSE. si a > b
 
        do k = 1, size(a)
            if ( a(k) > b(k) ) then
                CMP = .FALSE.
                return
            elseif ( a(k) < b(k) ) then
                CMP = .TRUE.
                return
            endif
        enddo
        CMP = .TRUE.    ! identiques
 
    end function cmp
 
end program lexico

[Cuve9]

Tout d'abord merci à vous d'avoir pris le temps de répondre à mon problème.

Lorsque je lance le compilateur, il m'affiche segmentation fault. Je n'ai jamais rencontré cette erreur par le passé. Qu'est ce qu'elle signifie ?

[__dardanos__]

Le compilateur est trop ancien (Faire un 'gfortran -v' pour connaitre la version.)
J'utilise la norme 2003 pour l'allocation dynamique.

[Cuve9]

Oui dans ma version il faut ajouter la fonction allocate pour allouer les différents tableaux.

Après avoir fait les modifs nécessaires, les compilateur n'aime pas mon allocation pour Vec. J'ai fait deux allocations différentes, pour les deux il n'aime pas. Les 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
25
program testlexico
    implicit none
    integer, parameter :: nbl=5, nbc=3
    integer :: i, j
    logical :: ok
    integer, dimension(:,:), allocatable :: Vec
    integer, dimension(:,:), allocatable :: T
    integer :: pballocation
 
    T = reshape( (/1,3,5,6,2,11,2,3,5,8,9,13,7,15,1/), (/nbl,nbc/) )
 
     if(.not. allocated(Vec)) then
        allocate(Vec(1,nbc),stat=pballocation )
        if(pballocation .GT. 0) then
           stop " Erreur: probleme memoire "   
        end if
     end if
 
 
     if(.not. allocated(T)) then
        allocate(T(nbl,nbc),stat=pballocation )
        if(pballocation .GT. 0) then
           stop " Erreur: probleme memoire "   
        end if
     end if

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
program testlexico
    implicit none
    integer, parameter :: nbl=5, nbc=3
    integer :: i, j
    logical :: ok
    integer, dimension(:), allocatable :: Vec
    integer, dimension(:,:), allocatable :: T
    integer :: pballocation
 
    T = reshape( (/1,3,5,6,2,11,2,3,5,8,9,13,7,15,1/), (/nbl,nbc/) )
 
     if(.not. allocated(Vec)) then
        allocate(Vec(nbc),stat=pballocation )
        if(pballocation .GT. 0) then
           stop " Erreur: probleme memoire "   
        end if
     end if
 
 
     if(.not. allocated(T)) then
        allocate(T(nbl,nbc),stat=pballocation )
        if(pballocation .GT. 0) then
           stop " Erreur: probleme memoire "   
        end if
     end if

Le code en entier :

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
program testlexico
    implicit none
    integer, parameter :: nbl=5, nbc=3
    integer :: i, j
    logical :: ok
    integer, dimension(:), allocatable :: Vec
    integer, dimension(:,:), allocatable :: T
    integer :: pballocation
 
    T = reshape( (/1,3,5,6,2,11,2,3,5,8,9,13,7,15,1/), (/nbl,nbc/) )
 
     if(.not. allocated(Vec)) then
        allocate(Vec(nbc),stat=pballocation )
        if(pballocation .GT. 0) then
           stop " Erreur: probleme memoire "   
        end if
     end if
 
 
     if(.not. allocated(T)) then
        allocate(T(nbl,nbc),stat=pballocation )
        if(pballocation .GT. 0) then
           stop " Erreur: probleme memoire "   
        end if
     end if
 
    do i = 1, size(T,1)
        write(*,"(99i4)") T(i,:)
    end do
 
    do
        ok = .true.
        do i = 1, size(T,1)
            do j = i+1, size(T,1)
                if (.not. CMP( T(i,:), T(j,:) ) ) then
                    Vec = T(i,:) ; T(i,:) = T(j,:) ; T(j,:) = Vec
                    ok = .false.
                end if
            end do
        end do
        if (ok) exit
    enddo
 
    write(*,"('Voici le tableau T dont les lignes sont triees dans l''ordre lexicographique')")
    do i = 1, size(T,1)
         write(*,"(99i4)") T(i,:)
    end do
 
contains
 
    function CMP(a,b)
        integer, dimension(:), intent(in) :: a, b
        integer :: k
        logical :: CMP
 
        ! Compare 2 tableaux de dimensions 1 selon l'ordre lexicographique
        ! renvoie .TRUE. si a <= b
        ! renvoie .FALSE. si a > b
 
        do k = 1, size(a)
            if ( a(k) > b(k) ) then
                CMP = .FALSE.
                return
            elseif ( a(k) < b(k) ) then
                CMP = .TRUE.
                return
            endif
        enddo
        CMP = .TRUE.    ! identiques
 
    end function cmp
 
end program testlexico

[__dardanos__]

Alors, on supprime l'alloc dyn :

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
program lexico
    implicit none
    integer, parameter :: nbl=5, nbc=3
    integer :: i, j
    logical :: ok
    integer, dimension(nbc) :: Vec
    integer, dimension(nbl,nbc) :: T
 
    T = reshape( (/1,3,5,6,2,11,2,3,5,8,9,13,7,15,1/), (/nbl,nbc/) )
 
    do
        ok = .true.
        do i = 1, size(T,1)
            do j = i+1, size(T,1)
                if (.not. CMP( T(i,:), T(j,:) ) ) then
                    Vec = T(i,:) ; T(i,:) = T(j,:) ; T(j,:) = Vec
                    ok = .false.
                end if
            end do
        end do
        if (ok) exit
    enddo
 
    write(*,"('Voici le tableau T dont les lignes sont triees dans l''ordre lexicographique')")
    do i = 1, size(T,1)
        write(*,'(99i4)') T(i,:)
    end do
 
contains
 
    function CMP(a,b)
        integer, dimension(:), intent(in) :: a, b
        integer :: k
        logical :: CMP
 
        ! Compare 2 tableaux de dimensions 1 selon l'ordre lexicographique
        ! renvoie .TRUE. si a <= b
        ! renvoie .FALSE. si a > b
 
        do k = 1, size(a)
            if ( a(k) > b(k) ) then
                CMP = .FALSE.
                return
            elseif ( a(k) < b(k) ) then
                CMP = .TRUE.
                return
            endif
        enddo
        CMP = .TRUE.    ! identiques
 
    end function cmp
 
end program lexico

[Cuve9]

Yeah ça roule ! Merci Dardanos, tu me retires une grosse épine du pied. Je suis en première année d'école d'ingé et mon projet porte sur le krigeage, c'est très intéressant mais que c'est dure! Cest la première année que je fais vraiment de l'informatique, les années précédentes j'étais en licence de géologie...

Merci encore mille fois à LittleOwl et à Dardanos !

Bonne continuation