Recherche Idee/Suggestion sur Algo

Version imprimable

24/08/2008, 23h09
Danyel

Recherche Idee/Suggestion sur Algo
Salut All,

Je flanche sur le moyen (efficace) de realiser un petit algo dont voici son expose.
(Je simplifie au maximum sur l'essentiel)
- J'ai dix cases numerotees (1 à 10) avec un chiffre dans chacun.
- Le chiffre peut etre identique ou non à une autre case.
- Il peut y avoir plusieurs possibilites de chiffres identiques mais differents dans la valeur.
Alors avec cela, je dois realiser un algo qui me permette de savoir quelles cases ont des chiffres identiques ... et je vois pas pour une bonne solution efficace et optimise.

Merci pour votre aide.
Thx Danyel.
25/08/2008, 10h32
grrrkewel

Salut Danyel,

Tu as cherché du côté des différents algos de tri (tri à bulle, récursif, etc...)???
Ca te permettrai de trouver les valeurs égales rapidement je pense.:roll:

Citation:

Il peut y avoir plusieurs possibilites de chiffres identiques mais differents dans la valeur.

Cette condition n'est pas très claire je trouve, ou c'est moi qui suis idiot...;)

Aller, bon courage.
25/08/2008, 10h58
Elstak

hmm je suis pas sur mais si je me souviens bien de mes cours d'algo je dirais:

tu fais une liste, tu retire le 1er élément dont tu conserves la valeur, tu compare les autres et si c'est la même tu les retires aussi jusqu'à ce que ta liste soit vide. Après je sais pas ce que tu veux faire, si c'est juste le numéro de la case tu fais une liste de structure avec dedans la valeur et la position. Non? :roll:
25/08/2008, 17h46
Danyel

Citation:

Envoyé par grrrkewel

Tu as cherché du côté des différents algos de tri (tri à bulle, récursif, etc...)???
Ca te permettrai de trouver les valeurs égales rapidement je pense.:roll:

Effectuer le tri n'est pas reellement le probleme, c'est plutot qu'il faut que je retrouve l'emplacement de la case qui le contient.

Citation:

Envoyé par grrrkewel

Il peut y avoir plusieurs possibilites de chiffres identiques mais differents dans la valeur.
Cette condition n'est pas très claire je trouve, ou c'est moi qui suis idiot...;)

Et bien par exemple, il peut y a voir 1 serie du chiffre '10' et une autre serie d'un autre chiffre '15' par exemple
25/08/2008, 17h47
Danyel

Citation:

Envoyé par Elstak

si c'est juste le numéro de la case tu fais une liste de structure avec dedans la valeur et la position.

Qu'entends tu par liste de structure ?
25/08/2008, 18h12
OhMonBato

Par exemple un tableau Nombre(x,y), x étant l'indice de ton nombre, y valant 0 ou 1, 0 pour la valeur du nombre, 1 sa position dans ta liste.

Tu tries ton tableau Nombre par ordre croissant, tu n'as plus ensuite qu'à lire le tableau de son premier à son dernier indice et voir si tu as des nombres égaux, combien sont égaux et quelle est leur position.

Mais bon, les jours finissant en "i", je peux dire des co....ies :aie:
25/08/2008, 21h02
Danyel

C'est effectivement une possibilite, mais apres qq recherches, il semblerait que faire un tri sur un tableau à multi-dimensions soit une vraie galere (cf : tomlev)

N'hésitez pas à appronfondir ou signaler d'autres solutions ;)
25/08/2008, 21h35
Skalp

Tu n'as pas besoin du nombre d'occurrence, tu veux juste l'information "présent plus d'une fois" ?
Tu n'as pas besoin de retenir les valeurs, tu veux juste les positions ?
(je n'ai pas d'idée a priori, c'est pour faire avancer la réflexion :) )

Bonsoir,

Je ne vois pas réellement où est le problème :

Code:

1
2
3
4
5
6
7
8
9
10
11
i = 0
TANT QUE i < 10
    j = i + 1
    TANT QUE j < 10
          SI case[i] = case[j]
               STOCKAGE(i, j, case[i])
          FIN SI
          j = j +1
     FIN TANT QUE
     i = i + 1
FIN TANT QUE

Ne fait-il pas simplement l'affaire ?

25/08/2008, 23h43
OhMonBato

Citation:

Envoyé par Danyel

C'est effectivement une possibilite, mais apres qq recherches, il semblerait que faire un tri sur un tableau à multi-dimensions soit une vraie galere (cf : tomlev)

Mais là il ne s'agit que de trier le tableau en utilisant uniquement le Nombre(x,0) pour reprendre mon exemple donc je ne vois pas trop où est le problème.
26/08/2008, 00h32
Tusbar

Plusieurs dimensions ? Faudra m'expliquer là...
26/08/2008, 01h18
Danyel

Citation:

Envoyé par Skalp

Tu n'as pas besoin du nombre d'occurrence, tu veux juste l'information "présent plus d'une fois" ?

Non.

Citation:

Envoyé par Skalp

Tu n'as pas besoin de retenir les valeurs, tu veux juste les positions ?

Exact.
Avoir le/les valeurs pourrait etre un plus, mais restons sur l'essentiel pour l'instant ;)

Citation:

Envoyé par Tusbar

Code algo :
i = 0
TANT QUE i < 10
j = i + 1
TANT QUE j < 10
SI case[i] = case[j]
STOCKAGE(i, j, case[i])
FIN SI
j = j +1
FIN TANT QUE
i = i + 1
FIN TANT QUE

Ne fait-il pas simplement l'affaire ?

Je vais voir et faire des tests en conditions reelles.

Citation:

Envoyé par OhMonBato

Mais là il ne s'agit que de trier le tableau en utilisant uniquement le Nombre(x,0) pour reprendre mon exemple donc je ne vois pas trop où est le problème.

J'ai fait des recherches et c'est le resultat qui en resulte
... je recherche le post en question ...
http://www.developpez.net/forums/d53...au-dimensions/
Et la methode de Tomlev me laisse sans voix :lol:

Citation:

Envoyé par Tusbar

Plusieurs dimensions ? Faudra m'expliquer là...

Tableau1(x) = Simple Dimension
Tableau2(x,y,z) = Multi Dimension

Je continue a chercher et je pars essayer le code de Tusbar sur le champs.
Merci à tous pour votre aide.

A l'ancienne (style VB6, on se refait pas, et j'ignore si il y a des méthodes de tri plus efficaces en Net) :

Il te faut juste un bouton et 2 controles text dont tu mettras la propriété Multiline à True.
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 25 26 27 28 29 30 31 32 33 34 35 36 PublicClass Form1 Private Nbre(20, 1) AsInteger PrivateSub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click 'Création d'un tableau contenant 20 nombres entiers Dim i AsInteger Dim j AsInteger For i = 1 To 20 Nbre(i, 0) = CInt(Int(21) * Rnd()) 'Le nombre Nbre(i, 1) = i 'Sa place Next 'Affichage des données brutes dans un textbox TextBox1.Clear() For i = 1 To 20 TextBox1.Text = TextBox1.Text & Nbre(i, 0) & vbCrLf Next 'Tri du tableau pour mettre les nombres en ordre croissant For i = 1 To 19 For j = i + 1 To 20 If Nbre(j, 0) < Nbre(i, 0) Then Nbre(0, 0) = Nbre(i, 0) Nbre(0, 1) = Nbre(i, 1) Nbre(i, 0) = Nbre(j, 0) Nbre(i, 1) = Nbre(j, 1) Nbre(j, 0) = Nbre(0, 0) Nbre(j, 1) = Nbre(0, 1) EndIf Next Next 'Affichage des données triées dans un textbox TextBox2.Clear() For i = 1 To 20 TextBox2.Text = TextBox2.Text & Nbre(i, 0) & Chr(9) & Nbre(i, 1) & vbCrLf Next EndSub EndClass
Une fois le tableau trié, je pense que le lire et voir combien de nombres égaux sont dans la liste ne représente pas trop de difficultés.
Evidemment s'il y a beaucoup de nombres à trier, faut voir le temps que ça prend.

Tu veux une belle solution ? ;)

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
25
26
27
28
29
30
31
32
33
 
class CaseValeur
    {
        public int Numero { get; set; }
        public int Valeur { get; set; }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            List<CaseValeur> casesValeurs = new List<CaseValeur>
            {
                new CaseValeur { Numero = 1, Valeur = 1 },
                new CaseValeur { Numero = 2, Valeur = 4 },
                new CaseValeur { Numero = 3, Valeur = 6 },
                new CaseValeur { Numero = 4, Valeur = 7 },
                new CaseValeur { Numero = 5, Valeur = 3 },
                new CaseValeur { Numero = 6, Valeur = 3 },
                new CaseValeur { Numero = 7, Valeur = 1 },
                new CaseValeur { Numero = 8, Valeur = 9 },
                new CaseValeur { Numero = 9, Valeur = 9 },
                new CaseValeur { Numero = 10, Valeur = 0 }
            };
 
            var counts = (from c in casesValeurs
                          group c by c.Valeur into groups
                          where groups.Count() > 1
                          select groups).Count();
 
            Console.WriteLine(counts);
        }
    }

EDIT : La solution proposée renvoie le nombre de groupes de valeurs (un groupe de valeurs est une valeur qui apparaît plusieurs fois).
En supprimant le dernier Count() tu récupères les cases groupées par valeurs quand la valeur apparaît plus d'une fois dans les cases.

26/08/2008, 10h17
Elstak

Citation:

Qu'entends tu par liste de structure ?

Voilà, je pensais à quelque chose qui ressemble à ce que propose saumon. Tu utilise son type Casevaleur qui a le numero et la valeur !

bon apres son traitement j'ai pas tout suivi comment que ca marche ce truc, mais bon :aie:
26/08/2008, 18h38
Danyel

Un grand merci à tous pour votre implication.
Je vais encore tester et tester :lol:

Merci aussi saumon pour ta belle solution, mais elle est pas en vb 8O
Certes elle parait la plus optimisee, mais je saurais pas correctement la convertir.