lapras a écrit:On a des personnes qui ne peuvent parler que avec trois syllabes (qu'on note 'A', 'B' et 'C').
mais ils ne peuvent pas faire de répétition.
Par exemple
ABAB
est interdit
ou bien
ABCABC
est interdit
AA est interdit
etc..
je dois démontrer qu'il y'a une infinité de mots.
Mais c'est trop dur mathématiquement, on doit donc le faire avec un algo qui te sort les mots possibles pour la longueur que tu veux.
Mais cet algo a besoin des mots de la longueurs (i-1) pour faire un mot de la longueur i
Dans ce cas ce n'est pas la peine de continuer à chercher dans cette voie car même si ton programme trouve des mots de longueur 10000000000000000000000000000000000000...0000000000000000000000000 (ce qui m'étonnerait car ça demandera effectivement beaucoup d'espace disque pour stocker tous les mots de longueur i donnée, et beaucoup de temps de calcul pour vérifier qu'il n'y a pas de répétition en calculant ceux de longueur i+1, l'ordinateur risque de saturer avant), ça ne suffira pas à prouver qu'il existe une infinité de mots, l'ordinateur ne calculera toujours qu'un nombre fini de mots. Si la solution est effectivement à trouver en faisant un programme informatique, ce n'est pas le calcul systématique de tous les mots de longueur i qu'il faut faire.
À mon avis si on veut une vraie démonstration (et pas juste « il y a des mots de longueur i pour i < 100000000 donc il doit y avoir une infinité de mots » qui est le résultat que tu obtiendrais avec ton programme) il faut la faire mathématiquement, soit en montrant que s'il existe des mots de longueur i alors il y en a de longueur i+1 (ce qui revient à montrer que le programme que tu veux faire tournerait indéfiniment), soit par l'absurde, mais je n'ai pas cherché.