Exercice sur structure de ConnexionRésolu

Question

Bonjour, je reviens vers toi une fois de plus cptpingu pour ceci : 

" Un programme permet de mémoriser les connexions faites à partir d’un ordinateur sur différents sites. À chaque connexion, l’adresse IP du site est mémorisée ainsi que la durée de connexion en minutes. Le programme tourne en arrière-plan et permet de remplir un tableau de l’ensemble des connexions faites depuis le dernière démarrage de l’ordinateur. On a, à notre disposition les déclarations suivantes " :

uneConnexion : structure ip : chaine duree : entierfinstructurelesConnexions[1..500] : uneConnexionnbConnexions : entier // nombre de cases remplies dans lesConnexions

On doit écrire (en algo ou dans le langage de votre choix) les fonctionnalités suivantes (c’est donc à chaque fois un extrait de programme qui est demandé, en partant du principe que le tableau lesConnexions est partiellement rempli et que la variable nbConnexions contient le nombre de cases remplies dans le tableau) : 

a. écrire l’extrait de programme qui permet d’afficher la durée totale de connexions, en minutes, depuis le dernier démarrage de l’ordi.

b. écrire l’extrait de programme qui permet d’afficher la liste des sites visités (donc la liste des IP), en n’affichant qu’une fois chaque IP. Attention, le tableau étant rempli au fur et à mesure des connexions, il n’est pas trié.

Voilà pour la a) et b) j'ai fais cela (je n'ai pas écris d'algo, ni de code, juste de la compréhension...) :

a) dernier démarrage de l'ordi : demordi : entier   durée totale de connexions : durtot : entier durtot = duree1 + duree2 + ............. + duree500 durtot - demordi afficher "durée totale de connexions :" + durtot b) afficher la liste des addresses IP :iptot = ip1 + ip2 + ... + ip500 - (les doublons).

cptpingu · Answer

Bonjour.

a) Pourquoi soustraire la date de démarrage de l'ordinateur ? Tu as visité "google.fr" pendant 3 min, et "codes-sources.com" pendant 5 min. Que l'ordinateur ait démarré il y 10 min ou il y a 3 mois, ça ne change pas le fait que tu aies 8 min de connexions cumulées.

b) C'est un simple affichage d'ip. La seule difficulté, est de n'afficher qu'une seule fois chaque ip. Deux solutions pour cela: trier le tableau d'ip avant de l'afficher (car les doublons seront côte à côte, donc facile à ne pas afficher plusieurs fois), ou alors utiliser une collection garantissant l'unicité (en C++, un std::set, mais j'ai peur que ce soit de la "triche" :p).
On peut aussi (mais c'est très très moche, et peu optimisé/lent) faire ceci: avant d'afficher une ip, on regarde dans le tableau si l'ip a déjà été "vu" (en partant de la position actuelle non comprise vers le début du tableau).

Encore une fois, je conseille l'utilisation du C++, afin de valider tes exercices.

TheRogerFederer · Answer

a) Mouais je m'en doutais un peu, disons que c'étais pour confirmer une intuition............ hormis cela, ce que j'ai fais ai censé être la bonne voie ??

b) Oui oui tout a fait cela je l'avais compris, c'est juste que pour supprimer les doublons je n'ai pas encore vu (d'ailleurs je pense trier le tableau serait ce qu'il y a de plus proche de ce que j'ai vu).............! j'ai vu que certains faisaient une double boucle for, d'autres font qqch du genre :

while (RL_FIN_TRAIT_TRI!=1)
{
RL_FIN_TRAIT_TRI=1;
 
   for (i=0;i<15;i++)
    {
        if (tab[i]==tab[i+1])
        {
            for(j=i+1;j<nb_tab;j++)
            {
            tab[j] = tab[j+1];
            }
 
        RL_FIN_TRAIT_TRI = 0;
        compteur_doublon = compteur_doublon +1;
        printf("
doublon : %d
",compteur_doublon);
        }
        else
        {
        }
    }
}

Je précise que ce qu'il y a dans le code n'a rien a voir avec l'exo, c'est un exemple de code ou est utilisé un algo pour supprimer les doublons (il se peut que le bout de code ne fasse pas ce qui est recherché car cela n'est qu'un partie du code).

cptpingu · Answer

a) Le principe me paraissait ok.

b) C'est un code qui supprime les doublons alors qu'ils sont déjà côte à côte. Il le fait de manière crade (pas optimisé du tout, bien lent). Dans l'exercice, il n'est pas nécessaire de supprimer les doublons, il suffit simplement de ne pas les afficher plusieurs fois. Si tu tries, alors les doublons seront contigüs. Dans ce cas, il te suffit de ne pas afficher un élément si l'élément n - 1 est identique. C'est aussi simple que ça.
La seule réelle difficulté de cet exercice va être de trier ta liste. (Je te conseille de créer une fonction "tri", qui prend en argument un tableau et sa taille, et qui trie le tableau).


Améliorer votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

TheRogerFederer · Answer

D'accord j'essaye cela et je te montre ce que j'ai fais.

TheRogerFederer · Answer

Re-Bonjour, est ce que un tri à bulle comme cela serai bien :

// tri à bulle 
#define TRUE 1
#define FALSE 0
void tri_a_bulle (int*t, int n)
{ 
   int j = 0 ;
   int tmp = 0 ;
   int en_desordre = 1 ;
   while (en_desordre)
   {
      en_desordre = FALSE ;   
      for(j =0; j < n-1; j++)
      { 
         if(t[j] > t[j+1])
         {
            tmp = t[j+1] ;
            t[j+1] = t[j] ;
            t[j] = tmp ;
            en_desordre = TRUE ;
         }
      }
   }
}

???

cptpingu · Answer

Pour savoir si ça fonctionne, il suffit de le tester :).
Si tu lui donnes un tableau, est-ce que tu le retrouves trié ? As-tu testé avec différentes entrées pour t'assurer que tout allait bien ?

TheRogerFederer · Answer

En faite je pense faire plutôt comme cela :

int main () 
{
 
 // déclarations
 int i, j ; // compteur de boucle 
 int numcase ; // variable qui contient l'indice minimum
 int sauv ; // variable de permutation
 int n ; // dimension tableau
 int vec[5] ; // tableau qui contient 5 éléments
 
 // début
 printf(" Entrez la dimension du tableau : ") ;
 scanf("%d", &n) ;
 for (i = 0; i < n; i++)
 {
  printf(" Entrez l'\x82l\x82ment num\x82ro %d : ", i+1) ;
  scanf("%d", &vec[i]) ;
 }
 for (i = 0; i < n-1; i++)
 {
  numcase = i ;
  
  // -- recherche du plus petit élément de i à n --
  for (j = i+1; j < n; j++)
  {
   if (vec[j] < vec[numcase])
   { 
    numcase = j ;
   }
  }
  
  // échange des 2 cases
  sauv = vec[numcase] ;
  vec[numcase] = vec[i] ;
  vec[i] = sauv ;
 }
 
 // affichage du résultat
 for (i = 0; i < n; i++)
 {
  printf(" Le r\x82sultat du tri est : %d
 ", vec[i]) ;
 }
 
return 0 ;

}


Par contre si je rentre des adresses ip du genre : 192.168.1.12, l'interpréteur de commande me fait n'importe quoi, tu pourrait me dire dans quoi contenir le format d'une adresse ip ? Ou quel type au moins ?

cptpingu · Answer

Souviens toi de ce que l'on a vu précédemment. On découpe un code en petites fonctions ! Donc pour moi, ça part mal.

Tu devrais avoir une fonction de tri. La fonction de tri devrait elle même utiliser une fonction qui inverse deux valeurs, et une fonction qui compare deux adresses ip pour dire qui est la plus petite.

Tu devrais aussi avoir une fonction qui demande les éléments du tableau, et rempli un tableau. De même, il te faudrait une fonction qui affiche le temps de connexions cumulées, une fonction qui affiche les ips (c'est elle qui va se servir de la fonction de tri).

L'exercice est un prétexte à la création de fonctions, et au découpage du code. Si tu mets tout dans le main en mode crado/indigeste, tu passes à côté de ce qu'on te demande.

Fais-le proprement, commence par te demander comment découper ton code. Puis liste les fonctions dont tu as besoin. Enfin, écris ces fonctions, en commençant par les plus "faciles" (celles qui ne dépendent pas d'autres fonctions, et qui sont utilisées par d'autres).

Je t'invite aussi à créer une fonction de "debug", c'est-à-dire une fonction que tu ne vas pas garder au final, mais qui va te servir à "voir" ce qu'il se passe pendant la phase de développement. Cette fonction affichera l'état du tableau (la liste des toutes les ip + durée). Créé aussi une fonction (que tu ne vas pas garder non plus) qui retourne un tableau pré-rempli de valeurs de test (sinon tu vas passer ton temps à re-remplir les mêmes valeurs). Une fois ton programme terminé, tu remplaceras la fonction de pré-remplissage par la fonction qui remplie en demandant à l'utilisateur.

quel type au moins ?
L'ip est une chaîne de caractères.


Améliorer votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

TheRogerFederer · Answer

Ouch ça fait beaucoup de chose à faire ;)

fred · Answer

Bonjour tous le monde, cptpingu j'ai suivi ton résonnement mais je bloque pour la fonction qui affiche les ips

cptpingu · Answer

@fred: Il te suffit de réaliser les étapes suivantes:

 Faire une fonction qui compare deux ips, et dit qui est la plus petite des deux (donc qui prend 4 arguments, un char* + taille pour la première ip, ainsi qu'un autre char* + taille pour la deuxième). Renvoyer "vrai" si la première ip est inférieur à la deuxième (facile à faire, il suffit de comparer si le premier caractère est bien inférieur. Si c'est le cas c'est vrai, sinon c'est faux. Si les deux caractères sont identiques, recommencer la logique sur le prochain caractère. Bien penser à gérer les cas particuliers où les deux chaines n'ont pas la même taille.).
 Faire une fonction qui trie un tableau (tu lui donnes un tableau de char* contenant les ips + la taille du tableau). La fonction qui compare deux ips sera utilisée.
 Afficher les ips triées. Comme les doublons sont côte à côte, ne pas les afficher est trivial. On n'affiche pas une ip si l'ip à l'index n - 1, est identique.
 Facultativement, on pourrait écrire une méthode qui échange deux ips (c'est plus propre). Il n'est pas choquant que l'inversion se fasse directement dans la méthode de trie.


En soi, l'exercice demandé n'est vraiment pas difficile (volontairement), la difficulté est dans le choix du découpage de code.


Améliorer votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

fred · Answer

Dans la première étape, la taille pour les adresses ips placée en paramètre est elle obtenu dans une autre fonction?

cptpingu · Answer

À vrai dire, l'ip étant une chaîne de caractères, il est aisé d'obtenir sa taille via un "strlen". Il y a deux choix possibles pour la signature:

  Soit on met deux char*, et ne se soucie pas de la taille. Il suffit juste de vérifier quand on arrive sur le caractère spécial '\0', qui signifie la fin de la chaîne, sur l'une des deux chaînes .
  Soit on met deux char* + leur taille respective. Il n'est donc plus nécessaire de vérifier la présence d'un '\0'.

L'avantage de préciser les tailles est de pouvoir comparer deux chaînes ou deux "débuts" de chaînes (plus générique). Le défaut est que c'est plus compliqué que la première version. Si c'est plus simple pour toi, la première version est tout aussi juste que la deuxième, mais est plus facile à mettre en place.

TheRogerFederer · Answer

Bonjour, cela fait longtemps que je ne suis pas venu ici, désolé mais j'ai été pas mal occupé dans d'autre matière.

bon j'ai pas écris du C++ mais seulement de l'algo pour le moment pour voir un peu, voilà à quoi je suis arrivé :

(n-1 : désigne le dernière élément du tableaun-2 : désigne l'avant dernier élément du tableau......2 : désigne le deuxième élément du tableau1 : désigne le premiere élément du tableau)afficher la liste des adresses IP :i, j : entier // compteur de boucle min : entier // variable qui contient l'indice minimum temp : entier // variable de permutationn : entier // dimension du tableauchar* tableau[500] = {ip1, ip2,..., ip500}debut	afficher "entrez la dimension du tableau :"	saisir n	pour i allant de 0 a n		afficher "entrez l'element numero %d :" + i+1 		saisir tableau[i]		i++	fin pour	pour i allant de 0 a n-1		min = i		// recherche du plus petit élément de i a n		pour j allant de i+1 a j < n 			si tableau[j] < tableau[min]				min = j 				j++			fin si		fin pour		// échange de 2 cases		temp = tableau[min]		tableau[min] = tableau[i]		tableau[i] = temp 		i++	fin pour		// non-affichage des doublons	pour i allant de 0 a n		si n-1 == n-2 alors				afficher "l'adresse" + n-1		fin si		i++	fin pour		// affichage du résultat	pour i allant de 0 a i < n 		afficher "%d" + tableau[i] 		i++	fin pourfin

cptpingu · Answer

@TheRogerFederer: En théorie, c'est assez approchant de ce qui est demandé (Le non-affichage des doublons a plusieurs erreurs, néanmoins: problème de borne + affichage de la même valeur N fois).
Dans la pratique, ce qui me gêne, c'est que tu es à côté de ce que l'on te demande de travailler. Il ne faut pas faire un gros paté, puis essayer de le découper, mais plutôt prendre l'habitude, au plus tôt, de découper en fonctions, et de les assembler pour réaliser ton programme. Attention de ne pas prendre de mauvaises habitudes qui te seront rapidement préjudiciables au fur et à mesure que la complexité des exercices qu'on te demandera, augmentera.
 

Améliorer votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

TheRogerFederer · Answer

Pour : "(Le non-affichage des doublons a plusieurs erreurs, néanmoins: problème de borne + affichage de la même valeur N fois).", je m'en doutais mais comment écrire que je veux le faire pour tout élément ??

Oui je n'en doute pas tu me l'avais déjà dis avant désolé..........

cptpingu · Answer

Chaque chose en son temps. Commence déjà par créer le programme en C, qui affiche la moyenne et les ips (en affichant les doublons, sans tri).
Une fois cela fait, tu feras la version qui affiche les ips triées, avec doublons.
Enfin, on mettra en place le non affichage des doublons.

N'essaie jamais de tout faire "d'un coup". Dans la "vraie vie", aucun programmeur n'essaie de tout coder (écrire des milliers de lignes) puis d'essayer de compiler, en si disant: "ok, j'ai tout écris, je corrige les erreurs de compilation et j'ai fini". Généralement, ce que l'on fait, c'est qu'on code une toute petite partie du problème et on la test. Si ça fonctionne, on "avance", et on rajoute des choses. On reproduit ce processus jusqu'à avoir tout le programme.

TheRogerFederer · Answer

Est ce que cette fonction serait bien pour les doublons :

int eliminedoublon (int tab[], int n)
{
    int i, j ;
    for(i = 1; i < n; i++) // i va balayer sur tout le tableau sauf le       1er élément qui reste à sa place 
    {
         for(j = 0; j < n; j++) // j va balayer les éléments déjà remplis pour comparaison avec un élément pointé par i
         {
                if(tab[j] == tab[i])
                break ; // Il s'agit d'un doublon   
         }
                     if (j == taille) // Vrai s'il ne s'agit pas d'un doublon 
                     {
                         tab[taille++] = tab[i] ; 
                     }
                    
    }

return (taille); // Taille utile du tableau, il faut bien en informer l'appelant

}

(taille correspond à n)

??????

cptpingu · Answer

Au niveau théorique: Comme déjà expliqué, il ne faut pas "éliminer" les doublons. Juste ne pas les afficher.

Au niveau technique: l'algo est horriblement coûteux (complexité en O(n²), alors que le non affichage des doublons est de O(n) !). La raison pour laquelle on trie avant, c'est que c'est bien moins couteux de trier (complexité O(nlog(n))) puis éviter les doublons lors de l'affichage (complexité O(n)).

Ta méthode te coûte: O(n²) + O(n) alors que le prix devrait plutôt se situer vers O(nlog(n)) + O(n).

Je ne vais pas rentrer dans les détails de ce qu'est une complexité algorithmique, mais pour vulgariser ta méthode doit être environ 100 fois plus lente que nécessaire. Pour peu d'éléments, tu ne le verras pas de suite, mais si on agrandit la taille du tableau, tu auras le temps de prendre un café avant d'avoir ta réponse.

De plus, essaie de faire l'exo par étape, comme je te l'ai décris précédemment. Le non affichage des doublons est la dernière étape. Fais les choses dans l'ordre, sinon tu vas avoir du mal à t'en sortir.

cptpingu · Answer

Le sujet n'ayant pas eu de réponse depuis un moment (aucun de vous n'a posté la solution, ce qui est dommage pour ceux qui tomberaient sur ce fil de discussion), je me permet de proposer une solution propre. #include #include typedef struct { char ip[32]; int duree; } Connexion; void echange(Connexion* a, Connexion* b) { Connexion tmp = *a; *a = *b; *b = tmp; } /*! ** La "vraie" fonction est "strcmp", mais comme ** il n'est pas indiqué si elle est autorisée pour ** l'exercice, en voici une version "maison". ** ** Elle retourne: ** 1: s1 est plus grand que s2 ** 0: s1 est identique à s2 ** -1: s1 est plus petit que s2 */ int compare(const char* s1, const char* s2) { /* Tant qu'on est pas arrivé à la fin de s1 ou s2 */ while (*s1 && *s2) { /* s1 est plus grand que s2, inutile de parcourir le reste de la chaîne */ if (*s1 > *s2) return 1; /* s1 est plus petit que s2, inutile de parcourir le reste de la chaîne */ if (*s1 < *s2) return -1; /* Les caractères sont identiques, on "avance" s1 et s2 pour comparer le prochain caractère */ ++s1; ++s2; } /* s1 plus court que s2 */ if (!*s1 && *s2) return -1; /* s1 plus long que s2 */ if (*s1 && !*s2) return 1; /* s1 et s2 ont la même taille et le même contenu, donc sont indentiques */ return 0; } void tri_a_bulle(Connexion tab[64], int nb_connexion) { int en_desordre = 1; int i = 0; int j = 0; for (i = 0; (i < nb_connexion) && en_desordre; ++i) { en_desordre = 0; for (j = 1; j < nb_connexion - i; ++j) { if (compare(tab[j - 1].ip, tab[j].ip) == 1) { echange(&tab[j], &tab[j - 1]); en_desordre = 1; } } } } void creer_connexions_pour_debug(Connexion tab[64], int* nb_connexion) { strcpy(tab[0].ip, "192.168.0.1"); tab[0].duree = 360; ++*nb_connexion; strcpy(tab[1].ip, "10.7.1.36"); tab[1].duree = 600; ++*nb_connexion; strcpy(tab[2].ip, "84.46.25.146"); tab[2].duree = 500; ++*nb_connexion; strcpy(tab[3].ip, "192.168.0.1"); tab[3].duree = 180; ++*nb_connexion; strcpy(tab[4].ip, "10.7.1.36"); tab[4].duree = 20; ++*nb_connexion; strcpy(tab[5].ip, "192.168.0.1"); tab[5].duree = 170; ++*nb_connexion; } void afficher_pour_debug(Connexion tab[64], int nb_connexion) { int i = 0; for (i = 0; i < nb_connexion; ++i) printf("tab[%i]: ip=%s, duree=%i ", i, tab[i].ip, tab[i].duree); } void afficher_duree_totale_connexion(Connexion tab[64], int nb_connexion) { int i = 0; int total = 0; for (i = 0; i < nb_connexion; ++i) total += tab[i].duree; printf("Duree totale de connexion: %i ", total); } void afficher_ips_sans_doublon(Connexion tab[64], int nb_connexion) { int i = 0; printf("Affichage des ips sans doublons: "); for (i = 0; i < nb_connexion; ++i) if (i == 0 || compare(tab[i - 1].ip, tab[i].ip) != 0) printf("%s ", tab[i].ip); printf(" "); } void afficher_liste_ips(Connexion tab[64], int nb_connexion) { tri_a_bulle(tab, nb_connexion); afficher_ips_sans_doublon(tab, nb_connexion); } int main(void) { Connexion tab[64]; int nb_connexion = 0; creer_connexions_pour_debug(tab, &nb_connexion); afficher_pour_debug(tab, nb_connexion); afficher_duree_totale_connexion(tab, nb_connexion); afficher_liste_ips(tab, nb_connexion); return 0; }

Exercice sur structure de Connexion

20 réponses

Votre réponse

Discussions similaires