> Le Site du Zéro > Les forums > Programmation > Langage C > Exercices pour débutants en C > Lecture du sujet

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

Pour accéder à cette section
Connectez-vous !

Page Précédente 1 2 3 ... 21 22 23 24 25 26 27 ... 50 51 52 53 Suivante

Auteur

Message

2 visiteurs sur ce sujet (2 anonymes)

Page Précédente 1 2 3 ... 21 22 23 24 25 26 27 ... 50 51 52 53 Suivante

zx-spectrum

# Posté le 15/04/2009 à 09:14:01

http://www.worldofspectrum.org

Reprise du dernier message de la page précédente :

bonjour
Citation : ShareMan

Bon, alors ton algo est exactement en O(2*256+n), donc si l'on simplifie, on a du O(n+256) et donc du O(n). C'est à peu près la même chose que bluestorm, sauf que tu passes par une variable i inutile. Comme bluestorm l'a dit, c'est négligeable ça, mais autant l'éviter quand c'est si flagrant.

Ainsi, (i= chaine[j]; compte[i]++;) devient (compte[chaine[j]]++;).

sauf que si ton compilo est bien reglé tu devrais avoir ceci :
Code : Bash

||=== a, Debug ===|
C:\Documents and Settings\J Luc\Mes documents\sobetra\a\main.c||In function `main':|
C:\Documents and Settings\J Luc\Mes documents\sobetra\a\main.c|35|warning: array subscript has type `char'|
||=== Build finished: 0 errors, 1 warnings ===|

et donc c'est pour cela que j'utilise une variable temporaire i !
@+

shareman

# Posté le 15/04/2009 à 12:39:56

charlotte <3

Ville : Mertzwiller
Pays : France métropolitaine

Bah tu peux toujours caster. De plus, le "problème" se pose tout de même avec i.

Édité le 15/04/2009 à 12:41:53 par shareman

Nouvel atelier : Codez votre propre petit préprocesseur pour langage C !
Citation : Woody Allen

Si l'au-delà existe, c'est à quelle distance du centre ville, et c'est ouvert jusqu'à quelle heure ?

zx-spectrum

# Posté le 15/04/2009 à 14:17:03

http://www.worldofspectrum.org

Citation : ShareMan

Bah tu peux toujours caster. De plus, le "problème" se pose tout de même avec i.

Eh bien non. Le fait de passer par une variable temporaire, m'enlève le warning !!
Qui peux me dire pourquoi ?
@+

shareman

# Posté le 15/04/2009 à 16:24:24

charlotte <3

Ville : Mertzwiller
Pays : France métropolitaine

Pour un petit truc comme ça, je me fous un peu de ce que me dit le compilateur. Il faut rester logique. En prenant mon premier code (où on met tout dans [] sans caster), le warning nous signale une "inattention". Si tu l'as comprise, tu en déduis que le même problème se pose avec i, warning ou pas. De plus, si tu es pointilleux et que tu trouves qu'un petit warning de ce genre fait tache dans ton programme, tu peux faire un cast, comme dit. Pour répondre à ta question, je n'en sais rien. Compilateur mal réglé sans doute.

Nouvel atelier : Codez votre propre petit préprocesseur pour langage C !
Citation : Woody Allen

Si l'au-delà existe, c'est à quelle distance du centre ville, et c'est ouvert jusqu'à quelle heure ?

pH+

# Posté le 15/04/2009 à 16:48:31

push me

Ville : Chaudfontaine
Pays : Belgique
études : HEPL INPRES

compte[(int) chaine[j]]++; enlève l'avertissement. J'imagine que l'avertissement est dû au simple fait que l'indice d'un tableau est un int ?

Édité le 15/04/2009 à 16:49:25 par pH+

shareman

# Posté le 15/04/2009 à 16:52:36

charlotte <3

Ville : Mertzwiller
Pays : France métropolitaine

Oui, bien sûr. Mais i est aussi un int. Bon, au font, c'est pas grave.

Nouvel atelier : Codez votre propre petit préprocesseur pour langage C !
Citation : Woody Allen

Si l'au-delà existe, c'est à quelle distance du centre ville, et c'est ouvert jusqu'à quelle heure ?

pH+

# Posté le 15/04/2009 à 17:05:04

push me

Ville : Chaudfontaine
Pays : Belgique
études : HEPL INPRES

L'avertissement du compilateur n'apparaît pas avec i et c'est logique vu que la conversion de type a lieu lorsque l'on affecte la valeur à i.

Goost

# Posté le 16/04/2009 à 07:23:30

études : INSA Lyon

L'avertissement est du au fait que l'indice que tu mets est un char et non un int, c'est tout, rien de grave dans ce cas, puisque le tableau a 256 cases

On peut tromper une fois mille personnes mais on ne peut pas tromper mille fois une personne

Secret (cliquez pour afficher)

Et voilà, un de plus... Petit curieux ! Ne lis-tu pas les mises en garde?

zx-spectrum

# Posté le 16/04/2009 à 08:50:03

http://www.worldofspectrum.org

Merci pour vos reponses.
Citation : sharemean

Compilateur mal réglé sans doute.

A priori non, car j'ai pris les options suivantes, sous les conseils de Ed !
Code : Bash

1 2	-Wall -Wextra -ansi -O -Wwrite-strings -Wstrict-prototypes -Wuninitialized -Wunreachable-code

Jaloyan1

# Posté le 16/04/2009 à 21:56:47

Sms = portable,forum = clavier
Avatar

Citation : 21

C'est quoi votre truc avec O(x) ?

Comme déjà dit, c'est la complexité de ton algorithme, plus elle est proche du logN, mieux c'est.
N représente le nombre de données à traiter.
Donc O(N) veut dire que son algorithme est linéaire, si tu as 5000 données à traiter en un temps x, si tu en avais 50000, ton algo mettrait 10 fois plus de temps en temps linéaire, après tu as le pire qui puisse arriver, c'est nⁿ de complexité.
Bien sur, cela est extrêmement gourmand et si tu as une complexité exponentielle, c'est déjà remarquable(c'est ironique).
Après tu as les complexité amorties, mais bon ce serait long pour t'expliquer.

Cependant, une petite remarque, on a pas les limites max des entrées, l'étendue des caractères, le temps max, cela peut être très important.
Et de préférence en cas d'un adressage direct, mettez votre tableau en variable globale, on ne le dira jamais assez, car si votre algo utilise des fonctions récursives, en moins d'un demi million d'appels récursifs + votre tableau ,vous aurez explosé la pile de votre RAM et vous aurez des résultats surprenants.

Édité le 16/04/2009 à 22:00:27 par Jaloyan1

Si quelqu'un vous dit : "Je me tue à vous le répéter", laissez-le mourir.

int x = 0; x >?= (a < b)?((a < c)?((a < d)?a:d):((c < d)?c:d)):((b < c)?((b < d)?b:d):((c < d)?c:d));
Quelqu'un a compris ce que ce code fait? :-°

shareman

# Posté le 16/04/2009 à 22:08:22

charlotte <3

Ville : Mertzwiller
Pays : France métropolitaine

Citation : Jaloyan1

Comme déjà dit, c'est la complexité de ton algorithme, plus elle est proche du logN, mieux c'est.

Euh... Oui, certes, mais pourquoi précisément log n ici ?

Nouvel atelier : Codez votre propre petit préprocesseur pour langage C !
Citation : Woody Allen

Si l'au-delà existe, c'est à quelle distance du centre ville, et c'est ouvert jusqu'à quelle heure ?

Jaloyan1

# Posté le 16/04/2009 à 22:14:41

Sms = portable,forum = clavier
Avatar

Citation : ShareMan

Citation : Jaloyan1

Comme déjà dit, c'est la complexité de ton algorithme, plus elle est proche du logN, mieux c'est.

Euh... Oui, certes, mais pourquoi précisément log n ici ?

car généralement il est un peu plus dur de faire un algo qui est mieux que le logN, O(1) exclus.

Mais ici le mieux que l'on peut faire c'est du O(N), car il va falloir au moins parcourir au moins 1 fois la chaine.

EDIT : non rien une bourde

Édité le 19/04/2009 à 17:24:02 par Jaloyan1

Si quelqu'un vous dit : "Je me tue à vous le répéter", laissez-le mourir.

int x = 0; x >?= (a < b)?((a < c)?((a < d)?a:d):((c < d)?c:d)):((b < c)?((b < d)?b:d):((c < d)?c:d));
Quelqu'un a compris ce que ce code fait? :-°

Monsieur_JaKy

# Posté le 18/04/2009 à 22:27:22

JaKy & Rory FTW!
Avatar

Ville : Bourges
Pays : France métropolitaine

Vivement le prochain exercice. Quelqu'un sait déjà sur quoi il portera ?

Lulz

freecircus

# Posté le 19/04/2009 à 11:45:15

"Se coucher tard nuit"

Citation : Jaloyan1

Mais ici le mieux que l'on peut faire c'est du O(N), car il va falloir au moins parcourir au moins 1 fois la chaine.
Cependant, il est possible de le faire avec du C++ en O(LogN)

hm par quelle sorcellerie est-ce possible ?

...clap clap!

shareman

# Posté le 19/04/2009 à 12:05:57

charlotte <3

Ville : Mertzwiller
Pays : France métropolitaine

Je rappelle que log(n) est inférieur à n. Donc avec du log(n), il y aura forcément des éléments que tu ne vas pas parcourir. Comment peux-tu dresser des stats si tu ne connais pas tout le contenu de la chaîne ? Donc log(n) pas possible ici (ni en C, ni en C++ hein).

Nouvel atelier : Codez votre propre petit préprocesseur pour langage C !
Citation : Woody Allen

Si l'au-delà existe, c'est à quelle distance du centre ville, et c'est ouvert jusqu'à quelle heure ?

Jaloyan1

# Posté le 19/04/2009 à 15:56:47

Sms = portable,forum = clavier
Avatar

delestage

Édité le 19/04/2009 à 17:24:54 par Jaloyan1

Si quelqu'un vous dit : "Je me tue à vous le répéter", laissez-le mourir.

int x = 0; x >?= (a < b)?((a < c)?((a < d)?a:d):((c < d)?c:d)):((b < c)?((b < d)?b:d):((c < d)?c:d));
Quelqu'un a compris ce que ce code fait? :-°

bluestorm

# Posté le 19/04/2009 à 17:10:31

dont ask to ask
Avatar

Blog
Twitter

De loin, ton histoire a l'air assez douteuse. Et le peu de détails que tu donnes n'inspire pas la confiance. Comment fais-tu, as-tu un schéma d'algorithme (ou carrément du code qui marche) à donner ?

Citation

Mais bon c'est si on a l'entrée directement sous forme de set, ce qui signifie une format spécial de fichiers ce qui implique un éditeur spécial.

Je ne sais pas de quel genre de "set" tu parles, et je ne suis pas convaincu qu'ils soient pratique pour manipuler des chaines. De plus, si tu fais du précalcul sur tes données, forcément tu peux avoir des résultats intéressants. Si j'ai le droit de choisir le format de fichier que je veux, et que je déclare que mon programme lit des fichiers dans le format "texte avec les statistiques de fréquences en en-tête", je peux avoir le résultat en O(1).

Citation

on pourrait faire les stats en O(LogN * 256). Soit O(LogN)

Comme je l'ai déjà dit, il faut, pour évaluer ces algorithmes, considérer la taille de l'alphabet comme une variable supplémentaire. Ton algorithme serait donc en O(A log N), où A est la taille de l'alphabet.

Considérer que "256" est ici une constante muette qui ne change pas la complexité, c'est faire une erreur d'appréciation qui peut donner lieu à des résultats aberrants. Exemple :
- mon ordinateur a une quantité d'espace de stockage finie
- son comportement dépend uniquement des données dans cet espace (portions "texte" des programmes compris), tant qu'il ne fait pas d'entrée sortie "externe" (par l'écran, par le réseau, etc.)
- donc il existe un nombre maximal d'états par lequel peut passer un programme qui ne fait pas d'entrée-sortie "externe" qui termine (ne boucle pas à l'infini)
- donc tous ces programmes sont en complexité O(1)

Édité le 19/04/2009 à 17:11:17 par bluestorm

big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog

Jaloyan1

# Posté le 19/04/2009 à 17:23:02

Sms = portable,forum = clavier
Avatar

Citation : bluestorm

Euh finalement je viens de relire la doc sur set, il s'avère qu'il ne stocke que des valeurs différentes.

Toutes mes excuses, je me suis trompé, on ne peut pas faire de statistiques sur ce problème.

Je modifie une partie de mes messages.

Pour ceux qui veulent quand même en apprendre sur le set :

http://www.cppreference.com/wiki/stl/set/count

Si quelqu'un vous dit : "Je me tue à vous le répéter", laissez-le mourir.

int x = 0; x >?= (a < b)?((a < c)?((a < d)?a:d):((c < d)?c:d)):((b < c)?((b < d)?b:d):((c < d)?c:d));
Quelqu'un a compris ce que ce code fait? :-°

Eusebus

# Posté le 21/04/2009 à 22:37:23

Geek mangeur de cookies
Avatar

Bien le bonjour/bonsoir.

Avec un peu de retard, voici la correction de l'exercice zStrstat que je vous avais proposé. Réponse a reçu 8 participations.
Il y avait trois possibilités pour les entrées, afin de satisfaire tout le monde. L'exercice en lui-même était assez simple, voici quelques propositions de correction pour chaque choix :

1er choix

Chaîne en dur, une des idées qui est revenue plusieurs fois était de stocker les caractères de référence (donc chiffres et alphabet) dans une chaîne, ce qui permettait de s'affranchir des problèmes d'encodage/charset.

Code : C

#include <stdio.h>
#include <ctype.h>

#define LEN 36

int main(void)
{
        const char str[] = "Ceci est une chaine de test.";
        const char alphanum[] = "0123456789abcdefghijklmnopqrstuvwxyz";
        int stat[LEN] = { 0 };
        size_t i, j;

        for (i = 0; str[i] != '\0'; i++)
        {
                int found = 0;
                char c = tolower(str[i]);

                for(j = 0; j < LEN && !found; j++)
                        if(c == alphanum[j])
                        {
                                found = 1;
                                stat[j]++;
                        }
        }

        printf("Statistiques pour la chaine \"%s\" :\n", str);

        for(i = 0; i < LEN; i++)
                if(stat[i] != 0)
                        printf("%c : %d\n", alphanum[i], stat[i]);

	putchar('\n');
        puts("**FIN**");

        return 0;
}

Je pense (et j'espère) que le code est suffisamment clair et parle de lui-même. On parcourt notre chaîne et on compare chaque caractère avec nos références. Le flag found permet d'arrêter les comparaisons lorsque qu'une correspondance est trouvée, ce qui permet de diminuer le nombre de tests à effectuer. Pour gérer à la fois les majuscules et les minuscules, il est plus simple de convertir en minuscules puis de faire les tests.

2e choix

La chaîne est récupérée via l'invite de commande. Pour changer de méthode de traitement du problème, je me permets de reprendre le code de bluestorm que j'ai légèrement modifié : changement de la condition d'arrêt du while, EOF changé en '\n' , il devient plus "simple" (peu de monde envoie un EOF à la console pour signifier la fin de la saisie), en revanche il ne permet plus d'avoir une entrée sur plusieurs lignes ; changement de isalpha() en isalnum() pour gérer la présence de chiffres :

Code : C

#include <stdio.h>
#include <ctype.h>

int main(void)
{
    int c, i, freqs[256] = {0};
    
    while ((c = tolower(getchar())) != '\n')
        if (isalnum(c))
            freqs[c]++;

    for (i = 0; i < 256; ++i)
        if (freqs[i] > 0)
            printf("'%c'\t%d\n", i, freqs[i]);

    return 0;
}

Le code exploite entièrement les fonctions que l'on retrouve dans la bibliothèque standard, et se trouve être très rapide. Dans le premier while, il y a lecture d'un caractère, passage en minuscule par la fonction tolower (qui, je le rappelle, renvoie la valeur du caractère lu s'il ne s'agit pas d'un caractère en majuscule) puis on cherche à savoir s'il s'agit d'un caractère alphanumérique. Si tel est le cas, on augmente de 1 la valeur qui correspond à ce caractère dans le tableau freqs . La place de chaque caractère est déterminée dans ce tableau par la valeur-même de ce caractère, donc le compteur est placé à l'indice dont la valeur est celle du caractère (phrase un peu longue, mais en lisant lentement vous devriez comprendre

). Une fois que l'on est arrivé au bout de notre chaine, on affiche donc nos statistiques.

3e choix

Pour le 3e choix, la lecture se fait dans un fichier. Le plus simple était de lire caractère par caractère, on pouvait aussi utiliser fgets() pour récupérer la (ou les) ligne(s), mais ça alourdit un peu l'ensemble. En reprenant les deux méthodes précédentes, on obtiendrait :

Code : C

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define LEN 36

int main(void)
{
        const char alphanum[] = "0123456789abcdefghijklmnopqrstuvwxyz";
        int stat[LEN] = { 0 };
        char c;
        size_t i, j;
        FILE *fp = fopen("bla.txt", "r");

        if(fp == NULL)
        {
                perror("fopen()");
                exit(EXIT_FAILURE);
        }

        while((c = tolower(fgetc(fp))) != EOF)
        {
                int found = 0;

                for(j = 0; j < LEN && !found; j++)
                        if(c == alphanum[j])
                        {
                                found = 1;
                                stat[j]++;
                        }
        }

        printf("Statistiques :\n");

        for(i = 0; i < LEN; i++)
                if(stat[i] != 0)
                        printf("%c : %d\n", alphanum[i], stat[i]);

        putchar('\n');
        puts("**FIN**");
        fclose(fp);

        return 0;
}

La seule différence vient de la lecture des caractères qui se fait via la fonction fgetc().

Avec la solution bluestormienne (désolé pour le néologisme foireux) :

Code : C

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

int main(void)
{
    int c, i, freqs[256] = {0};
    FILE *fp = fopen("foo.txt", "r");

    if(fp == NULL)
    {
            perror("fopen()");
            exit(EXIT_FAILURE);
    }

    while ((c = tolower(fgetc(fp))) != EOF)
        if (isalnum(c))
            freqs[c]++;

    for (i = 0; i < 256; ++i)
        if (freqs[i] > 0)
            printf("'%c'\t%d\n", i, freqs[i]);
    
    fclose(fp);

    return 0;
}

Voilà en ce qui concerne cet exercice. Si vous avez des questions, n'hésitez pas !
Le prochain exercice devrait arriver sous peu.

"Ce qui est affirmé sans preuve peut être nié sans preuve" Euclide
"Tout ensemble inductif admet au moins un élément maximal." Lemme de Zorn

Jaloyan1

# Posté le 21/04/2009 à 23:27:44

Sms = portable,forum = clavier
Avatar

Ce n'est pas pour te critiquer eusebus, je trouve que tu as fais un bon travail, mais par contre tes algorithmes sont un peu trop gourmant, tu as du (LEN * N) où n est la taille du texte en entrée, enfin c'est comme cela dans les cas où tu utilises le tableau[LEN]

et si lenght valait 200?

Je pense qu'il serait mieux d'utiliser le tableau à adressage direct (de 256 cases), ce qui serait plus pratique et pourrait réduire le temps d'exécution du programme.
Comme LEN est une constante, on peut dire que c'est du O(N), mais comme LEN peut être différent selon l'implémentation, si on a besoin d'une table ASCII complète, ou alors même de faire des statistiques unicode, le temps d'exécution risque d'augmenter très rapidement..

Si quelqu'un vous dit : "Je me tue à vous le répéter", laissez-le mourir.

int x = 0; x >?= (a < b)?((a < c)?((a < d)?a:d):((c < d)?c:d)):((b < c)?((b < d)?b:d):((c < d)?c:d));
Quelqu'un a compris ce que ce code fait? :-°

Eusebus

# Posté le 21/04/2009 à 23:58:35

Geek mangeur de cookies
Avatar

Ce n'est certes pas la manière la plus efficace mais elle a le mérite d'être facilement compréhensible je pense. Je n'ai effectivement pas précisé que LEN (utilisé car j'essaie d'éviter les nombre magique) est le nombre de caractères de référence et est valable quelles que soient la machine et l'implémentation, en fait c'est strlen(alphanum) . Je ne vois donc en fait pas du tout où tu veux en venir avec ton 2e paragraphe, vu que la taille du tableau est fixe, ni ce que viennent faire les termes "table ASCII complète" et "statistiques unicode" dans le cadre de l'exercice. Ni même ce que tu entends par statistiques unicode, en fait.

Et c'est bien pour cela que j'ai présenté la manière dont tu parles (dans "2e choix" et le 2e code de la partie 3) en m'appuyant sur le code de bluestorm. Personnellement j'avais codé de cette manière également, mais elle est déjà le fruit d'une réflexion plus poussée et qui, d'après ce que j'ai vu des codes proposés, n'est venu à l'esprit d'aucune personne à part bluestorm. Mais j'ai tenu à la présenter car celle méthode est très efficace oui.

Édité le 22/04/2009 à 00:02:28 par Eusebus

"Ce qui est affirmé sans preuve peut être nié sans preuve" Euclide
"Tout ensemble inductif admet au moins un élément maximal." Lemme de Zorn

zx-spectrum

# Posté le 22/04/2009 à 00:30:17

http://www.worldofspectrum.org

Citation : Jaloyan1

peux tu argumenter avec un algorithme de ton cru, que je puisse faire la différence? j'aime bien les explications faciles à comprendre.
@+

Jaloyan1

# Posté le 22/04/2009 à 08:37:11

Sms = portable,forum = clavier
Avatar

Citation : zx-spectrum

Citation : Jaloyan1

peux tu argumenter avec un algorithme de ton cru, que je puisse faire la différence? j'aime bien les explications faciles à comprendre.
@+

Ben en gros c'est le code de bluestorm, avec un tableau à adressage direct, (pour ceux qui ne le savent pas, c'est un tableau de 256 cases, 1 pour chaque caractère ascii)et à chaque fois que l'on rencontre un caractère ascii carac, on met tableau[tolower(carac)]++;
comme cela en temps linéaire, on obtient les statistiques.
Et on peut même reporter cette méthode en O(N) à des statistiques un peu plus compliquées comme un texte unicode.

Si quelqu'un vous dit : "Je me tue à vous le répéter", laissez-le mourir.

int x = 0; x >?= (a < b)?((a < c)?((a < d)?a:d):((c < d)?c:d)):((b < c)?((b < d)?b:d):((c < d)?c:d));
Quelqu'un a compris ce que ce code fait? :-°

zx-spectrum

# Posté le 22/04/2009 à 09:55:04

http://www.worldofspectrum.org

Citation : Jaloyan1

Citation : zx-spectrum

Citation : Jaloyan1

peux tu argumenter avec un algorithme de ton cru, que je puisse faire la différence? j'aime bien les explications faciles à comprendre.
@+

si tu regardes bien la correction d'Eusebus, il me semble qu'il propose cette solution dans :
le cas n°2 , le code de bluestorm
le cas n°3 bis ici : (un extrait)
Code : C

1
2
3

while ((c = tolower(fgetc(fp))) != EOF)
        if (isalnum(c))
            freqs[c]++;

ici on parcourt "une seule fois le buffer d'entrée",et on incremente comme tu le souligne.

Effectivement le cas n°1 et trois sont plus gourmands en temps d'execution..et c'est une autre façon de voir les choses, peut-être un peu plus facile à comprendre pour les débutants .

Citation : jaloyan

avec un tableau à adressage direct

au fait c'est quoi un tableau à adressage direct? Cela voudrait dire qu'il existe des tableaux à adressage indirect?

En fait j'ai pas compris ou tu voulais en venir ?
@+

Édité le 22/04/2009 à 10:01:45 par zx-spectrum

Eusebus

# Posté le 22/04/2009 à 13:51:29

Geek mangeur de cookies
Avatar

Petite astuce aussi pour la méthode "naïve", au lieu de placer les lettres dans l'ordre alphabétique, on peut aussi utiliser cette chaine-ci :

Code : C

1	const char alphanum[] = "esantirulodcpmqvgfbhxyjzkw0123456789";

qui classe les lettres par fréquence moyenne d'apparition dans un texte français (le fameux "esantirulo") et j'ai rejetté les chiffres à la fin. Ca permet de gagner un peu en rapidité, m'enfin sur ma machine par exemple, pour un texte de 704000 caractères (en intégrant la gestion des accents, une lettre accentuée comptant pour cette même-lettre sans accent) je passe de 0.156s à 0.140s.

"Ce qui est affirmé sans preuve peut être nié sans preuve" Euclide
"Tout ensemble inductif admet au moins un élément maximal." Lemme de Zorn

Jaloyan1

# Posté le 22/04/2009 à 13:58:34

Sms = portable,forum = clavier
Avatar

un tableau d'adressage direct est un tableau de la taille du nombres de possibilités pour une valeur donnée.
Chaque indice du tableau correspond à une valeur donnée.

Par exemple lorsqu'on dynamise un DFS sur un DAG(sinon on ne peut pas dynamiser), on utilise ce genre de tableau, une case pour chaque nœud du graphe (généralement).

Et donc dans ce cas, on utilise un tableau du nombre de possibilité pour une valeur, donc avec un char c'est 256, bref, c'est le code proposé.
Et donc dans un tableau à adressage direct, pour accéder à une case et inscrire par exemple que x a déjà été vu, tu fais tableau[x] = 1;
et donc tu vérifie que l'objet n'a pas été vu en 0(1), ce qui est un sérieux avantage si tu as un tableau d'adressage direct de 500000 cases par exemple.

Si quelqu'un vous dit : "Je me tue à vous le répéter", laissez-le mourir.

int x = 0; x >?= (a < b)?((a < c)?((a < d)?a:d):((c < d)?c:d)):((b < c)?((b < d)?b:d):((c < d)?c:d));
Quelqu'un a compris ce que ce code fait? :-°

zx-spectrum

# Posté le 22/04/2009 à 14:49:41

http://www.worldofspectrum.org

bonjour
Citation : Jaloyan1

Si tu peux STP ne pas utiliser trop d'abréviation (et oui cela fait 25 ans que je ne suis plus à l'école !!)
DFS : traduction?
DAG : traduction?

une definition du mode d'adressage

Citation : jaloyan

un tableau d'adressage direct est un tableau de la taille du nombres de possibilités pour une valeur donnée.
Chaque indice du tableau correspond à une valeur donnée.

je comprend pas la correlation que tu fais entre mode d'adressage et la dimension de ton tableau. J'ai toujours pas compris ce que tu voulais dire !!
Moi je crois que tu confonds plein de choses.
A mon sens : pour acceder directement à une donnée, un tableau est bien approprié. Car tu accedes à chaque élément avec un indice.
exemple tableau[indice] est l'élément n°indice du tableau

Dans le cas d'une liste chainée pour avoir l'element N°indice, tu vas être obligé de parcourir ta chaine j'usqu'au N°indice. Et la ce n'est plus un acces direct mais séquentiel, puisque on arrive par étape à l'élément numéroté indice !

C'est comme cela que je vois simplement les choses
@+

Jaloyan1

# Posté le 22/04/2009 à 15:10:45

Sms = portable,forum = clavier
Avatar

DFS : Depth First Search -> parcours en profondeur
DAG : Graphe orienté acyclique

Citation : zx-spectrum

Moi je crois que tu confonds plein de choses.

Non je n'arrive pas à l'exprimer, c'est différent.

Citation : zx-spectrum

A mon sens : pour acceder directement à une donnée, un tableau est bien approprié. Car tu accedes à chaque élément avec un indice.
exemple tableau[indice] est l'élément n°indice du tableau

Ben non, c'est pas ça, c'est juste que au lieu d'enregistrer chaque truc à une place au hasard, par exemple dans une liste dans doublons, dans le cas d'un tableau sans adressage direct, si j'envoie "dans"
on verra

Code : C

dejaVu[0] = d
dejaVu[1] = a
dejaVu[2] = n
dejaVu[3] = s

alors qu'avec l'adressage direct on aura

Code : C

dejaVu[d] = 1
dejaVu[a] = 1
dejaVu[n] = 1
dejaVu[s] = 1

et pour toutes les autres cases tu tableau[256] on aura 0

Je pense que si avec cet exemple tu n'a toujours pas compris, je pense que je ferais mieux de ne pas être prof plus tard dans la vie.

Édité le 22/04/2009 à 15:11:23 par Jaloyan1

Si quelqu'un vous dit : "Je me tue à vous le répéter", laissez-le mourir.

int x = 0; x >?= (a < b)?((a < c)?((a < d)?a:d):((c < d)?c:d)):((b < c)?((b < d)?b:d):((c < d)?c:d));
Quelqu'un a compris ce que ce code fait? :-°

Eusebus

# Posté le 22/04/2009 à 15:15:14

Geek mangeur de cookies
Avatar

Hum, désolé de te décevoir, mais même moi qui connais ce procédé j'ai du mal avec ton explication. Je vais essayer de reformuler.

@zx-spectrum :

Le tableau d'adressage direct est utile par exemple pour faire des statistiques => le nombre d'occurences de certains caractères dans un texte à tout hasard.

En gros, chaque caractère a une "valeur". Cette valeur, on l'utilisera comme indice dans le tableau pour repérer la case qui correspond à notre caractère.

Par exemple, on sait que dans la table ASCII (étendue), les caractères ont une valeur entre 0 et 255 (ce qui permet d'utiliser un char pour stocker cette valeur). Donc, on affecte un tableau contenant 256 cases, sachant que la case d'indice i correspondra au caractère dont la valeur est i. C'est ça le principe d'adressage direct : on utilise la valeur-même du caractère comme indice dans le tableau pour stocker les données afférentes à ce caractère.

Édité le 22/04/2009 à 15:29:15 par Eusebus

"Ce qui est affirmé sans preuve peut être nié sans preuve" Euclide
"Tout ensemble inductif admet au moins un élément maximal." Lemme de Zorn

Jaloyan1

# Posté le 22/04/2009 à 15:22:23

Sms = portable,forum = clavier
Avatar

Citation : Eusebus

Hum, désolé de te décevoir, mais même moi qui connais ce procédé j'ai du mal avec ton explication. Je vais essayer de reformuler.

<en cours>

d'accord j'élimine le métier de prof de mon avenir.

Si quelqu'un vous dit : "Je me tue à vous le répéter", laissez-le mourir.

int x = 0; x >?= (a < b)?((a < c)?((a < d)?a:d):((c < d)?c:d)):((b < c)?((b < d)?b:d):((c < d)?c:d));
Quelqu'un a compris ce que ce code fait? :-°

zx-spectrum

# Posté le 22/04/2009 à 18:04:12

http://www.worldofspectrum.org

bonjour
Citation : Eusebus

a priori c'est moi qui ai fait confusion entre :
mode "acces direct" aux données et "tableau d'adressage direct". En fait j'ai donné une definition de : acces direct et acces séquentiel aux données.

Merci pour vos explications
@+

Retour au forum "Langage C" ou à la liste des forums

Pour accéder à cette section
Connectez-vous !

Livre du Zéro

Cours

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

1er choix

2e choix

3e choix