Les mots possibles

[Ululo]

Bonjour,

Je suis en train de construire un programme informatique permettant de déterminer une liste de mots possibles dans la lanque française, c'est-à-dire tout mot composé de lettres (accentuées ou non) de notre alphabet et dont le nombre de lettres est compris entre 1 et le nombre de lettres du mot anticonstitutionnellement.

À un moment, j'ai besoin de déterminer quel est le nombre de ces mots possibles.

Soit m le nombre de lettres dans le mot le plus long.
Soit n le nombre de lettres dans l'alphabet.

Comment obtenir à partir de ces deux valeurs le nombre de mots "possibles" ?

J'ai mis ça dans Enigme, mais je me suis peut-être trompé, hein, n'hésitez pas à déplacer ce sujet…

Merci d'avance,
Ululo.

Edit. : Je vois que le sujet a été déplacé en partie "Informatique" ; j'en remercie les modérateurs. Cependant, je précise que ce que je souhaiterais avoir est une formule mathématique, et non un programme informatique. Si c'est ce domaine qui vous intéresse néanmoins, je précise que j'utilise pour ce programme l'Applescript.

[fatal_error]

Salut,

On peut chercher le nombre de mot a 1 lettre, puis le nombre de mots a 2 lettres, etc, jusqu'a m.

Posons
Le nombre de mots qu'on peut générer, à k lettres c'est:
n^k
On peut donc avec une longueur max de m lettres créer

mots différents
Bien sûr, on aurait des mots de la langue française qui n'existent pas. Ex : aaaaa
Après, s'il s'agit d'énumérer tous les cas de constructions qui sont pas possibles, autant prendre un dico qui existe déjà...

[Ululo]

Super !
Merci beaucoup Fatal error.
En fait, déjà, en me disant que à k lettres le nombre de mots qu'on peut générer est n^k, tu m'aides beaucoup.
Pour mon programme, je n'ai qu'à faire une boucle, la première fois k=1, puis à chaque fois k=k+1, et on fait Letotal=Letotal+n^k, et on a fini !
Youpi, et encore merci !

Par contre, pour la suite, je veux dire la formule avec la fraction, je n'avais jamais vu de formule comme ça, j'ai un tout petit niveau en maths. Tu pourrais explixiter s'il te plaît ?

Sinon ce n'est pas grave, hein, j'ai compris le raisonnement.

Et pour les mots qui n'existent pas, le but est d'en créer le plus possible, Aaaaaa est bien sûr le bienvenu chez moi !

Merci encore,
Ululo.

[fatal_error]

re,

la formule elle vient de la somme des termes d'une suite géométrique de raison n que tu as pe vu en premiere ou quelquechose par là.

D'ailleurs, je me suis planté je l'ai faite commencer à 1.
La valeur correcte est donc


ps:c'est pas la peine de te fatiguer a faire une boucle si tu as le nombre directement donné par mais bon, si c'est exigé :happy2:

[Ululo]

Rien n'est exigé, c'est moi qui programme pour mon plaisir.
Donc j'ai essayé avec ta formule.
Sachant que j'ai 38 lettres dans mon alphabet (en comptant les voyelles accentuées) et 25 lettres dans mon mot le plus long…
Mon script me retourne…
2 147 483 647 !

Ca fait pas un peu beaucoup ?
Je sais pas moi, mais deux milliards !

Au fait, je n'ai rien vu du tout en 1ère, puisque je suis au collège.

Ululo.

[Doraki]

Non c'est loiiiiiiiin d'etre correct

Il y en a beaucoup plus que ça.
La formule donne 3207537835785284375345918642992788530258.
Et c'est bien le nombre de mots que tu cherches.
Ton script doit pas pouvoir calculer avec des grands nombres =p.

[Ululo]

Oui, je crois que c'est pas mon script qui n'est pas capable, c'est moi qui ai du mal à manipuler les nombres de cette taille-là et à les afficher sous forme décimale (euh, du genre, normale).
Mais ce nombre me refroidit un peu, étant donné qu'aucun ordi ou serveur (sauf si la NASA me prête un de ses joujous, mais j'en doute), ne pourra me calculer ce nombre de mots, enfin si peut-être, mais alors ça prendrait des plombes.

Merci pour tout,
Ululo.

[fatal_error]

re,

si j'ai pas trop mal compté, ya 40 chiffres dans le nombre de Doraki,
or un double va de cf ici
40<300 donc normalement tu dois avoir un problème dans ta boucle.

Par ailleurs, si tu avais depassé la limite, je pense que tu aurais une it de ton programme en cours d'execution.

Si tu dois calculer , en itératif, tu peux procéder ainsi (non testé)

Code: Tout sélectionner

double nbMotsGeneres(int nbLettres,int longueurMot)
{
  double puissance=1;
  double somme;
  int i,j;
  i=0;
  while(i<longueurMot)
  {
    puissance*=nbLettres;/* représente n^k avec n=nbLettres et k=i+1*/
    somme+=puissance; /* on ajoute n^k a la somme
    i++;
  }
  return somme;
}

Concernant le temps de calcul, on a une multiplication, une somme, une incrementation et un test.
soit 4*longueurMot.
ca doit pas prendre des plombes.

[Ululo]

Le calcul du nombre de mots, c'est qu'une partie du programme.
Le but du programme en entier, c'est de dresser une liste de tous ces mots.

[fatal_error]

Effectivement niveau mémoire ca risque d'etre lourd.
un char c'est 1 octet.
(Je passe les coeff)
10^{40} octets=10^{31} Go

Le problème, c'est pas le calcul du nombre de mots, c'est le stockage.

[PrépaQuébec]

Salut Fatal_error, juste un truc, à quoi sert ton j dans la fonction nbMotsGeneres? Tu avais une idée que tu n'as pas exploitée peut-être?
Ensuite tu déclares la variable somme de type double sans l'initialiser, or tu l'utilises dans ton while en Rvalue... (somme = somme + puissance) Ya bug là!

@++

[fatal_error]

w00t, t'es mieux que gcc :zen:

j ne sert a rien. Je savais qu'en C faut tout déclarer avant donc je l'ai écrit en me disant qu'il servirait peut etre.
Effectivement, la somme n'est pas initialisée et aurait du l'etre (a zero)

Enfin, puissance n'aurait pas du etre initialisée a 1 avant la définition des autres variables.(C)

[Patastronch]

Le problème, c'est pas le calcul du nombre de mots, c'est le stockage.

Sache que calculler 10^40 mots c'est pas un probleme de mémoire seulement mais aussi un probleme de temps. Mais c'est quoi cette nouvelle génération d'informaticiens qui n'a aucune notion de complexité algorithmique !

[fatal_error]

calculler 10^40 mots c'est différent de calculer le nombre de mots.
D'ailleurs, sauf erreur, un mot ca se calcule pas. Ca se crée, ca se génère...

Mais je te concède n'avoir pas beaucoup de notions sur la compléxité algorithmique :)

Edit: apres coup je comprends mieux le sens du message.
Effectivement, les n boucles imbriquées font mal.
La complexité exponentielle c'est pas bien.

[PrépaQuébec]

Salut,

Renseigne-toi sur la notion grand O fatal_error, moyen théorique pour évaluer l'efficacité algorithmique.

Stef