Discussion :

[hongjan]

Bonsoir,
je cherche à écrire un algorithme qui permet de parcourir un tableau pour calculer le nombre des entiers redondants ainsi que leurs indices dans le tableau.
Exemple: soit le tableau en entrée A le suivant A=[1,8,3,8,12,8,1]. La sortie de ce programme est donc deux tableaux le premier B=[2,3] et C=[0,6,1,3,5].
D'avance merci.

[Auteur]

Bonsoir

comment ferais-tu pour écrire cet algo ?

[hongjan]

j'ai pensé d'abord à trier le tableau A donc on aura A_tri=[1,1,3,8,8,8,12]
ensuite on déclare un autre tableau Treated initialisé à zeros de meme taille que A pour marquer les cases qui sont déjà traitées. et voici l'algorithme que je propose:
K=1
For i = 0 à taille de A_tri
For j=0 à taille de A_tri
if A_tri(i)==A_tri(j) && i<>j && Treated(i)<>1
B(k)=B(k)+1
Treated(j)==1
if A_tri(i)<>A_tri(i+1)
k=k+1
end if
end if
end for
end for

De cette facon je peux pas récupérer le tableau d'indices et je voulais pas vraiment passer par l’étape de tri. merci

[Deuzz]

bonsoir

Voici une proposition

• Lecture du tableau
  • On recherche le plus grand entier (et on place la valeur dans max)
  • et les éventuelles occurrences de 0 (le cas échéant on indique le nombre de fois dans n et les indices dans un tableau P()
• Si n est supérieur à 1 on note la valeur dans B() et on transfert les différents indices de P() vers C().
• On répète le procédé jusqu'à max

Ce qui donnerait à peu près un truc comme ça :

J'y connais rien à la syntaxe alors il y a surement quelques trucs à modifier.
b et c me servent à savoir à quel indice je suis rendu dans le remplissage de B() et C().

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
b=0
c=0
n = 0
max = 0
 
For i=0 à taille de A               //1ère lecture
    if A(i)>max                           // recherche du maximum
        max = A(i)
    end if
    if A(i) = 0                             // et des 0
        P(n)= i                                // stockage des indices  
        n= n+1                               // et du nombre de répétition
    end if
end for
if n>1
    B(b)=n                                // remplissage de B
    b = b + 1
    for k = 0 to n
        C(c) = P(k)                         // et de C
        c=c+1
    end for
end if
P()=0                                 // remise à zéro des variables 
n = 0
 
For j=1 to max                 // on recommence 
    for i=0 à taille A()
        if A(i) = j
            P(n)= i
            n= n+1
        end if
    end for
    if n>1
        B(b)=n
        b = b + 1
        for k = 0 to n
            C(c) = P(k)
            c=c+1
        end for
    end if
    P()=0
    n = 0
end for

[anapurna]

salut

pourquoi ne pas te servir d'un tableaux d'indice ou a chaque valeur trouvé tu incrémente la case

Code :

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

1
2
3
4
 
  For i =low(A_tri) 0 à  High(A_tri) do
    B[A_tri[i]] := B[A_tri[i]]+1;
  end for

tu te trouvera donc avec un tableau indicé ou la valeur inclut correspond au nombre d'occurence de cette indice
si je reprend ton exemple

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
 
A_tri=[1,1,3,8,8,8,12]
 
[1] = 2
[2] = 0
[3] = 1
[4] = 0
[5] = 0
[6] = 0 
[7] = 0
[8] = 3 
[9] = 0
[10] = 0
[11] = 0
[12] = 1

[Deuzz]

Pourquoi ne pas te servir d'un tableaux d'indice ou a chaque valeur trouvé tu incrémente la case

A mon avis, ta solution ne convient pas à Hongjan puisqu'elle a les mêmes défauts que sa proposition :

De cette facon je peux pas récupérer le tableau d'indices et je voulais pas vraiment passer par l’étape de tri.

Le but de l'exercice est d'obtenir les tableaux B() donnant les nombres de répétition et C() recensant les indices des nombres répétés dans le tableau A()

[Flodelarab]

Bonjour,

question bête: pourquoi vous faites pas simple?
On parcourt le tableau et on note la quantité et les indices.

Exemple concret:

Code :

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

1
2
3
4
5
6
7
8
$ cat /tmp/redondance.txt
1
8
3
8
12
8
1

Code :

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

1
2
3
4
5
6
7
8
9
10
$ awk '{qte[$1]++;indice[$1]=indice[$1]"\n"NR;} END{for (i in qte) if (qte[i]>1) print qte[i]" "; for (i in qte) if (qte[i]>1) print indice[i];}' /tmp/redondance.txt
2
3
 
1
7
 
2
4
6

[yahiko]

1. Tout d'abord, tu peux associer chaque nombre du tableau à son indice de façon explicite comme ceci :
A=[1,8,3,8,12,8,1] => A'=[(1,0), (8,1), (3,2), (8,3), (12,4), (8,5), (1,6)]
On obtient donc un tableau de couples.

2. Ensuite tu tries ton nouveau tableau A' sur le premier élément de chaque couple (et éventuellement sur le second élément du couple en deuxième critère de tri si ton tri n'est pas stable) :
A"=[(1,0), (1,6), (3,2) , (8,1), (8,3), (8,5), (12,4)]

3. Tu parcours linéairement ton tableau une fois trié pour générer tes deux sous-tableaux résultat :
B=[2, 3]
C=[0, 6, 1, 3, 5]

Si besoin, tu peux trier le tableau C avoir les indices dans l'ordre croissant :
C'=[0, 1, 3, 5, 6]