Recherche dichotomique en C dans fichier [Résolu/Fermé]

Signaler
-
 DzarGol -
Bonjour, j'ai un petit problème en langage C... Je cherche à faire une recherche dans un fichier contenant un dictionnaire, c'et pour un programme de scrabble... Dnc j'ai besoin de faire une recherche dichotomique dans mon fichier pour savoir si le mot que j'ai a vérifier existe.
Le problème est que je ne sais pas vraiment comment utiliser la recherche dichotomique dans un fichier, puisque ça ne fonctionne pas de la meme manierre que dans un tableau.
Si vous savez comment faire et que vous avez du temps à me consacrer, merci d'avance!!!

9 réponses

Messages postés
1877
Date d'inscription
jeudi 1 novembre 2001
Statut
Membre
Dernière intervention
9 janvier 2008
110
ben, tu lis le fichier et tu le charges dans un tableau... (en RAM donc)

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
3
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 80980 internautes nous ont dit merci ce mois-ci

Messages postés
89
Date d'inscription
vendredi 3 janvier 2003
Statut
Membre
Dernière intervention
19 janvier 2006
21
Salut,

Avant tout je crois qu'il serait utile que tu précises exactement ce que tu veux dire dans "un fichier contenant un dictionnaire". Je veux dire qu'il faudrait préciser le type de format de fichier et la structure de données employé pour conserver ton dictionnaire.

En effet, comme tu parles de ta capacité à faire cette recherche dans un tableau mais pas un fichier je penses que c'est de là que vient ton problème?

@+ Lord Woden ;o)
Messages postés
1877
Date d'inscription
jeudi 1 novembre 2001
Statut
Membre
Dernière intervention
9 janvier 2008
110
De toute façon, à moins que ton fichier ne fasse plus de quelques Mo, il vaut mieux le charger en mémoire justement... sinon ta recherche va être extrêmement lente.

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
oui, désolée, j'ai oublié de préciser.
C'est un fichier txt, qui contient environ 360 000 mots.
J'ai réussi à effectuer cette recherche avec un simple strcmp, mais il se trouve que cela ralentit notre programme de scrabble, donc je pensais effectuer une recherche dichotomique pour gagner su temps. Le problème de créer un tableau de mots contenant mon dico c'est que ce serait beaucoup trop lourd, alors je ne sais pas comment faire pour faire cette recherche dichotomique sans passer mon fichier txt en tableau.

j'espère avoir été un peu plus claire...
teebo
Messages postés
33567
Date d'inscription
jeudi 14 octobre 2004
Statut
Modérateur
Dernière intervention
24 février 2011
1653 > batmat
Messages postés
1877
Date d'inscription
jeudi 1 novembre 2001
Statut
Membre
Dernière intervention
9 janvier 2008

C'est presque toujours vrai (sauf quelques cas particuliers de programmes), j'ai meme vu une boite ou il leur fallait une heure pour lancer leur soft, ca genait personne, ils prenaient leur cafe, tapaient la discute, lisaient les mails en arrivant et voila :O)

.  .
\_/
fou2dodie
Messages postés
606
Date d'inscription
mercredi 6 juin 2001
Statut
Membre
Dernière intervention
29 août 2006
32 > teebo
Messages postés
33567
Date d'inscription
jeudi 14 octobre 2004
Statut
Modérateur
Dernière intervention
24 février 2011

ouai mais j'iamgine mal son prof lors de sa soutenance partir prendre un café et taper la discute le tant que le programme se lance ;0)

LMCT (H -2 avant que je te rejoigne ma dodie)

j'ai touché le fond
maintenant je creuse
teebo
Messages postés
33567
Date d'inscription
jeudi 14 octobre 2004
Statut
Modérateur
Dernière intervention
24 février 2011
1653 > fou2dodie
Messages postés
606
Date d'inscription
mercredi 6 juin 2001
Statut
Membre
Dernière intervention
29 août 2006

Bien vu :-DDD

.  .
\_/
batmat
Messages postés
1877
Date d'inscription
jeudi 1 novembre 2001
Statut
Membre
Dernière intervention
9 janvier 2008
110 > teebo
Messages postés
33567
Date d'inscription
jeudi 14 octobre 2004
Statut
Modérateur
Dernière intervention
24 février 2011

Ouai, mais il vaudrait mieux qu'il le prenne avant, que de penser pendant :
"J'devrais aller chercher un café moi !"

:-)

@++
Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
Bonjour,
je dois faire un projet "scrabble" en langage C pour le moment
je sias pas d'ou commencer pouvez vous m'aider .
merci
je vais peut etre vous paraître stupide, mais qu'est-ce que tu entends par passe le en ram? je comprends ce que tu veux dire, mais je ne vois pas du tout comment faire ça.
je ne suis pas très douée en C, en fait je n'ai commencé qu'il y a quelques moi et je reconnais que tout ce qui concerne la mémoire est un peu flou pour moi...
J'ai fait un petit prog en basic et voici les resultats:

analyse du dico en cours...
Le programme a trouvé 369085 Mots dans le dico.
chargement en cours
100%
creation des phrases...
creation de la phrase 739 / 739
quel mot voulez-vous chercher
?MAISON
ce mot est bien dans le dico
temps de recherche : 141 ms
quel mot voulez-vous chercher
?ZYGOMATIQUE
ce mot est bien dans le dico
temps de recherche : 281 ms
quel mot voulez-vous chercher
?AVION
ce mot est bien dans le dico
temps de recherche : 0 ms
quel mot voulez-vous chercher
?MAISON
ce mot est bien dans le dico
temps de recherche : 141 ms
quel mot voulez-vous chercher
?LOIRE
ce mot est bien dans le dico
temps de recherche : 16 ms
quel mot voulez-vous chercher
?


j'ai un dico de 370 000 mots
je le charge en memoire dans un tableau puis je cree des phrases de 500 mots chacunes

enfin je teste la presence du mot que je cherche dans l'une de ces phrases.

si tu veux la source la voici:

        print "analyse du dico en cours..."
        open "dico.txt" for input as #dico
            while eof(#dico)=0
                scan
                line input #dico, mot$
                mot$=upper$(word$(mot$,1))
                if mot$=mot2$ then goto [reload.cnn]
                nb=nb+1
                if int(nb/5000)=nb/5000 then locate 1,2:print nb
                mot2$=mot$
                [reload.cnn]
            wend
        close #dico
        locate 1,2:print "Le programme a trouvé ";nb;" Mots dans le dico."
        print "chargement en cours"
        nbt=nb
        dim dico$(nbt)
        nb=0
        open "dico.txt" for input as #dico
            while eof(#dico)=0
                scan
                line input #dico, mot$
                mot$=upper$(word$(mot$,1))
                if mot$=mot2$ then goto [reload.cnt]
                nb=nb+1
                mot2$=mot$
                if int(nb*100/nbt)=nb*100/nbt then locate 1,4:print using("###",(nb*100/nbt));"%"
                dico$(nb)=mot$
                [reload.cnt]
            wend
        close #dico
        print "creation des phrases..."
        nbph=int(nbt/500)+1
        'print nbph
        dim ph$(nbph)
        trace 2
        for i=1 to nbt
            nump=int(i/500)+1
            if nump<>nump2 then
                nump2=nump
                locate 1,6:print "creation de la phrase ";nump;" / ";nbph
            end if
            ph$(nump)=ph$(nump)+" "+dico$(i)
        next i
    [suite]
        print "quel mot voulez-vous chercher"
        input r$
        r$=" "+upper$(r$)+" "
        t=time$("ms")
        for i=1 to nbph
            if instr(ph$(i),r$) then okmot=1:exit for
        next i
        t2=time$("ms")
        if okmot=1 then
            print "ce mot est bien dans le dico"
        else
            print "ce mot n'est pas dans le dico"
        end if
        print "temps de recherche : ";(t2-t);" ms"
    goto [suite]
    
    wait


c'est ecrit en Liberty BASIC, donc en C tu devrais exploser les temps, tout le monde sait que le basic, c'est lent ! (lol)

@++
y a pas moyen de créer une structure spéciale, genre un arbre binaire de recherche (basé sur le dichotomique, d'ailleurs), le stocker en mémoire au démarrage et faire ensuite des accès dessus pour la recherche? en C, ça devrait se programmer assez bien, et les structures ABR sont dans les plus rapides pour faire une recherche...

à voir... ;-)

(au fait, je suis moi aussi sur un projet de Scrabble en C, donc si vous trouvez une soluce en C, prévenez... ;-) )

@++
Messages postés
1072
Date d'inscription
dimanche 11 février 2001
Statut
Membre
Dernière intervention
29 janvier 2006
206
J'ai croisé un jour déjà lointain, l'auteur d'un site avec jeu en ligne, qui m'a dit que son dictionnaire, sans doute en Java, occupait moins de 500ko.
Je suppose qu'il s'agit d'une sorte d'arbre dont les clés sont d'abord à une lettre (sous-arbre dont les mots commencent par ...), etc. Les feuilles sont les mots du dictionnaire, mais on peut supposer que les féminins, les pluriels, les conjugaisons sont gérés par des pointeurs vers quelques règles de génération des terminaisons.
Je sais que le jeu proposé n'applique aucune stratégie, se contentant de proposer la solution rapportant le maximum de points, compte-tenu des lettres déjà en place, et autres multiplicateurs de la grille.
Mon meilleur score (je ne suis pas un spécialiste) est de -40 par rapport à celui de la "machine" !!!

Le site en question : http://duel-de-mots.com/
en fait, j'avais aussi trouvé une structure bizarre permettant de mettre l'ODS4 de 4Mo en 400Ko, mais c un algo assez compliqué... Il faut aller voir sur ce site : http://www.nongnu.org/eliot/