Dans le cadre d'un exercice de cours dans lequel nous devons réaliser un solveur pour un jeu que nous avons programmé (je vous passe les détails du jeu). J'ai pensé à réaliser un algorithme qui affiche tous les mots de taille k sur l'alphabet 0,1,2,3. Par exemple pour les mots de taille 3 il existerai 000; 001; 010; 100; 101; 110 ect...
Le problème est que je ne vois pas trop comment faire cela en c.
Par exemple je commence par la combinaison 000 après je fais par exemple toutes les combinaisons qui commence par 1 donc 100 101 102 103 110 111 112 ect... Et ensuite je fais toutes les combinaisons qui commence par 2. Comme si j'essayais d'ouvrir un cadenas sans connaître le code
combinaison <- "0000"
tab[4] = {0,0,0,0}
k <- 4
tant que k > 0
faire
memoriser combinaison
incrementer tab[k]
tant que k > 0 && tab[k] == 4
faire
tab[k] <- 0
decrementer k
si k > 0 alors
incrementer tab[k]
finsi
finfaire
pour i de 1 a 4 faire
combinaison[i] <- '0' + tab[i]
finfaire
Je ne crois pas mettre trompé.
A toi de traduire en C!
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Pour le premier, on garde le nombre dans un tableau. A un moment on arrive à 0212 par exemple. Le suivant, on l'obtient en à jouant 1 à droite; soit 0213. Celui d'après, pareil, sauf qu'on est arrivé à 3, alors on revient à 0 et on augmente le chiffre qui est à sa gauche.
Si on généralise, on voit que l'opération passer au suivant consiste à remplacer tous les 3 qui sont à droite par des 0, et incrémenter le chiffre de gauche, si il y en a.
* donnée : un tableau chiffre[taille]
* initialiser à 0
* opération : passer au suivant :
position = taille - 1
tant que position >= 0 et chiffre[position] = base-1
faire
| chiffre[position] = 0
| position = position - 1
si position >= 0
| chiffre[position] += 1
sinon
| c'est fini
Autre approche, il y a $base^{taille}$ manières de remplir le tableau. Il suffit d'avoir une boucle avec un indice qui va de 0 à $base^{taille}, et de décomposer l'indice sur la base (le chiffre de droite c'est indice%base, celui d'avant (indice/base)% base, etc.
En dépit du format douteux de mon code, ça fait ce que tu suggères dans ta première approche.
En changeant RSIZE et NBASE, je peux changer à volonté la longueur du registre (nombre de digits) et la base (4 ici).
L'autre possibilité consiste à incrémenter un nombre de NBASE et de faire la conversion comme 'printf' le ferait, mais pour une base quelconque.
On se tape encore des modulo et des divisions.
Pour reprendre mes constantes, on augmentera NBASE^RSIZE fois.
Si NBASE vaut 4 et RSIZE vaut 3, j'aurai 4^3 = 64 incrémentations.
Cette dernière façon nous limite à la grandeur d'un 'int' ou d'un 'long long'.
Le Tout est souvent plus grand que la somme de ses parties.
Aide algorithme brute force
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.